equivalence-0.3.1: Maintaining an equivalence relation implemented as union-find using STT.

Copyright | Patrick Bahr, 2010
License | All Rights Reserved
Maintainer | Patrick Bahr
Stability | unknown
Portability | unknown
Safe Haskell | None
Language | Haskell98

Data.Equivalence.Monad

Description

This is an alternative interface to the union-find implementation in '`STT'`. It is wrapped into the monad transformer `EquivT`.

Synopsis

- class (Monad m, Ord v) => MonadEquiv c v d m | m -> v, m -> c, m -> d where
  - equivalent :: v -> v -> m Bool
  - classDesc :: v -> m d
  - equateAll :: [v] -> m ()
  - equate :: v -> v -> m ()
  - removeClass :: v -> m Bool
  - getClass :: v -> m c
  - combineAll :: [c] -> m ()
  - combine :: c -> c -> m c
  - (===) :: c -> c -> m Bool
  - desc :: c -> m d
  - remove :: c -> m Bool
- newtype EquivT s c v m a = EquivT {
  - unEquivT :: ReaderT (Equiv s c v) (STT s m) a
  }
- type EquivT' s = EquivT s ()
- type EquivM s c v = EquivT s c v Identity
- type EquivM' s v = EquivM s () v
- runEquivT :: Monad m => (v -> c) -> (c -> c -> c) -> (forall s. EquivT s c v m a) -> m a
- runEquivT' :: Monad m => (forall s. EquivT' s v m a) -> m a
- runEquivM :: (v -> c) -> (c -> c -> c) -> (forall s. EquivM s c v a) -> a
- runEquivM' :: (forall s. EquivM' s v a) -> a

# Documentation

class (Monad m, Ord v) => MonadEquiv c v d m | m -> v, m -> c, m -> d where Source

This class specifies the interface for a monadic computation that maintains an equivalence relation.

Minimal complete definition

equivalent, classDesc, equateAll, removeClass, getClass, combineAll, (===), desc, remove

Methods

equivalent :: v -> v -> m Bool Source

This function decides whether the two given elements are equivalent in the current equivalence relation

classDesc :: v -> m d Source

This function obtains the descriptor of the given element's equivalence class.

equateAll :: [v] -> m () Source

This function equates the element in the given list. That is, it unions the equivalence classes of the elements and combines their descriptor.

equate :: v -> v -> m () Source

This function equates the given two elements. That is it unions the equivalence classes of the two elements.

removeClass :: v -> m Bool Source

This function removes the equivalence class of the given element. If there is no corresponding equivalence class, `False` is returned; otherwise `True`.

getClass :: v -> m c Source

This function provides the equivalence class the given element is contained in.

combineAll :: [c] -> m () Source

This function combines all equivalence classes in the given list. Afterwards all elements in the argument list represent the same equivalence class!

combine :: c -> c -> m c Source

This function combines the two given equivalence classes. Afterwards both arguments represent the same equivalence class! One of it is returned in order to represent the new combined equivalence class.

(===) :: c -> c -> m Bool Source

This function decides whether the two given equivalence classes are the same.

desc :: c -> m d Source

This function returns the descriptor of the given equivalence class.

remove :: c -> m Bool Source

This function removes the given equivalence class. If the equivalence class does not exists anymore `False` is returned; otherwise `True`.

Instances

MonadEquiv c v d m => MonadEquiv c v d (ReaderT r m) Source |
MonadEquiv c v d m => MonadEquiv c v d (StateT s m) Source |
MonadEquiv c v d m => MonadEquiv c v d (ExceptT e m) Source |
(MonadEquiv c v d m, Error e) => MonadEquiv c v d (ErrorT e m) Source |
(MonadEquiv c v d m, Monoid w) => MonadEquiv c v d (WriterT w m) Source |
(Monad m, Ord v) => MonadEquiv (Class s d v) v d (EquivT s d v m) Source |

newtype EquivT s c v m a Source

This monad transformer encapsulates computations maintaining an equivalence relation. A monadic computation of type `EquivT` `s c v m a` maintains a state space indexed by type `s`, maintains an equivalence relation over elements of type `v` with equivalence class descriptors of type `c` and contains an internal monadic computation of type `m a`.

Constructors

EquivT |

Fields

unEquivT :: ReaderT (Equiv s c v) (STT s m) a

Instances

MonadError e m => MonadError e (EquivT s c v m) Source |
MonadReader r m => MonadReader r (EquivT s c v m) Source |
MonadState st m => MonadState st (EquivT s c v m) Source |
(Monoid w, MonadWriter w m) => MonadWriter w (EquivT s c v m) Source |
MonadTrans (EquivT s c v) Source |
(Monad m, Ord v) => MonadEquiv (Class s d v) v d (EquivT s d v m) Source |
Monad m => Monad (EquivT s c v m) Source |
Functor m => Functor (EquivT s c v m) Source |
(Functor m, Monad m) => Applicative (EquivT s c v m) Source |

type EquivT' s = EquivT s () Source

This monad transformer is a special case of `EquivT` that only maintains trivial equivalence class descriptors of type `()`.

type EquivM s c v = EquivT s c v Identity Source

This monad encapsulates computations maintaining an equivalence relation. A monadic computation of type `EquivM` `s c v a` maintains a state space indexed by type `s`, maintains an equivalence relation over elements of type `v` with equivalence class descriptors of type `c` and returns a value of type `a`.

type EquivM' s v = EquivM s () v Source

This monad is a special case of `EquivM` that only maintains trivial equivalence class descriptors of type `()`.

runEquivT Source

Arguments

:: Monad m |
=> (v -> c) | used to construct an equivalence class descriptor for a singleton class
-> (c -> c -> c) | used to combine the equivalence class descriptor of two classes which are meant to be combined.
-> (forall s. EquivT s c v m a) |
-> m a |

This function runs a monadic computation that maintains an equivalence relation. The first tow arguments specify how to construct an equivalence class descriptor for a singleton class and how to combine two equivalence class descriptors.

runEquivT' :: Monad m => (forall s. EquivT' s v m a) -> m a Source

This function is a special case of `runEquivT` that only maintains trivial equivalence class descriptors of type `()`.

runEquivM Source

Arguments

:: (v -> c) | used to construct an equivalence class descriptor for a singleton class
-> (c -> c -> c) | used to combine the equivalence class descriptor of two classes which are meant to be combined.
-> (forall s. EquivM s c v a) |
-> a |

This function runs a monadic computation that maintains an equivalence relation. The first tow arguments specify how to construct an equivalence class descriptor for a singleton class and how to combine two equivalence class descriptors.

runEquivM' :: (forall s. EquivM' s v a) -> a Source

This function is a special case of `runEquivM` that only maintains trivial equivalence class descriptors of type `()`.