[ruby-core:24773] Re: [Bug #1852] Enumerable's #hash Raises ArgumentError When Recursive Values are Present

In article <[e-mail]>,
  Yusuke ENDOH <[e-mail]> writes:

> The following program implements a graph with adjacency list by
> using Array and Struct:
>
>   Node = Struct.new(:item, :neighbors)
>   node1 = Node.new(1, [])
>   node2 = Node.new(2, [node1])
>   node1.neighbors << node2

If node2's item is 1, eql? cannot distinguish node1 and
node2 on Ruby 1.9.2.

So, DFS doesn't work well on 1.9.2.

% ./ruby -v -e '
Node = Struct.new(:item, :neighbors)
node1 = Node.new(1, [])
node2 = Node.new(1, [node1])
node1.neighbors << node2
p node1.eql?(node2)
'
ruby 1.9.2dev (2009-08-05 trunk 24405) [i686-linux]
true

> This function worked on 1.8.7 and 1.9.1p243, but not on trunk.

node1.eql?(node2) should be false for DFS.
The program works because it is false on 1.8.7 and 1.9.1.

The program doesn't work reliably on 1.9.2 because eql? is
changed it to return true.  You can notice it with the
exception.

You can use Hash#compare_by_identity to accomplish it on 1.9.

% ./ruby -ve '
Node = Struct.new(:item, :neighbors)
node1 = Node.new(1, [])
node2 = Node.new(1, [node1])
node1.neighbors << node2

def dfs(node, visited = {}, &block)
  return if visited[node]
  yield(node)
  visited[node] = true
  node.neighbors.each {|n| dfs(n, visited, &block) }
end

visited = {}
visited.compare_by_identity

dfs(node1, visited) {|n| p n.item }
'
ruby 1.9.2dev (2009-07-28 trunk 24300) [i686-linux]
1
1

> If hash of recursive structure were a constant, this function
> would work.  Collisions, however, would be terribly frequent.

With Hash#compare_by_identity, DFS works well without
terrible performace problem.

If hashes of node1 and node2 is constant, it doesn't work as
follows.

% ./ruby -ve '
Node = Struct.new(:item, :neighbors)
node1 = Node.new(1, [])
node2 = Node.new(1, [node1])
node1.neighbors << node2

def node1.hash() 0 end
def node2.hash() 0 end

def dfs(node, visited = {}, &block)
  return if visited[node]
  yield(node)
  visited[node] = true
  node.neighbors.each {|n| dfs(n, visited, &block) }
end

dfs(node1) {|n| p n.item }
'
ruby 1.9.2dev (2009-08-05 trunk 24405) [i686-linux]
1

> I wonder that it might be intrinsically unreasonable to use
> primitive data types for such a purpose.

Hash can be used, with compare_by_identity.
-- 
Tanaka Akira