persistent-equivalence-0.3: Persistent equivalence relations (aka union-find)

Data.Equivalence.Persistent

Description

Code for manipulation of 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`.

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

Synopsis

# Documentation

data Equivalence i Source

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

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

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

domain :: Ix i => Equivalence i -> (i, i)Source

Gets the domain of an equivalence relation, as the ordered pair of index bounds.

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

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

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

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

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

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

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

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