scyther-proof-0.3.0: Automatic generation of Isabelle/HOL correctness proofs for security protocols.

Data.UnionFind

Description

A persistent, but not so efficient union-find structure.

Synopsis

# Documentation

newtype UnionFind a Source

Constructors

 UnionFind FieldsunUnionFind :: Map a a

Instances

 Typeable1 UnionFind Eq a => Eq (UnionFind a) (Data a, Ord a) => Data (UnionFind a) Ord a => Ord (UnionFind a) Show a => Show (UnionFind a) Ord a => Monoid (UnionFind a)

unionFind :: Ord a => Map a a -> UnionFind aSource

Smart constructor from a `Map` to a union-find structure.

map :: (Ord a, Ord b) => (a -> b) -> UnionFind a -> UnionFind bSource

`empty` is the syntactic identity equivalence relation.

size :: UnionFind a -> IntSource

`size uf` returns the number of stored equalities.

equate :: Ord a => a -> a -> UnionFind a -> UnionFind aSource

`equate x y uf` inserts the equality `x = y` into `uf`.

fromList :: Ord a => [(a, a)] -> UnionFind aSource

equateList :: Ord a => UnionFind a -> [(a, a)] -> UnionFind aSource

toList :: UnionFind a -> [(a, a)]Source

find :: Ord a => a -> UnionFind a -> Maybe aSource

`find x uf` returns the representative of the equivalence class that `x` belongs to in `uf`, if there is any.

findWithDefault :: Ord a => a -> a -> UnionFind a -> aSource

`findWithDefault def x uf` returns the representative of the equivalence class that `x` belongs to in `uf` or `def`, if there is no representative.

equiv :: Ord a => (a, a) -> UnionFind a -> BoolSource

`(x,y) equiv uf` iff `x` and `y` are in the same equivalence class with respect to `uf`.