| Portability | portable |
|---|---|
| Stability | experimental |
| Maintainer | Luke Palmer <lrpalmer@gmail.com> |
| Safe Haskell | Safe-Inferred |
Data.Partition
Description
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 }