Data.Equivalence.Persistent

Code for manipulation equivalence classes on index types. An Equivalence is an equivalence relation. The empty equivalence relation is constructed over a ranges of values using emptyEquivalence. Less discerning equivalence relations can be obtained with equate and equateAll. The relation can be tested with equiv and equivalent, and canonical representatives can be chosen with repr.

An example follows:

 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

Documentation

data Equivalence i

An Equivalence is an equivalence relation on a range of values of some index type.

emptyEquivalence :: Ix i => (i, i) -> Equivalence i

emptyEquivalence is an equivalence relation that equates two values only when they are equal to each other. It is the most discerning such relation possible.

repr :: Ix i => Equivalence i -> i -> i

repr gives a canonical representative of the equivalence class containing x. It is chosen arbitrarily, but is always the same for a given equivalence relation.

This function is slightly unsafe. In particular, it's possible to build the same equivalence relation by equating values in two different orders, and the choice of canonical representatives will differ. You can either think of a value of type Equivalence as an equivalence relation together with a choice of canonical representatives, or you can consider this not a pure function. Since Equivalence is not an instance of Eq and equality is not observable, both perspectives are valid.

equiv :: Ix i => Equivalence i -> i -> i -> Bool

Determines if two values are equivalent under the given equivalence relation.

equivalent :: Ix i => Equivalence i -> [i] -> Bool

Determines if all of the given values are equivalent under the given equivalence relation.

equate :: Ix i => i -> i -> Equivalence i -> Equivalence i

Construct the equivalence relation obtained by equating the given two values. This combines equivalence classes.

equateAll :: Ix i => [i] -> Equivalence i -> Equivalence i

Construct the equivalence relation obtained by equating all of the given values. This combines equivalence classes.