-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Maintaining an equivalence relation implemented as union-find using STT.
--   
--   This is an implementation of Tarjan's Union-Find algorithm (Robert E.
--   Tarjan. "Efficiency of a Good But Not Linear Set Union Algorithm",
--   JACM 22(2), 1975) in order to maintain an equivalence relation. This
--   implementation is a port of the <i>union-find</i> package using the ST
--   monad transformer (instead of the IO monad).
@package equivalence
@version 0.2.5


-- | This is an implementation of Tarjan's Union-Find algorithm (Robert E.
--   Tarjan. "Efficiency of a Good But Not Linear Set Union Algorithm",
--   JACM 22(2), 1975) in order to maintain an equivalence relation.
--   
--   This implementation is a port of the <i>union-find</i> package using
--   the ST monad transformer (instead of the IO monad).
--   
--   The implementation is based on mutable references. Each equivalence
--   class has exactly one member that serves as its representative
--   element. Every element either is the representative element of its
--   equivalence class or points to another element in the same equivalence
--   class. Equivalence testing thus consists of following the pointers to
--   the representative elements and then comparing these for identity.
--   
--   The algorithm performs lazy path compression. That is, whenever we
--   walk along a path greater than length 1 we automatically update the
--   pointers along the path to directly point to the representative
--   element. Consequently future lookups will be have a path length of at
--   most 1.
--   
--   Each equivalence class remains a descriptor, i.e. some piece of data
--   attached to an equivalence class which is combined when two classes
--   are unioned.
module Data.Equivalence.STT

-- | This is the top-level data structure that represents an equivalence
--   relation. An equivalence relation of type <a>Equiv</a> <tt>s c a</tt>
--   lives in the state space indexed by <tt>s</tt>, contains equivalence
--   class descriptors of type <tt>c</tt> and has elements of type
--   <tt>a</tt>.
data Equiv s c a
data Class s c a

-- | This function constructs the initial data structure for maintaining an
--   equivalence relation. That is it represents, the fines (or least)
--   equivalence class (of the set of all elements of type <tt>a</tt>). The
--   arguments are used to maintain equivalence class descriptors.
leastEquiv :: Monad m => (a -> c) -> (c -> c -> c) -> STT s m (Equiv s c a)

-- | This function provides the equivalence class the given element is
--   contained in.
getClass :: (Monad m, Ord a) => Equiv s c a -> a -> STT s m (Class s c a)

-- | 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.
combine :: (Monad m, Ord a) => Equiv s c a -> Class s c a -> Class s c a -> STT s m (Class s c a)

-- | This function combines all equivalence classes in the given list.
--   Afterwards all elements in the argument list represent the same
--   equivalence class!
combineAll :: (Monad m, Ord a) => Equiv s c a -> [Class s c a] -> STT s m ()

-- | This function decides whether the two given equivalence classes are
--   the same.
same :: (Monad m, Ord a) => Equiv s c a -> Class s c a -> Class s c a -> STT s m Bool

-- | This function returns the descriptor of the given equivalence class.
desc :: (Monad m, Ord a) => Equiv s c a -> Class s c a -> STT s m c

-- | This function removes the given equivalence class. If the equivalence
--   class does not exists anymore <tt>False</tt> is returned; otherwise
--   <tt>True</tt>.
remove :: (Monad m, Ord a) => Equiv s c a -> Class s c a -> STT s m Bool

-- | This function equates the two given elements. That is, it unions the
--   equivalence classes of the two elements and combines their descriptor.
equate :: (Monad m, Ord a) => Equiv s c a -> a -> a -> STT s m ()

-- | This function equates the element in the given list. That is, it
--   unions the equivalence classes of the elements and combines their
--   descriptor.
equateAll :: (Monad m, Ord a) => Equiv s c a -> [a] -> STT s m ()

-- | This function decides whether the two given elements are in the same
--   equivalence class according to the given equivalence relation
--   representation.
equivalent :: (Monad m, Ord a) => Equiv s c a -> a -> a -> STT s m Bool

-- | This function returns the descriptor of the given element's
--   equivalence class.
classDesc :: (Monad m, Ord a) => Equiv s c a -> a -> STT s m c

-- | This function removes the equivalence class of the given element. If
--   there is no corresponding equivalence class, <tt>False</tt> is
--   returned; otherwise <tt>True</tt>.
removeClass :: (Monad m, Ord a) => Equiv s c a -> a -> STT s m Bool


-- | This is an alternative interface to the union-find implementation in
--   ''Data.Equivalence.STT''. It is wrapped into the monad transformer
--   <a>EquivT</a>.
module Data.Equivalence.Monad

-- | This class specifies the interface for a monadic computation that
--   maintains an equivalence relation.
class (Monad m, Ord v) => MonadEquiv c v d m | m -> v, m -> c, m -> d where equate x y = equateAll [x, y] combine x y = combineAll [x, y] >> return x
equivalent :: MonadEquiv c v d m => v -> v -> m Bool
classDesc :: MonadEquiv c v d m => v -> m d
equateAll :: MonadEquiv c v d m => [v] -> m ()
equate :: MonadEquiv c v d m => v -> v -> m ()
removeClass :: MonadEquiv c v d m => v -> m Bool
getClass :: MonadEquiv c v d m => v -> m c
combineAll :: MonadEquiv c v d m => [c] -> m ()
combine :: MonadEquiv c v d m => c -> c -> m c
(===) :: MonadEquiv c v d m => c -> c -> m Bool
desc :: MonadEquiv c v d m => c -> m d
remove :: MonadEquiv c v d m => c -> m Bool

-- | This monad transformer encapsulates computations maintaining an
--   equivalence relation. A monadic computation of type <a>EquivT</a>
--   <tt>s c v m a</tt> maintains a state space indexed by type <tt>s</tt>,
--   maintains an equivalence relation over elements of type <tt>v</tt>
--   with equivalence class descriptors of type <tt>c</tt> and contains an
--   internal monadic computation of type <tt>m a</tt>.
newtype EquivT s c v m a
EquivT :: ReaderT (Equiv s c v) (STT s m) a -> EquivT s c v m a
unEquivT :: EquivT s c v m a -> ReaderT (Equiv s c v) (STT s m) a

-- | This monad transformer is a special case of <a>EquivT</a> that only
--   maintains trivial equivalence class descriptors of type <tt>()</tt>.
type EquivT' s = EquivT s ()

-- | This monad encapsulates computations maintaining an equivalence
--   relation. A monadic computation of type <a>EquivM</a> <tt>s c v a</tt>
--   maintains a state space indexed by type <tt>s</tt>, maintains an
--   equivalence relation over elements of type <tt>v</tt> with equivalence
--   class descriptors of type <tt>c</tt> and returns a value of type
--   <tt>a</tt>.
type EquivM s c v = EquivT s c v Identity

-- | This monad is a special case of <a>EquivM</a> that only maintains
--   trivial equivalence class descriptors of type <tt>()</tt>.
type EquivM' s v = EquivM s () v

-- | 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 => (v -> c) -> (c -> c -> c) -> (forall s. EquivT s c v m a) -> m a

-- | This function is a special case of <a>runEquivT</a> that only
--   maintains trivial equivalence class descriptors of type <tt>()</tt>.
runEquivT' :: Monad m => (forall s. EquivT' s 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.
runEquivM :: (v -> c) -> (c -> c -> c) -> (forall s. EquivM s c v a) -> a

-- | This function is a special case of <a>runEquivM</a> that only
--   maintains trivial equivalence class descriptors of type <tt>()</tt>.
runEquivM' :: (forall s. EquivM' s v a) -> a
instance MonadEquiv c v d m => MonadEquiv c v d (ReaderT r m)
instance MonadEquiv c v d m => MonadEquiv c v d (StateT s m)
instance (MonadEquiv c v d m, Error e) => MonadEquiv c v d (ErrorT e m)
instance (MonadEquiv c v d m, Monoid w) => MonadEquiv c v d (WriterT w m)
instance (Monad m, Ord v) => MonadEquiv (Class s d v) v d (EquivT s d v m)
instance MonadError e m => MonadError e (EquivT s c v m)
instance MonadState st m => MonadState st (EquivT s c v m)
instance (Monoid w, MonadWriter w m) => MonadWriter w (EquivT s c v m)
instance MonadReader r m => MonadReader r (EquivT s c v m)
instance MonadTrans (EquivT s c v)
instance Monad m => Monad (EquivT s c v m)
instance (Functor m, Monad m) => Applicative (EquivT s c v m)
instance Functor m => Functor (EquivT s c v m)
