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


-- | Persistent equivalence relations (aka union-find)
--   
--   This is a persistent data structure for equivalence relations (known
--   in the imperative world as union-find or disjoint set union). It
--   exhibits optimal performance when used in a linear pattern, but
--   degrades when other access patterns are used.
--   
--   The basic idea is as given by Conchon and Filliatre in their 2007
--   paper, "A persistent union-find data structure." Unlike the
--   implementation given in the paper, this version is safe with multiple
--   threads, but does not optimize for backtracking.
--   
--   Version 0.3 contains some performance improvements for concurrent
--   applications, and removes the <a>repr</a> function, which was poorly
--   defined and had no good uses.
@package persistent-equivalence
@version 0.3


-- | Code for manipulation of equivalence classes on index types. An
--   <a>Equivalence</a> is an equivalence relation. The empty equivalence
--   relation is constructed over a ranges of values using
--   <a>emptyEquivalence</a>. Less discerning equivalence relations can be
--   obtained with <a>equate</a> and <a>equateAll</a>. The relation can be
--   tested with <a>equiv</a> and <a>equivalent</a>.
--   
--   An example follows:
--   
--   <pre>
--   import Data.Equivalence.Persistent
--   
--   rel = equateAll [1,3,5,7,9]
--       . equate 5 6
--       . equate 2 4
--       $ emptyEquivalence (1,10)
--   
--   test1 = equiv rel 3 5 -- This is True
--   test2 = equiv rel 1 6 -- This is True
--   test3 = equiv rel 4 6 -- This is False
--   </pre>
module Data.Equivalence.Persistent

-- | An <a>Equivalence</a> is an equivalence relation on a range of values
--   of some index type.
data Equivalence i

-- | <a>emptyEquivalence</a> is an equivalence relation that equates two
--   values only when they are equal to each other. It is the most
--   discerning such relation possible.
emptyEquivalence :: Ix i => (i, i) -> Equivalence i

-- | Gets the domain of an equivalence relation, as the ordered pair of
--   index bounds.
domain :: Ix i => Equivalence i -> (i, i)

-- | Determines if two values are equivalent under the given equivalence
--   relation.
equiv :: Ix i => Equivalence i -> i -> i -> Bool

-- | Determines if all of the given values are equivalent under the given
--   equivalence relation.
equivalent :: Ix i => Equivalence i -> [i] -> Bool

-- | Construct the equivalence relation obtained by equating the given two
--   values. This combines equivalence classes.
equate :: Ix i => i -> i -> Equivalence i -> Equivalence i

-- | Construct the equivalence relation obtained by equating all of the
--   given values. This combines equivalence classes.
equateAll :: Ix i => [i] -> Equivalence i -> Equivalence i