AVL.Set

An AVL Tree based set.

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

Insert, remove, get and member operations all take O(log n) time. Size takes constant O(1) time.

Set

type alias Set key =

AVLSet key

Represents a set of unique values. So (Set Int) is a set of integers and (Set ID) is a set of custom ID values.

Construction

type alias Comparator key =

key -> key -> Order

A comparator is a function which compares two keys.

import AVL.Set as Set exposing (Comparator, Set)


type ID
    = ID Int


compareID : Comparator ID
compareID (ID x) (ID y) =
    compare x y


ids : Set ID User
ids =
    Set.fromListWith compareID [ ID 0, ID 1, ID 2 ]


probs : List Bool
probs =
    [ Set.member (ID 0)
    , Set.member (ID 3)
    ]

empty : Set comparable

Create an empty set with comparable keys.

emptyWith : Comparator key -> Set key

Create an empty set with custom keys.

singleton : comparable -> Set comparable

Create a set with one comparable key.

singletonWith : Comparator key -> key -> Set key

Create a set with one custom key.

fromList : List comparable -> Set comparable

Convert an list into a set with comparable keys.

fromListWith : Comparator key -> List key -> Set key

Convert an list into a set with custom keys.

Deconstruction

toList : Set key -> List key

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

Manipulation

insert : key -> Set key -> Set key

Insert a key into a set.

remove : key -> Set key -> Set key

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

toggle : key -> Set key -> Set key

Toggle a specific key.

clear : Set key -> Set key

Remove all entries from a set. Useful when you need to create new empty set using same comparator.

Query

isEmpty : Set key -> Bool

Determine if a set is empty.

size : Set key -> Int

Determine the number of elements in a set. It takes constant time to determine the size.

member : key -> Set key -> Bool

Determine if a value is in a set.

Transform

map : (key -> key) -> Set key -> Set key

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

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

Only keep elements that pass the given test.

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


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


-- positives == [ 0, 1, 2 ]

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

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.

foldl : (key -> acc -> acc) -> acc -> Set key -> acc

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

foldr : (key -> acc -> acc) -> acc -> Set key -> acc

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

Combine

union : Set key -> Set key -> Set key

Combine two sets.

diff : Set key -> Set key -> Set key

Keep a key when them do not appear in the right set.

intersect : Set key -> Set key -> Set key

Keep a keys when them appear in the right set.

owanturist/elm-avl-dict/2.0.0