Moduleghc-9.14.1GHC2021

GHC.Data.UnionFind

Synopsis

newtype Point
value writePoint
value readPoint
data Link
value fresh
value repr
value find
value union
value equivalent

Packageghc-9.14.1
Exports9
LanguageGHC2021
LicenceBSD-3-Clause
SourceUnionFind.hs

newtypenewtype Point s a

A variable which can be unified; alternately, this can be thought of as an equivalence class with a distinguished representative.

Constructors

Point (STRef s (Link s a))

Instances1Eq

Eq (Point s a)Defined in ghc-9.14.1 · GHC.Data.UnionFind

valuewritePoint :: Point s a -> Link s a -> ST s ()

Source#

Mutable write to a Point

valuereadPoint :: Point s a -> ST s (Link s a)

Source#

Read the current value of Point.

datadata Link s a

Source#

The internal data structure for a Point, which either records the representative element of an equivalence class, or a link to the Point that actually stores the representative type.

Constructors

Info !(STRef s Int) !(STRef s a)
Link !(Point s a)

valuefresh :: a -> ST s (Point s a)

Source#

Create a fresh equivalence class with one element.

valuerepr :: Point s a -> ST s (Point s a)

Source#

Flatten any chains of links, returning a Point which points directly to the canonical representation.

valuefind :: Point s a -> ST s a

Source#

Return the canonical element of an equivalence class Point.

valueunion :: Point s a -> Point s a -> ST s ()

Source#

Unify two equivalence classes, so that they share a canonical element. Keeps the descriptor of point2.

valueequivalent :: Point s a -> Point s a -> ST s Bool

Source#

Test if two points are in the same equivalence class.