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

minh thu noteed at gmail.com
Thu Jan 8 03:49:04 EST 2009

2009/1/8 Luke Palmer <lrpalmer at gmail.com>:
> 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.

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

  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 ?


More information about the Haskell-Cafe mailing list