Nested Hash Via Recursion in Ruby

Question

I've been trying to make a nested default hash programmatically in Ruby, basically a short-hand for Ruby's :

h = Hash.new {|h,k| h[k] = Hash.new}

I'd like to extend this to work to as many levels as needed. I made the following function:

def nested_hash(level, default={})
   return default if level == 0
   return Hash.new{ |h,k| h[k] = nested_hash(level - 1, default) }
end

It looks like it's working correctly but I run into the following issue when creating multiple keys

h = nested_hash(1)
h[0][1] = [1, 2, 3] # h is {0=>{1=>[1, 2, 3]}}
h[2] # should give a new Hash, but returns {1=>[1, 2, 3]}
h # {0=>{1=>[1, 2, 3]}, 2=>{1=>[1, 2, 3]}}

Why is the default value changing for the function and becoming the previously set value?

EDIT

I've found a solution that works:

def nested_hash(level, default={})
    return Hash.new{ |h,k| h[k] = default } if level <= 1
    Hash.new{ |h,k| h[k] = nested_hash(level - 1, default) }
end

Never mind, this doesn't work either in a similar way:

h = nested_hash(1)
h[0][1] = [1, 2, 3]
h[2][0] # nil
h # {0=>{1=>[1, 2, 3]}, 2=>{1=>[1, 2, 3]}}

I'm still confused as to why the original default was shared amongst the keys.

Aleksei Matiushkin · Accepted Answer · 2019-02-07 03:51:33Z

4

Just out of curiosity:

hash =
  Hash.new do |h, k|
    h[k] = h.dup.clear.extend(Module.new do
      define_method(:level, ->{ h.level - 1 })
    end).tap { |this| raise "🔥" if this.level <= 0 }
  end.extend(Module.new { define_method(:level, ->{ 5 }) })

#⇒ {}

hash["0"]["1"]["2"]["3"]
#⇒ {}
hash["0"]["1"]["2"]["3"]["4"]
#⇒ RuntimeError: "🔥"

Or, as a function:

def nhash lvl
  Hash.new do |h, k|
    h[k] = h.dup.clear.extend(Module.new do
      define_method(:level, ->{ h.level - 1 })
    end).tap { |this| raise "🔥" if this.level < 0 }
  end.extend(Module.new { define_method(:level, ->{ lvl }) })
end

Resulting in:

✎ h = nhash 2
#⇒ {}
✎ h[0][1] = [1, 2, 3]
#⇒ [1, 2, 3]
✎ h[2][0]
#⇒ {}
✎ h[2][0][5]
#⇒ RuntimeError: 🔥

One might reset the default proc instead of raising if necessary.

The only drawback of this approach, on attempt to call the level above permitted, all the intermediate empty hashes will be created. This also might be overcome by defining the method, accumulating the path (instead of simply returning the level,) and erasing empty parents before raising.

edited Feb 7, 2019 at 3:51

answered Feb 6, 2019 at 18:30

Aleksei Matiushkin

121k12 gold badges109 silver badges173 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Mulan Over a year ago

Great answer. Though I'm left wondering why h.dup.clear is needed instead of just a new empty hash?

Mulan Over a year ago

Oh, maybe to inherit the dynamic :level method? Very interesting approach :D

Abundance Over a year ago

Can we extend this to have a default value? Ideally, I wanted this to work with an empty array as a key as well. Something like h = nhash(2, []) where I can do h[0][1] << 1 afterwards. Or even something like h = nhash(2, 0), where I can do h[0][1] += 1

Aleksei Matiushkin Over a year ago

“Can we extend [...]?”—Sure you can.

SRack · Accepted Answer · 2019-02-06 17:21:01Z

2

You can use default_proc for this. The best explanation is that given in the docs:

If Hash::new was invoked with a block, return that block, otherwise return nil.

So in this case, each new hash key is instantiated with its parent hash's default.

For example:

hash = Hash.new { |h, k| h[k] = Hash.new(&h.default_proc) }

That way, every nested level will have the same default:

hash[0][1] = [1, 2, 3]
hash[:first_level] # => {}
hash[:first_level][:second_level] # => {}
hash[2] # => {}
hash # => {0=>{1=>[1, 2, 3]}, :first_level=>{:second_level=>{}}, 2=>{}}

Edit based on comment:

In that case, you could use something ugly, though working, like this:

hash = Hash.new { |h, k| h[k] = Hash.new { |h, k| h[k] = Hash.new { |h, k| h[k] = raise('Too Deep') } } }
hash[1] # => {}
hash[1][2] # => {}
hash[1][2][3] # => RuntimeError: Too Deep

edited Feb 6, 2019 at 17:21

answered Feb 6, 2019 at 17:00

SRack

12.4k7 gold badges55 silver badges66 bronze badges

4 Comments

Abundance Over a year ago

This is indeed very cool, but I'd like to have a hard cut-off for the levels. hash[0][1][2][3] gives an empty hash, whereas I'd like to have it give an error.

SRack Over a year ago

Thanks for the update @Abundance - got led astray by "I'd like to extend this to work to as many levels as needed". See you've reached a nice solution though, glad you've got it going.

Aleksei Matiushkin Over a year ago

@SRack you might be interested: I slightly extended your idea in my answer to make the length dynamically configured :)

SRack Over a year ago

Thanks for the comment @AlekseiMatiushkin, that's a great answer you've put together. Glad you dropped this in here or I might have missed it :)

Collectives™ on Stack Overflow

Nested Hash Via Recursion in Ruby

2 Answers 2

4 Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related