Portability | portable |
---|---|

Stability | experimental |

Maintainer | Luke Palmer <lrpalmer@gmail.com> |

Safe Haskell | Safe-Inferred |

Disjoint set data structure -- `Partition a`

maintains a collection of
disjoint sets of type `a`

, with the ability to find which set a particular
item belongs to and the ability to merge any two such sets into one.

# Documentation

A Partition of `a`

: represents a collection of disjoint sets of `a`

whose
union includes every element of `a`

. Semantics: `[[Partition a]] = P(P(a))`

where `P`

is the power set operation.

A partition in which every element of `a`

is in its own set. Semantics:
`[[discrete]] = { { x } | x in a }`

fromSets :: Ord a => [Set a] -> Partition aSource

Takes a list of disjoint sets and constructs a partition containing those sets, with every remaining element being given its own set.

nontrivialSets :: Partition a -> [Set a]Source

Returns a list of all nontrivial sets (sets with more than one element) in the partition.

join :: Ord a => a -> a -> Partition a -> Partition aSource

`join x y`

merges the two sets containing `x`

and `y`

into a single set. Semantics:
`[[join x y p]] = (p `minus` find x `minus` find y) `union` { find x `union` find y }`