Copyright	Patrick Bahr 2010
License	BSD-3-Clause
Maintainer	Patrick Bahr, Andreas Abel
Stability	stable
Portability	non-portable (MPTC with FD)
Safe Haskell	None
Language	Haskell2010

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, Applicative 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
- values :: m [v]
- classes :: m [c]
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, Applicative m) => (v -> c) -> (c -> c -> c) -> (forall s. EquivT s c v m a) -> m a
runEquivT' :: (Monad m, Applicative 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, Applicative 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

Nothing

Methods

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

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

default equivalent :: (MonadEquiv c v d n, MonadTrans t, t n ~ m) => v -> v -> m Bool Source #

classDesc :: v -> m d Source #

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

default classDesc :: (MonadEquiv c v d n, MonadTrans t, t n ~ m) => v -> m d Source #

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.

default equateAll :: (MonadEquiv c v d n, MonadTrans t, t n ~ m) => [v] -> m () Source #

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.

default removeClass :: (MonadEquiv c v d n, MonadTrans t, t n ~ m) => v -> m Bool Source #

getClass :: v -> m c Source #

This function provides the equivalence class of the given element.

default getClass :: (MonadEquiv c v d n, MonadTrans t, t n ~ m) => v -> m c Source #

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!

default combineAll :: (MonadEquiv c v d n, MonadTrans t, t n ~ m) => [c] -> m () Source #

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.

default (===) :: (MonadEquiv c v d n, MonadTrans t, t n ~ m) => c -> c -> m Bool Source #

desc :: c -> m d Source #

This function returns the descriptor of the given equivalence class.

default desc :: (MonadEquiv c v d n, MonadTrans t, t n ~ m) => c -> m d Source #

remove :: c -> m Bool Source #

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

default remove :: (MonadEquiv c v d n, MonadTrans t, t n ~ m) => c -> m Bool Source #

values :: m [v] Source #

This function returns all values represented by some equivalence class.

Since: 0.4.1

default values :: (MonadEquiv c v d n, MonadTrans t, t n ~ m) => m [v] Source #

classes :: m [c] Source #

This function returns the list of all equivalence classes.

Since: 0.4.1

default classes :: (MonadEquiv c v d n, MonadTrans t, t n ~ m) => m [c] Source #

Instances

Instances details

MonadEquiv c v d m => MonadEquiv c v d (ReaderT r m) Source #
Instance details Defined in Data.Equivalence.Monad Methods equivalent :: v -> v -> ReaderT r m Bool Source # classDesc :: v -> ReaderT r m d Source # equateAll :: [v] -> ReaderT r m () Source # equate :: v -> v -> ReaderT r m () Source # removeClass :: v -> ReaderT r m Bool Source # getClass :: v -> ReaderT r m c Source # combineAll :: [c] -> ReaderT r m () Source # combine :: c -> c -> ReaderT r m c Source # (===) :: c -> c -> ReaderT r m Bool Source # desc :: c -> ReaderT r m d Source # remove :: c -> ReaderT r m Bool Source # values :: ReaderT r m [v] Source # classes :: ReaderT r m [c] Source #
MonadEquiv c v d m => MonadEquiv c v d (StateT s m) Source #
Instance details Defined in Data.Equivalence.Monad Methods equivalent :: v -> v -> StateT s m Bool Source # classDesc :: v -> StateT s m d Source # equateAll :: [v] -> StateT s m () Source # equate :: v -> v -> StateT s m () Source # removeClass :: v -> StateT s m Bool Source # getClass :: v -> StateT s m c Source # combineAll :: [c] -> StateT s m () Source # combine :: c -> c -> StateT s m c Source # (===) :: c -> c -> StateT s m Bool Source # desc :: c -> StateT s m d Source # remove :: c -> StateT s m Bool Source # values :: StateT s m [v] Source # classes :: StateT s m [c] Source #
MonadEquiv c v d m => MonadEquiv c v d (ExceptT e m) Source #
Instance details Defined in Data.Equivalence.Monad Methods equivalent :: v -> v -> ExceptT e m Bool Source # classDesc :: v -> ExceptT e m d Source # equateAll :: [v] -> ExceptT e m () Source # equate :: v -> v -> ExceptT e m () Source # removeClass :: v -> ExceptT e m Bool Source # getClass :: v -> ExceptT e m c Source # combineAll :: [c] -> ExceptT e m () Source # combine :: c -> c -> ExceptT e m c Source # (===) :: c -> c -> ExceptT e m Bool Source # desc :: c -> ExceptT e m d Source # remove :: c -> ExceptT e m Bool Source # values :: ExceptT e m [v] Source # classes :: ExceptT e m [c] Source #
(MonadEquiv c v d m, Monoid w) => MonadEquiv c v d (WriterT w m) Source #
Instance details Defined in Data.Equivalence.Monad Methods equivalent :: v -> v -> WriterT w m Bool Source # classDesc :: v -> WriterT w m d Source # equateAll :: [v] -> WriterT w m () Source # equate :: v -> v -> WriterT w m () Source # removeClass :: v -> WriterT w m Bool Source # getClass :: v -> WriterT w m c Source # combineAll :: [c] -> WriterT w m () Source # combine :: c -> c -> WriterT w m c Source # (===) :: c -> c -> WriterT w m Bool Source # desc :: c -> WriterT w m d Source # remove :: c -> WriterT w m Bool Source # values :: WriterT w m [v] Source # classes :: WriterT w m [c] Source #
(Monad m, Applicative m, Ord v) => MonadEquiv (Class s d v) v d (EquivT s d v m) Source #
Instance details Defined in Data.Equivalence.Monad Methods equivalent :: v -> v -> EquivT s d v m Bool Source # classDesc :: v -> EquivT s d v m d Source # equateAll :: [v] -> EquivT s d v m () Source # equate :: v -> v -> EquivT s d v m () Source # removeClass :: v -> EquivT s d v m Bool Source # getClass :: v -> EquivT s d v m (Class s d v) Source # combineAll :: [Class s d v] -> EquivT s d v m () Source # combine :: Class s d v -> Class s d v -> EquivT s d v m (Class s d v) Source # (===) :: Class s d v -> Class s d v -> EquivT s d v m Bool Source # desc :: Class s d v -> EquivT s d v m d Source # remove :: Class s d v -> EquivT s d v m Bool Source # values :: EquivT s d v m [v] Source # classes :: EquivT s d v m [Class s d v] 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

Instances details

MonadWriter w m => MonadWriter w (EquivT s c v m) Source #
Instance details Defined in Data.Equivalence.Monad Methods writer :: (a, w) -> EquivT s c v m a Source # tell :: w -> EquivT s c v m () Source # listen :: EquivT s c v m a -> EquivT s c v m (a, w) Source # pass :: EquivT s c v m (a, w -> w) -> EquivT s c v m a Source #
MonadState st m => MonadState st (EquivT s c v m) Source #
Instance details Defined in Data.Equivalence.Monad Methods get :: EquivT s c v m st Source # put :: st -> EquivT s c v m () Source # state :: (st -> (a, st)) -> EquivT s c v m a Source #
MonadReader r m => MonadReader r (EquivT s c v m) Source #
Instance details Defined in Data.Equivalence.Monad Methods ask :: EquivT s c v m r Source # local :: (r -> r) -> EquivT s c v m a -> EquivT s c v m a Source # reader :: (r -> a) -> EquivT s c v m a Source #
MonadError e m => MonadError e (EquivT s c v m) Source #
Instance details Defined in Data.Equivalence.Monad Methods throwError :: e -> EquivT s c v m a Source # catchError :: EquivT s c v m a -> (e -> EquivT s c v m a) -> EquivT s c v m a Source #
MonadTrans (EquivT s c v) Source #
Instance details Defined in Data.Equivalence.Monad Methods lift :: Monad m => m a -> EquivT s c v m a Source #
(Monad m, Applicative m, Ord v) => MonadEquiv (Class s d v) v d (EquivT s d v m) Source #
Instance details Defined in Data.Equivalence.Monad Methods equivalent :: v -> v -> EquivT s d v m Bool Source # classDesc :: v -> EquivT s d v m d Source # equateAll :: [v] -> EquivT s d v m () Source # equate :: v -> v -> EquivT s d v m () Source # removeClass :: v -> EquivT s d v m Bool Source # getClass :: v -> EquivT s d v m (Class s d v) Source # combineAll :: [Class s d v] -> EquivT s d v m () Source # combine :: Class s d v -> Class s d v -> EquivT s d v m (Class s d v) Source # (===) :: Class s d v -> Class s d v -> EquivT s d v m Bool Source # desc :: Class s d v -> EquivT s d v m d Source # remove :: Class s d v -> EquivT s d v m Bool Source # values :: EquivT s d v m [v] Source # classes :: EquivT s d v m [Class s d v] Source #
Monad m => Monad (EquivT s c v m) Source #
Instance details Defined in Data.Equivalence.Monad Methods (>>=) :: EquivT s c v m a -> (a -> EquivT s c v m b) -> EquivT s c v m b Source # (>>) :: EquivT s c v m a -> EquivT s c v m b -> EquivT s c v m b Source # return :: a -> EquivT s c v m a Source #
Functor m => Functor (EquivT s c v m) Source #
Instance details Defined in Data.Equivalence.Monad Methods fmap :: (a -> b) -> EquivT s c v m a -> EquivT s c v m b Source # (<$) :: a -> EquivT s c v m b -> EquivT s c v m a Source #
Monad m => MonadFail (EquivT s c v m) Source #
Instance details Defined in Data.Equivalence.Monad Methods fail :: String -> EquivT s c v m a Source #
Monad m => Applicative (EquivT s c v m) Source #
Instance details Defined in Data.Equivalence.Monad Methods pure :: a -> EquivT s c v m a Source # (<>) :: EquivT s c v m (a -> b) -> EquivT s c v m a -> EquivT s c v m b Source # liftA2 :: (a -> b -> c0) -> EquivT s c v m a -> EquivT s c v m b -> EquivT s c v m c0 Source # (>) :: EquivT s c v m a -> EquivT s c v m b -> EquivT s c v m b Source # (<*) :: EquivT s c v m a -> EquivT s c v m b -> EquivT s c v m a 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, Applicative 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 two arguments specify how to construct an equivalence class descriptor for a singleton class and how to combine two equivalence class descriptors.

runEquivT' :: (Monad m, Applicative 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 ().