union-find-0.2: Efficient union and equivalence testing of sets.

Safe HaskellNone
LanguageHaskell98

Control.Monad.Trans.UnionFind

Synopsis

Documentation

data UnionFindT p m a Source #

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) Source # 

Methods

lift :: Monad m => m a -> UnionFindT p m a #

Monad m => Monad (UnionFindT p m) Source # 

Methods

(>>=) :: UnionFindT p m a -> (a -> UnionFindT p m b) -> UnionFindT p m b #

(>>) :: UnionFindT p m a -> UnionFindT p m b -> UnionFindT p m b #

return :: a -> UnionFindT p m a #

fail :: String -> UnionFindT p m a #

Functor m => Functor (UnionFindT p m) Source # 

Methods

fmap :: (a -> b) -> UnionFindT p m a -> UnionFindT p m b #

(<$) :: a -> UnionFindT p m b -> UnionFindT p m a #

Monad m => Applicative (UnionFindT p m) Source # 

Methods

pure :: a -> UnionFindT p m a #

(<*>) :: UnionFindT p m (a -> b) -> UnionFindT p m a -> UnionFindT p m b #

liftA2 :: (a -> b -> c) -> UnionFindT p m a -> UnionFindT p m b -> UnionFindT p m c #

(*>) :: UnionFindT p m a -> UnionFindT p m b -> UnionFindT p m b #

(<*) :: UnionFindT p m a -> UnionFindT p m b -> UnionFindT p m a #

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

data Point a Source #

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

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) Source #

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

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

Return the descriptor of the

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

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 Source #

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

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