Control.Monad.Trans.UnionFind

Documentation

data UnionFindT p m a

A monad transformer that adds union find operations.

The p parameter is the type of points. Uses the Data.UnionFind.IntMap as the underlying union-find implementation.

Instances

MonadTrans (UnionFindT p)

Monad m => Monad (UnionFindT p m)

Functor m => Functor (UnionFindT p m)

(Monad m, Functor m) => Applicative (UnionFindT p m)

runUnionFind :: Monad m => UnionFindT p m a -> m a

data Point a

fresh :: Monad m => p -> UnionFindT p m (Point p)

Create a new point with the given descriptor. The returned is only equivalent to itself.

Note that a Point has its own identity. That is, if two points are equivalent then their descriptors are equal, but not vice versa.

repr :: Monad m => Point p -> UnionFindT p m (Point p)

O(1). repr point returns the representative point of point's equivalence class.

descriptor :: Monad m => Point p -> UnionFindT p m p

Return the descriptor of the

union :: Monad m => Point p -> Point p -> UnionFindT p m ()

Join the equivalence classes of the points. The resulting equivalence class will get the descriptor of the second argument.

equivalent :: Monad m => Point p -> Point p -> UnionFindT p m Bool

Test if the two elements are in the same equivalence class.

 liftA2 (==) (repr x) (repr y)