| Copyright | Patrick Bahr 2010 |
|---|---|
| License | BSD-3-Clause |
| Maintainer | Patrick Bahr, Andreas Abel |
| Stability | stable |
| Portability | non-portable (MPTC) |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.Equivalence.STT
Description
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.
Synopsis
- data Equiv s c a
- data Class s c a
- leastEquiv :: (Monad m, Applicative m) => (a -> c) -> (c -> c -> c) -> STT s m (Equiv s c a)
- getClass :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s m (Class s c a)
- 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)
- combineAll :: (Monad m, Applicative m, Ord a) => Equiv s c a -> [Class s c a] -> STT s m ()
- same :: (Monad m, Applicative m, Ord a) => Equiv s c a -> Class s c a -> Class s c a -> STT s m Bool
- desc :: (Monad m, Applicative m, Ord a) => Equiv s c a -> Class s c a -> STT s m c
- remove :: (Monad m, Applicative m, Ord a) => Equiv s c a -> Class s c a -> STT s m Bool
- equate :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> a -> STT s m ()
- equateAll :: (Monad m, Applicative m, Ord a) => Equiv s c a -> [a] -> STT s m ()
- equivalent :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> a -> STT s m Bool
- classDesc :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s m c
- removeClass :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s m Bool
- values :: (Monad m, Applicative m, Ord a) => Equiv s c a -> STT s m [a]
- classes :: (Monad m, Applicative m, Ord a) => Equiv s c a -> STT s m [Class s c a]
Equivalence Relation
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.
Abstract representation of an equivalence class.
Instances
| (Monad m, Applicative m, Ord v) => MonadEquiv (Class s d v) v d (EquivT s d v m) Source # | |
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 # | |
Arguments
| :: (Monad m, Applicative m) | |
| => (a -> 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. |
| -> STT s m (Equiv 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
a). The arguments are used to maintain equivalence class
descriptors.
Operations on Equivalence Classes
getClass :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s m (Class s c a) Source #
This function provides the equivalence class the given element is contained in.
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) 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.
combineAll :: (Monad m, Applicative m, Ord a) => Equiv s c a -> [Class s c a] -> STT s m () Source #
This function combines all equivalence classes in the given list. Afterwards all elements in the argument list represent the same equivalence class!
same :: (Monad m, Applicative m, Ord a) => Equiv s c a -> Class s c a -> Class s c a -> STT s m Bool Source #
This function decides whether the two given equivalence classes are the same.
desc :: (Monad m, Applicative m, Ord a) => Equiv s c a -> Class s c a -> STT s m c Source #
This function returns the descriptor of the given equivalence class.
remove :: (Monad m, Applicative m, Ord a) => Equiv s c a -> Class s c a -> STT s m Bool Source #
This function removes the given equivalence class. If the
equivalence class does not exist anymore, False is returned;
otherwise True.
Operations on Elements
equate :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> a -> STT s m () Source #
This function equates the two given elements. That is, it unions the equivalence classes of the two elements and combines their descriptor.
equateAll :: (Monad m, Applicative m, Ord a) => Equiv s c a -> [a] -> STT s 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.
equivalent :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> a -> STT s m Bool Source #
This function decides whether the two given elements are in the same equivalence class according to the given equivalence relation representation.
classDesc :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s m c Source #
This function returns the descriptor of the given element's equivalence class.
removeClass :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s 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.