Safe Haskell	None
Language	Haskell2010

GHC.Data.UnionFind

Synopsis

newtype Point s a = Point (STRef s (Link s a))
writePoint :: Point s a -> Link s a -> ST s ()
readPoint :: Point s a -> ST s (Link s a)
data Link s a
- = Info !(STRef s Int) !(STRef s a)
- | Link !(Point s a)
fresh :: a -> ST s (Point s a)
repr :: Point s a -> ST s (Point s a)
find :: Point s a -> ST s a
union :: Point s a -> Point s a -> ST s ()
equivalent :: Point s a -> Point s a -> ST s Bool

Documentation

newtype Point s a Source #

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))

Instances

Instances details

Eq (Point s a) Source #
Instance details Defined in GHC.Data.UnionFind Methods (==) :: Point s a -> Point s a -> Bool # (/=) :: Point s a -> Point s a -> Bool #

writePoint :: Point s a -> Link s a -> ST s () Source #

Mutable write to a Point

readPoint :: Point s a -> ST s (Link s a) Source #

Read the current value of Point.

data 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)

fresh :: a -> ST s (Point s a) Source #

Create a fresh equivalence class with one element.

repr :: Point s a -> ST s (Point s a) Source #

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

find :: Point s a -> ST s a Source #

Return the canonical element of an equivalence class Point.

union :: 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.

equivalent :: Point s a -> Point s a -> ST s Bool Source #

Test if two points are in the same equivalence class.