Re: [Haskell-cafe] How to give unique name/id to nodes outside any monad ?

2009/1/8 Luke Palmer :

On Thu, Jan 8, 2009 at 1:28 AM, minh thu wrote:

...

Hi,

I'd like to process some kind of graph data structure, say something like

data DS = A [DS] | B DS DS | C.

but I want to be able to discover any sharing. Thus, in

b = B a a where a = A [C],

if I want to malloc a similar data structure, I have to handle to the node representing B two times the same pointer (the one returned after allocating A [C]).

To discover sharing, I thought it would be necessary to give unique name to node and then compare them while traversing the graph. I could give the name by hand but it would be cumbersome. But at least it would not require any monad for the bookkeeping of ungiven names. Is it possible to give those names automatically but outside any monad ?

If your graphs are acyclic, then you can label each node with a hash and use that for comparison. This usually works very well in practice.

Precisely ! How do you give that label to each node; i.e. how to ensure they are unique ? I don't want to end up with do c <- newNodeC a <- newNodeA [c] b <- newNodeB a a where newNodeX hides the handling of label. I'd like to simply write, like above, b = B a a where a = A [C] or, maybe, b = B label a a where a = A label [C] The question is : how can label be different each time ? Thanks, Thu