The DisjointSet type definition.

Creats an empty disjoint set.

Unifies two elements. If an element is not part of any set, it is created.

The root element is always the first element that was added.

This operation does path compression as an optimization.

import Dict


union "a" "a" empty |> toDict --> Dict.fromList [ ("a", "a") ]
union "a" "b" empty |> toDict --> Dict.fromList [ ("a", "a"), ("b", "a") ]


empty
    |> union "a" "b"
    |> union "b" "c"
    |> toDict
--> Dict.fromList [ ("a", "a"), ("b", "a"), ("c", "a") ]


empty
    |> union "a" "b"
    |> union "x" "y"
    |> union "b" "y"
    |> toDict
--> Dict.fromList [ ("a", "a"), ("b", "a"), ("x", "a"), ("y", "a") ]

Finds the root element from a given element.

import Dict


set : DisjointSet String
set =
    empty
        |> union "a" "b"
        |> union "b" "c"
        |> union "c" "d"
        |> union "e" "e"


find "a" set --> Just "a"
find "b" set --> Just "a"
find "c" set --> Just "a"
find "d" set --> Just "a"
find "e" set --> Just "e"
find "x" set --> Nothing

Creates a disjoint set from a dictionary of (element, equivalent) pairs.

Creates a dictionary of (element, equivalent) pairs from a disjoint set.