Data.Equality.Graph.ReprUnionFind

Union-find-like data structure that defines equivalence classes of e-class ids.

Documentation

data ReprUnionFind

A union find for equivalence classes of e-class ids.

Instances

Show ReprUnionFind

Defined in Data.Equality.Graph.ReprUnionFind

Methods

showsPrec :: Int -> ReprUnionFind -> ShowS

show :: ReprUnionFind -> String

showList :: [ReprUnionFind] -> ShowS

emptyUF :: ReprUnionFind

The empty ReprUnionFind.

makeNewSet

Arguments

:: ReprUnionFind

-> (ClassId, ReprUnionFind)

Newly created e-class id and updated ReprUnionFind

Create a new e-class id in the given ReprUnionFind.

unionSets

Arguments

:: ClassId

E-class id a

-> ClassId

E-class id b

-> ReprUnionFind

Union-find containing a and b

-> (ClassId, ReprUnionFind)

The new leader (always a) and the updated union-find

Union operation of the union find.

Given two leader ids, unions the two eclasses making a the leader, that is, b is now represented by a

findRepr

Arguments

:: ClassId

-> ReprUnionFind

-> ClassId

The found canonical representation

Find the canonical representation of an e-class id