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

MaintainerLuke Palmer <>
Safe HaskellSafe-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.



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.


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

discrete :: Partition aSource

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

empty :: Partition aSource

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.