[Haskell-cafe] How to give unique name/id to nodes outside any
lrpalmer at gmail.com
Thu Jan 8 03:40:57 EST 2009
On Thu, Jan 8, 2009 at 1:28 AM, minh thu <noteed at gmail.com> wrote:
> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe