On Mon, 16 Aug 1999, Keith Wansbrough wrote:
> Hi all... has anyone implemented the Union-Find algorithm in Haskell?
> I've looked at the various libraries listed at haskell.org and found
> nothing, but don't want to re-invent the wheel if someone else has done
> it already.
>
Yes I have. I used the ST monad.
Nothing fancy though, but it would be almost trivial to add
pathcompression and union by height. (I havn't done it because it was
not compatible with other operations I wanted).
A problem may be that the ADT I created contains a lot of stuff you would
not be interestd in. For example, I use a dynamic array to be able to add
elements to the disjoint set, and implement a function taking
two disjoint sets and calculating the intersection. (I used it to maintain
an equivalence relation between subformulas to
implement an extension of Stålmarck's proof procedure to many sorted first
order logic in haskell. http://www.dtek.chalmers.se/~d95lars/rapport.ps.
[Please don't look to much at the source code, it should really be
cleaned up])
If you are interested I can isolate the disjoint set things and give the
code to you.
/Lars L
