union-find-array-0.1: union find data structure

Safe HaskellNone



Monadic interface for creating a disjoint set data structure.



data UnionM l a Source

Union find monad.

data Union a Source

An immutable disjoint set forest.




size :: !Int
up :: UArray Int Int
label :: Array Int a

class Monad m => MonadUnion l m | m -> l whereSource


new :: l -> m NodeSource

Add a new node, with a given label.

lookup :: Node -> m (Node, l)Source

Find the node representing a given node, and its label.

merge :: (l -> l -> (l, a)) -> Node -> Node -> m (Maybe a)Source

Merge two sets. The first argument is a function that takes the labels of the corresponding sets' representatives and computes a new label for the joined set. Returns Nothing if the given nodes are in the same set already.

annotate :: Node -> l -> m ()Source

Re-label a node.

flatten :: m ()Source

Flatten the disjoint set forest for faster lookups.


(MonadUnion l m, MonadTrans t, Monad (t m)) => MonadUnion l (t m) 
MonadUnion l (UnionM l) 

data Node Source

A node in a disjoint set forest.


run :: UnionM l a -> aSource

Run a union find computation.

run' :: UnionM l a -> (Union l, a)Source

Run a union find computation; also return the final disjoint set forest for querying.