Set

Core

A set of unique values. The values can be any comparable type. This includes Int, Float, Char, String, and tuples or lists of comparable types.

Insert, remove, and query operations all take *O(log n)* time.

Types

Set

type Set a = Set

Represents a set of unique values. So Set Int is a set of integers and Set String is a set of strings.

Examples

numbers : Set Int
numbers =
    fromList [1, 2, 3]

Values

empty

empty : Set a

Create an empty set.

Examples

isEmpty empty == True

singleton

singleton : a -> Set a

Create a set with one value.

Examples

singleton 42
    |> member 42 == True

insert

insert : a -> Set a -> Set a

Insert a value into a set.

Examples

insert 3 (fromList [1, 2])
    |> toList == [1, 2, 3]

remove

remove : a -> Set a -> Set a

Remove a value from a set. If the value is not found, no changes are made.

Examples

remove 2 (fromList [1, 2, 3])
    |> toList == [1, 3]

isEmpty

isEmpty : Set a -> Bool

Determine if a set is empty.

Examples

isEmpty empty == True
isEmpty (singleton 1) == False

member

member : a -> Set a -> Bool

Determine if a value is in a set.

Examples

member 2 (fromList [1, 2, 3]) == True
member 4 (fromList [1, 2, 3]) == False

size

size : Set a -> Int

Determine the number of elements in a set.

Examples

size empty == 0
size (fromList [1, 2, 3]) == 3

union

union : Set a -> Set a -> Set a

Get the union of two sets. Keep all values.

Examples

union (fromList [1, 2]) (fromList [2, 3])
    |> toList == [1, 2, 3]

intersect

intersect : Set a -> Set a -> Set a

Get the intersection of two sets. Keeps values that appear in both sets.

Examples

intersect (fromList [1, 2]) (fromList [2, 3])
    |> toList == [2]

diff

diff : Set a -> Set a -> Set a

Get the difference between the first set and the second. Keeps values that do not appear in the second set.

Examples

diff (fromList [1, 2, 3]) (fromList [2])
    |> toList == [1, 3]

toList

toList : Set a -> List a

Convert a set into a list, sorted from lowest to highest.

Examples

toList (fromList [3, 1, 2]) == [1, 2, 3]

fromList

fromList : List a -> Set a

Convert a list into a set, removing any duplicates.

Examples

fromList [1, 1, 2, 3]
    |> toList == [1, 2, 3]

map

map : (a -> b) -> Set a -> Set b

Map a function onto a set, creating a new set with no duplicates.

Examples

map (\n -> n * 2) (fromList [1, 2, 3])
    |> toList == [2, 4, 6]

foldl

foldl : (a -> b -> b) -> b -> Set a -> b

Fold over the values in a set, in order from lowest to highest.

Examples

foldl (+) 0 (fromList [1, 2, 3]) == 6

foldr

foldr : (a -> b -> b) -> b -> Set a -> b

Fold over the values in a set, in order from highest to lowest.

Examples

foldr (::) [] (fromList [1, 2, 3]) == [1, 2, 3]

filter

filter : (a -> Bool) -> Set a -> Set a

Only keep elements that pass the given test.

Examples

numbers : Set Int
numbers =
    fromList [-2, -1, 0, 1, 2]

positives : Set Int
positives =
    filter (\x -> x > 0) numbers

-- positives == fromList [1, 2]

partition

partition : (a -> Bool) -> Set a -> (Set a, Set a)

Create two new sets. The first contains all the elements that passed the given test, and the second contains all the elements that did not.

Examples

partition (\x -> x < 0) (fromList [-1, 0, 1])
    |> (\(neg, rest) -> (toList neg, toList rest))
    == ([-1], [0, 1])