| 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
| MonadTrans (UnionFindT p) Source # | |
Defined in Control.Monad.Trans.UnionFind Methods lift :: Monad m => m a -> UnionFindT p m a | |
| Monad m => Monad (UnionFindT p m) Source # | |
Defined in Control.Monad.Trans.UnionFind 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 | |
| Functor m => Functor (UnionFindT p m) Source # | |
Defined in Control.Monad.Trans.UnionFind 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 # | |
Defined in Control.Monad.Trans.UnionFind 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 #
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)