-- 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 union-find package using the ST
--   monad transformer (instead of the IO monad).
@package equivalence
@version 0.3.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 union-find 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 Equiv s c a
--   lives in the state space indexed by s, contains equivalence
--   class descriptors of type c and has elements of type
--   a.
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 a). The
--   arguments are used to maintain equivalence class descriptors.
leastEquiv :: (Monad m, Applicative 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, Applicative 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, Applicative 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, Applicative 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, Applicative 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, Applicative 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 False is returned; otherwise
--   True.
remove :: (Monad m, Applicative 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, Applicative 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, Applicative 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, Applicative 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, Applicative 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, False is
--   returned; otherwise True.
removeClass :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s m Bool

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

-- | This class specifies the interface for a monadic computation that
--   maintains an equivalence relation.
class (Monad m, Applicative m, Ord v) => MonadEquiv c v d m | m -> v, m -> c, m -> d

-- | This function decides whether the two given elements are equivalent in
--   the current equivalence relation
equivalent :: MonadEquiv c v d m => v -> v -> m Bool

-- | This function obtains the descriptor of the given element's
--   equivalence class.
classDesc :: MonadEquiv c v d m => v -> m d

-- | This function equates the element in the given list. That is, it
--   unions the equivalence classes of the elements and combines their
--   descriptor.
equateAll :: MonadEquiv c v d m => [v] -> m ()

-- | This function equates the given two elements. That is it unions the
--   equivalence classes of the two elements.
equate :: MonadEquiv c v d m => v -> v -> m ()

-- | This function removes the equivalence class of the given element. If
--   there is no corresponding equivalence class, False is
--   returned; otherwise True.
removeClass :: MonadEquiv c v d m => v -> m Bool

-- | This function provides the equivalence class the given element is
--   contained in.
getClass :: MonadEquiv c v d m => v -> m c

-- | This function combines all equivalence classes in the given list.
--   Afterwards all elements in the argument list represent the same
--   equivalence class!
combineAll :: MonadEquiv c v d m => [c] -> m ()

-- | 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 :: MonadEquiv c v d m => c -> c -> m c

-- | This function decides whether the two given equivalence classes are
--   the same.
(===) :: MonadEquiv c v d m => c -> c -> m Bool

-- | This function returns the descriptor of the given equivalence class.
desc :: MonadEquiv c v d m => c -> m d

-- | This function removes the given equivalence class. If the equivalence
--   class does not exists anymore False is returned; otherwise
--   True.
remove :: MonadEquiv c v d m => c -> m Bool

-- | 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.
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 EquivT that only
--   maintains trivial equivalence class descriptors of type ().
type EquivT' s = EquivT s ()

-- | 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 c v = EquivT s c v Identity

-- | This monad is a special case of EquivM that only maintains
--   trivial equivalence class descriptors of type ().
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, Applicative m) => (v -> c) -> (c -> c -> c) -> (forall s. EquivT s c v m a) -> m a

-- | This function is a special case of runEquivT that only
--   maintains trivial equivalence class descriptors of type ().
runEquivT' :: (Monad m, Applicative 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 runEquivM that only
--   maintains trivial equivalence class descriptors of type ().
runEquivM' :: (forall s. EquivM' s v a) -> a
instance (GHC.Base.Monad m, GHC.Base.Applicative m, GHC.Classes.Ord v) => Data.Equivalence.Monad.MonadEquiv (Data.Equivalence.STT.Class s d v) v d (Data.Equivalence.Monad.EquivT s d v m)
instance (Data.Equivalence.Monad.MonadEquiv c v d m, GHC.Base.Monoid w) => Data.Equivalence.Monad.MonadEquiv c v d (Control.Monad.Trans.Writer.Lazy.WriterT w m)
instance (Data.Equivalence.Monad.MonadEquiv c v d m, Control.Monad.Trans.Error.Error e) => Data.Equivalence.Monad.MonadEquiv c v d (Control.Monad.Trans.Error.ErrorT e m)
instance Data.Equivalence.Monad.MonadEquiv c v d m => Data.Equivalence.Monad.MonadEquiv c v d (Control.Monad.Trans.Except.ExceptT e m)
instance Data.Equivalence.Monad.MonadEquiv c v d m => Data.Equivalence.Monad.MonadEquiv c v d (Control.Monad.Trans.State.Lazy.StateT s m)
instance Data.Equivalence.Monad.MonadEquiv c v d m => Data.Equivalence.Monad.MonadEquiv c v d (Control.Monad.Trans.Reader.ReaderT r m)
instance GHC.Base.Functor m => GHC.Base.Functor (Data.Equivalence.Monad.EquivT s c v m)
instance (GHC.Base.Applicative m, GHC.Base.Monad m) => GHC.Base.Applicative (Data.Equivalence.Monad.EquivT s c v m)
instance GHC.Base.Monad m => GHC.Base.Monad (Data.Equivalence.Monad.EquivT s c v m)
instance Control.Monad.Trans.Class.MonadTrans (Data.Equivalence.Monad.EquivT s c v)
instance GHC.Base.Monad m => Control.Monad.Fail.MonadFail (Data.Equivalence.Monad.EquivT s c v m)
instance Control.Monad.Reader.Class.MonadReader r m => Control.Monad.Reader.Class.MonadReader r (Data.Equivalence.Monad.EquivT s c v m)
instance (GHC.Base.Monoid w, Control.Monad.Writer.Class.MonadWriter w m) => Control.Monad.Writer.Class.MonadWriter w (Data.Equivalence.Monad.EquivT s c v m)
instance Control.Monad.State.Class.MonadState st m => Control.Monad.State.Class.MonadState st (Data.Equivalence.Monad.EquivT s c v m)
instance Control.Monad.Error.Class.MonadError e m => Control.Monad.Error.Class.MonadError e (Data.Equivalence.Monad.EquivT s c v m)
