Autovivification with Hashes

For you Perl folk, you may be familiar with the term autovivification. In essence, that is where an empty data structure gets automatically created if it is referenced, but does not exist.

For example, consider a hash. Let's say we want a two dimensional hash such that we can write:

1
2

    points = Hash.new
    points[1][2] = 5

The problem here is that points[1] must return a hash, and this hash is in turn accessed with the key '2'. It would be the same thing if we wrote:

1
2
3

    points = Hash.new
    tmp = points[1]
    tmp[2] = 5

All this is fine and good except that it does not work. points[1] returns nil because the default return argument for a Hash when it is referenced with a non-existant key is nil. But, we can change that.

1
2
3
4

    points = Hash.new(Hash.new)
    tmp = points[1]                         #=> {}
    tmp[2] = 5                              #=> 5
    points                                  #=> {}

Well, that wasn't such a good idea. points[1] returned a hash, but it never got applied to the original points hash. Even if we write this as points[1][2] = 5, we still get points to be an empty hash.

Blocks to the Rescue

What we need is to use the block form of Hash.new If a block is supplied to #new, it will be called with hash object and the key. So, to repeat the above, but with a block, we write:

1
2

    points = Hash.new { |h,k| h[k] = {} }
    points[1][2] = 5                        #=> {1=>{2=>5}}

If that was too quick to realize what just happend, we can break it down into two steps, like we did above, and see just what is happening:

1
2
3
4
5

    points = Hash.new{ |h,k| h[k] = {}}
    tmp = points[1]                         #=> {}
    points                                  #=> {1=>{}}
    tmp[2] = 5                              #=> 5
    points                                  #=> {1=>{2=>5}}

The expression points[1] actually creates a key-value pair and automatically sets the value to {}, just like we told it to inside the block that was passed to Hash.new.

Customizing Vivification

Now, that's all well and good, but what if we wanted to have our final value be an array. For example:

1
2

    points[1][2] << 5
    points[1][2] << 10

For this, we just need to make a small addition to our block that we pass to #new.

1
2
3

    points = Hash.new { |h,k| h[k] = Hash.new { |hh,kk| hh[kk] = [] }}
    points[1][2] << 5      #=> {1={2=>[5]}}
    points[1][2] << 10     #=> {1={2=>[5, 10]}}

Well, now that's pretty nifty.

Endless Vivification

What if we need a hash that has an arbitrary number of arguments. For example, say we wanted to represent a directory tree with a hash. We could end up with something like:

1
2

    tree["etc"]["samba"]["smb.conf"]              #=> contents of "smb.conf"
    tree["home"]["me"][".ssh"]["authorized_keys"] #=> list of keys

Here is where we enter into the magic and mysterious land of recursive lambda's. In the example above, it would be equivalent to write the Hash constructors as:

1
2

    blk =  lambda { |h,k| h[k] = {}}
    points = Hash.new &blk

or

1
2

    blk =  lambda { |h,k| h[k] = Hash.new { |hh,kk| hh[kk] = [] }}
    points = Hash.new &blk

But, to have a 'never ending' constructor, we define the block using recursion:

1
2
3
4
5
6
7

    blk = lambda { |h,k| h[k] = Hash.new &blk }
    tree = Hash.new &blk
    tree = Hash.new &blk   #=> {}
    tree[:a][:b][:c] = 4   #=> 4
    tree[:x][:y] = 1       #=> 1
    tree[:fred] = "sally"  #=> "sally"
    tree                   #=> {:a=>{:b=>{:c=>4}}, :x=>{:y=>1}, :fred=>"sally"}

Now, isn't that cool!

It's not too bad once you get used to it, but it can be a bit confusing at first.