| Safe Haskell | None |
|---|---|
| Language | Haskell98 |
Control.Monad.Trans.UnionFind
Synopsis
- 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
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)