Safe Haskell | None |
---|

- 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.

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 aSource

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 pSource

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 BoolSource

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

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