| Safe Haskell | None |
|---|---|
| Language | Haskell98 |
Control.Monad.Trans.UnionFind
- data UnionFindT p m a
- runUnionFind :: Monad m => UnionFindT p m a -> m a
- data Point a
- fresh :: Monad m => p -> UnionFindT p m (Point p)
- repr :: Monad m => Point p -> UnionFindT p m (Point p)
- descriptor :: Monad m => Point p -> UnionFindT p m p
- union :: Monad m => Point p -> Point p -> UnionFindT p m ()
- equivalent :: Monad m => Point p -> Point p -> UnionFindT p m Bool
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) | |
| 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 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)