Safe Haskell	None
Language	Haskell2010

Control.Monad.Union

Description

Monadic interface for creating a disjoint set data structure.

Synopsis

data UnionM l a
data Union a = Union {
- size :: !Int
- up :: UArray Int Int
- label :: Array Int a
}
class Monad m => MonadUnion l m | m -> l where
- new :: l -> m Node
- lookup :: Node -> m (Node, l)
- merge :: (l -> l -> (l, a)) -> Node -> Node -> m (Maybe a)
- annotate :: Node -> l -> m ()
- flatten :: m ()
data Node
run :: UnionM l a -> a
run' :: UnionM l a -> (Union l, a)

Documentation

data UnionM l a Source #

Union find monad.

Instances

Instances details

MonadUnion l (UnionM l) Source #
Instance details Defined in Control.Monad.Union Methods new :: l -> UnionM l Node Source # lookup :: Node -> UnionM l (Node, l) Source # merge :: (l -> l -> (l, a)) -> Node -> Node -> UnionM l (Maybe a) Source # annotate :: Node -> l -> UnionM l () Source # flatten :: UnionM l () Source #
Monad (UnionM l) Source #
Instance details Defined in Control.Monad.Union Methods (>>=) :: UnionM l a -> (a -> UnionM l b) -> UnionM l b # (>>) :: UnionM l a -> UnionM l b -> UnionM l b # return :: a -> UnionM l a #
Functor (UnionM l) Source #
Instance details Defined in Control.Monad.Union Methods fmap :: (a -> b) -> UnionM l a -> UnionM l b # (<$) :: a -> UnionM l b -> UnionM l a #
MonadFix (UnionM l) Source #
Instance details Defined in Control.Monad.Union Methods mfix :: (a -> UnionM l a) -> UnionM l a #
Applicative (UnionM l) Source #
Instance details Defined in Control.Monad.Union Methods pure :: a -> UnionM l a # (<>) :: UnionM l (a -> b) -> UnionM l a -> UnionM l b # liftA2 :: (a -> b -> c) -> UnionM l a -> UnionM l b -> UnionM l c # (>) :: UnionM l a -> UnionM l b -> UnionM l b # (<*) :: UnionM l a -> UnionM l b -> UnionM l a #

data Union a Source #

An immutable disjoint set forest.

Constructors

Union
Fields size :: !Int up :: UArray Int Int label :: Array Int a

class Monad m => MonadUnion l m | m -> l where Source #

Methods

new :: l -> m Node Source #

Add a new node, with a given label.

lookup :: Node -> m (Node, l) Source #

Find the node representing a given node, and its label.

merge :: (l -> l -> (l, a)) -> Node -> Node -> m (Maybe a) Source #

Merge two sets. The first argument is a function that takes the labels of the corresponding sets' representatives and computes a new label for the joined set. Returns Nothing if the given nodes are in the same set already.

annotate :: Node -> l -> m () Source #

Re-label a node.

flatten :: m () Source #

Flatten the disjoint set forest for faster lookups.

Instances

Instances details

(MonadUnion l m, MonadTrans t, Monad (t m)) => MonadUnion l (t m) Source #
Instance details Defined in Control.Monad.Union.Class Methods new :: l -> t m Node Source # lookup :: Node -> t m (Node, l) Source # merge :: (l -> l -> (l, a)) -> Node -> Node -> t m (Maybe a) Source # annotate :: Node -> l -> t m () Source # flatten :: t m () Source #
MonadUnion l (UnionM l) Source #
Instance details Defined in Control.Monad.Union Methods new :: l -> UnionM l Node Source # lookup :: Node -> UnionM l (Node, l) Source # merge :: (l -> l -> (l, a)) -> Node -> Node -> UnionM l (Maybe a) Source # annotate :: Node -> l -> UnionM l () Source # flatten :: UnionM l () Source #

data Node Source #

A node in a disjoint set forest.

Instances

Instances details

Eq Node Source #
Instance details Defined in Data.Union.Type Methods (==) :: Node -> Node -> Bool # (/=) :: Node -> Node -> Bool #
Ord Node Source #
Instance details Defined in Data.Union.Type Methods compare :: Node -> Node -> Ordering # (<) :: Node -> Node -> Bool # (<=) :: Node -> Node -> Bool # (>) :: Node -> Node -> Bool # (>=) :: Node -> Node -> Bool # max :: Node -> Node -> Node # min :: Node -> Node -> Node #
Ix Node Source #
Instance details Defined in Data.Union.Type Methods range :: (Node, Node) -> [Node] # index :: (Node, Node) -> Node -> Int # unsafeIndex :: (Node, Node) -> Node -> Int # inRange :: (Node, Node) -> Node -> Bool # rangeSize :: (Node, Node) -> Int # unsafeRangeSize :: (Node, Node) -> Int #

run :: UnionM l a -> a Source #

Run a union find computation.

run' :: UnionM l a -> (Union l, a) Source #

Run a union find computation; also return the final disjoint set forest for querying.