data-partition-0.2.0.1: A pure disjoint set (union find) data structure

Portability portable experimental Luke Palmer 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.

Synopsis

# Documentation

data Partition a Source

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.

Instances

 Eq a => Eq (Partition a) Ord a => Ord (Partition a) Show a => Show (Partition a)

A partition in which every element of `a` is in its own set. Semantics: `[[discrete]] = { { x } | x in a }`

Synonym for `discrete`.

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

find :: Ord a => Partition a -> a -> Set aSource

`find p x` finds the set that the element `x` is associated with. Semantics: `[[find p x]] = the unique s in p such that x in s`.

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

`rep p x` finds the minimum element in the set containing `x`.