-- 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.4.1


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

-- | Abstract representation of an equivalence class.
data Class s c a

-- | This function constructs the initial data structure for maintaining an
--   equivalence relation. That is, it represents the finest (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, 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 exist anymore, <tt>False</tt> is returned; otherwise
--   <tt>True</tt>.
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, <tt>False</tt> is
--   returned; otherwise <tt>True</tt>.
removeClass :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s m Bool

-- | This function returns all values represented by some equivalence
--   class.
values :: (Monad m, Applicative m, Ord a) => Equiv s c a -> STT s m [a]

-- | This function returns the list of all equivalence classes.
classes :: (Monad m, Applicative m, Ord a) => Equiv s c a -> STT s m [Class s c a]


-- | This is an alternative interface to the union-find implementation in
--   '<a>STT'</a>. 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, 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, <tt>False</tt> is
--   returned; otherwise <tt>True</tt>.
removeClass :: MonadEquiv c v d m => v -> m Bool

-- | This function provides the equivalence class of the given element.
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 exist anymore, <tt>False</tt> is returned; otherwise
--   <tt>True</tt>.
remove :: MonadEquiv c v d m => c -> m Bool

-- | This function returns all values represented by some equivalence
--   class.
values :: MonadEquiv c v d m => m [v]

-- | This function returns the list of all equivalence classes.
classes :: MonadEquiv c v d m => m [c]

-- | This function decides whether the two given elements are equivalent in
--   the current equivalence relation.
equivalent :: (MonadEquiv c v d m, MonadEquiv c v d n, MonadTrans t, t n ~ m) => v -> v -> m Bool

-- | This function obtains the descriptor of the given element's
--   equivalence class.
classDesc :: (MonadEquiv c v d m, MonadEquiv c v d n, MonadTrans t, t n ~ 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, MonadEquiv c v d n, MonadTrans t, t n ~ m) => [v] -> m ()

-- | 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 :: (MonadEquiv c v d m, MonadEquiv c v d n, MonadTrans t, t n ~ m) => v -> m Bool

-- | This function provides the equivalence class of the given element.
getClass :: (MonadEquiv c v d m, MonadEquiv c v d n, MonadTrans t, t n ~ 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, MonadEquiv c v d n, MonadTrans t, t n ~ m) => [c] -> m ()

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

-- | This function returns the descriptor of the given equivalence class.
desc :: (MonadEquiv c v d m, MonadEquiv c v d n, MonadTrans t, t n ~ m) => c -> m d

-- | This function removes the given equivalence class. If the equivalence
--   class does not exist anymore, <tt>False</tt> is returned; otherwise
--   <tt>True</tt>.
remove :: (MonadEquiv c v d m, MonadEquiv c v d n, MonadTrans t, t n ~ m) => c -> m Bool

-- | This function returns all values represented by some equivalence
--   class.
values :: (MonadEquiv c v d m, MonadEquiv c v d n, MonadTrans t, t n ~ m) => m [v]

-- | This function returns the list of all equivalence classes.
classes :: (MonadEquiv c v d m, MonadEquiv c v d n, MonadTrans t, t n ~ m) => m [c]

-- | 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 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) => (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, 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 <a>runEquivM</a> that only
--   maintains trivial equivalence class descriptors of type <tt>()</tt>.
runEquivM' :: (forall s. EquivM' s v a) -> a
instance 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)
instance GHC.Base.Monad m => GHC.Base.Monad (Data.Equivalence.Monad.EquivT s c v m)
instance GHC.Base.Monad m => GHC.Base.Applicative (Data.Equivalence.Monad.EquivT s c v m)
instance GHC.Base.Functor m => GHC.Base.Functor (Data.Equivalence.Monad.EquivT s c v m)
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 => 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 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)