This post originated from an RSS feed registered with Ruby Buzz by Eigen Class. Original Post: Recursive data structures, #hash and #eql? Feed Title: Eigenclass Feed URL: http://feeds.feedburner.com/eigenclass Feed Description: Ruby stuff --- trying to stay away from triviality. Latest Ruby Buzz Posts Latest Ruby Buzz Posts by Eigen Class Latest Posts From Eigenclass

In ruby-talk:167185, I showed a way to use hashes as keys in hashes without degrading the efficiency of the hash (too much). It involved creating objects on the fly with the appropriate #eql? and #hash methods, as we often do with hashes.

Some time later, I realized it would fail horribly (SystemStackError) if the hash contained itself (or one of its elements did, transitively). And then I asked myself, "am I really doing it that much worse than Ruby?". We know that the semantics of Hash#{eql?,hash} are such that "recursive hashes" are fine, but what about their cousin, Array?

 [RUBY_VERSION, RUBY_RELEASE_DATE]  # => ["1.8.3", "2005-09-24"]
 W = lambda{|x|x<<x}
 W[[]].hash                         # => 
 # ~> -:3:in `hash': stack level too deep (SystemStackError)
 # ~> 	from -:3

"Mmmm surely 1.9 will know better":

 [RUBY_VERSION, RUBY_RELEASE_DATE]  # => ["1.9.0", "2005-11-03"]
 W = lambda{|x|x<<x}
 W[[]].hash                         # => 2
 W[[]].eql? W[[]]                   # => 
 # ~> -:4:in `eql?': stack level too deep (SystemStackError)
 # ~> 	from -:4

Alright, so Hash#hash got wiser, but eql? is still doing a recursive element-by-element comparison.

Just to make sure, let's verify that Hash#{eql?,hash} can handle recursion (by not handling it at all, that is...)

 W2 = lambda{|x| x[x] = x}
 W2[{}].hash                        # => -605020064
 W2[{}].hash                        # => -605020114
 W2[{}].eql? W2[{}]                 # => false
 W2[{}] == W2[{}]                   # => false
 {} == {}                           # => true
 {1=>{}} == {1=>{}}                 # => true
 { {}=>1 } == { {}=>1 }             # => false

The two last lines differ because

 {} == {}                           # => true
 {}.eql?({})                        # => false
 

We finally arrive to our small challenge:

Can we create an Array#eql? method able to withstand recursive data structures consisting of arrays?

The default definition (rb_ary_eql) is essentially equivalent to:

 class Array
   def eql?(o) # !> method redefined; discarding old eql?
     return true if o.object_id == object_id
     return false unless Array === o
     return false if o.size != size
     
     size.times{|i| return false unless self[i].eql? o[i] }
     true
   end
 end

Let's verify that is behaves as badly as the default one. The handy lambda we've been using is called W because it's reminiscent of the Omega combinator:

 W = lambda{|x|x<<x}
 W[[]].eql? W[[]]                   # => 
                           
 # ~> -:3:in `eql?': stack level too deep (SystemStackError)
 # ~> 	from -:7:in `eql?'
 # ~> 	from -:7:in `eql?'
 # ~> 	from -:7:in `eql?'
 # ~> 	from -:7:in `eql?'
 # ~> 	from -:7:in `eql?'
 # ~> 	from -:7:in `eql?'
 # ~> 	from -:7:in `eql?'
 # ~> 	from -:7:in `eql?'
 # ~> 	 ... 4477 levels...
 # ~> 	from -:7:in `eql?'
 # ~> 	from -:7:in `eql?'
 # ~> 	from -:7:in `eql?'
 # ~> 	from -:16

Great, this shows we have something to play with.