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

[Luke Palmer]

On Thu, Jan 8, 2009 at 1:28 AM, minh thu <noteed at gmail.com> 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.

Luke
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090108/f2820cbf/attachment.htm