Abundance
Abundance

Reputation: 2183

Nested Hash Via Recursion in Ruby

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.

Upvotes: 4

Views: 1042

Answers (2)

Aleksei Matiushkin
Aleksei Matiushkin

Reputation: 121020

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.

Upvotes: 4

SRack
SRack

Reputation: 12223

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

Upvotes: 2

Related Questions