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

Adds a list of elements into their own set.

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


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

Finds the root element from a given element if it exists.

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

Checks whether or not the disjoint set contains an element.

set : DisjointSet String
set =
    add [ "a" ] empty


has "a" set --> True
has "b" set --> False

Returns a list of all the elements contained in the disjoint set.

items empty --> []
items (add [ "a", "b", "c" ] empty) --> [ "a", "b", "c" ]


empty
    |> union "a" "b"
    |> union "c" "d"
    |> items
--> [ "a", "b", "c", "d" ]

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

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