Tuesday, May 15, 2007

Dynamic Arbitrary Depth Hashes In Ruby

UPDATE: Charles Duan has an interesting article in a similar vein.

Arbitrary array and hash depth constructs cannot be created in Ruby in the way you would in Perl or PHP. The following will simply fail with an error:

irb(main):001:0> a = []
=> []
irb(main):002:0> a[1][2][3][4] = 1
NoMethodError: undefined method `[]' for nil:NilClass
from (irb):2
irb(main):003:0> h = {}
=> {}
irb(main):004:0> h[1][2][3][4] = 5
NoMethodError: undefined method `[]' for nil:NilClass
from (irb):4

When dynamically constructing your array or hash (aka Autovivification) this really gets in the way.

Autovivification
This is a dynamic data structure creation feature that can be found in Perl and PHP (those are the ones I know of). It allows you to create dynamic, complex, nested data structures based on the types implied in the syntax of the statement of code accessed through the data structure.

IOW, the act of fetching or storing a value at a leaf through a branch dynamically creates the branch(es) to the leaf.

VivifiedHash
One approach is to do the following:

irb(main):011:0* VivifiedHash = Hash.new(&(p=lambda{|h,k| h[k] = Hash.new(&p)}))
=> {}
irb(main):012:0> VivifiedHash[1][2][3][4] = 5
=> 5
irb(main):013:0> VivifiedHash[1][2][3][4]
=> 5
irb(main):014:0> VivifiedHash[1][2][3]
=> {4=>5}
irb(main):015:0> VivifiedHash[1][2]
=> {3=>{4=>5}}
irb(main):016:0> VivifiedHash[1]
=> {2=>{3=>{4=>5}}}
irb(main):017:0> VivifiedHash
=> {1=>{2=>{3=>{4=>5}}}}

All this does is recursively assign the default key of the hash a new hash object as value. Each branch you specify in your assignment will recursively trigger the creation of a new hash.

Limitations
The limitation on this are of course that your data structure cannot contain anything but hashes as branches. Leaf nodes can be any data type though.

Sources

  1. Ruby Hashes of Arbitrary Depth

  2. Multidimensional arrays and hashes discussion on the RubyTalk mailing

  3. Auto Vivification

1 comment:

Brian Katzung said...

You might also try my gem "xkeys".

It facilitates traversal (and autovivification) of nested arrays and hashes.

It uses a create-on-set approach rather than create-on-get, so accessing a non-existent element returns nil (or something else if you prefer) rather than a new empty hash.

About Me

My photo
I love solving real-world problems with code and systems (web apps, distributed systems and all the bits and pieces in-between).