A data structure that stores non-overlapping sets.

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.

union "a" "a" empty |> toList --> [ ("a", "a") ]
union "a" "b" empty |> toList --> [ ("a", "a"), ("b", "a") ]


empty
    |> union "a" "b"
    |> union "b" "c"
    |> toList
--> [ ("a", "a"), ("b", "a"), ("c", "a") ]


empty
    |> union "a" "b"
    |> union "x" "y"
    |> union "b" "y"
    |> toList
--> [ ("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 list of (element, equivalent) pairs.

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