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

Safe HaskellNone




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.


runUnionFind :: Monad m => UnionFindT p m a -> m aSource

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