Control.Monad.Union

Monadic interface for creating a disjoint set data structure.

Documentation

data UnionM l a

Union find monad.

Instances

MonadUnion l (UnionM l)

Defined in Control.Monad.Union

Methods

new :: l -> UnionM l Node

lookup :: Node -> UnionM l (Node, l)

merge :: (l -> l -> (l, a)) -> Node -> Node -> UnionM l (Maybe a)

annotate :: Node -> l -> UnionM l ()

flatten :: UnionM l ()

MonadFix (UnionM l)

Defined in Control.Monad.Union

Methods

mfix :: (a -> UnionM l a) -> UnionM l a

Applicative (UnionM l)

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

Functor (UnionM l)

Defined in Control.Monad.Union

Methods

fmap :: (a -> b) -> UnionM l a -> UnionM l b

(<$) :: a -> UnionM l b -> UnionM l a

Monad (UnionM l)

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

data Union a

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

Methods

new :: l -> m Node

Add a new node, with a given label.

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

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

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

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

Re-label a node.

flatten :: m ()

Flatten the disjoint set forest for faster lookups.

Instances

MonadUnion l (UnionM l)

Defined in Control.Monad.Union

Methods

new :: l -> UnionM l Node

lookup :: Node -> UnionM l (Node, l)

merge :: (l -> l -> (l, a)) -> Node -> Node -> UnionM l (Maybe a)

annotate :: Node -> l -> UnionM l ()

flatten :: UnionM l ()

(MonadUnion l m, MonadTrans t, Monad (t m)) => MonadUnion l (t m)

Defined in Control.Monad.Union.Class

Methods

new :: l -> t m Node

lookup :: Node -> t m (Node, l)

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

annotate :: Node -> l -> t m ()

flatten :: t m ()

data Node

A node in a disjoint set forest.

Instances

Ix Node

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

Eq Node

Defined in Data.Union.Type

Methods

(==) :: Node -> Node -> Bool

(/=) :: Node -> Node -> Bool

Ord Node

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

run :: UnionM l a -> a

Run a union find computation.

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

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