FastSet

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

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

Sets

type Set t

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

Build

empty : Set t

Create an empty set.

singleton : comparable -> Set comparable

Create a set with one value.

insert : comparable -> Set comparable -> Set comparable

Insert a value into a set.

remove : comparable -> Set comparable -> Set comparable

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

Query

isEmpty : Set k -> Bool

Determine if a set is empty.

isEmpty empty
--> True

member : comparable -> Set comparable -> Bool

Determine if a value is in a set.

size : Set t -> Int

Determine the number of elements in a set.

equals : Set comparable -> Set comparable -> Bool

Determine if two sets are equal. This is needed because the structure could be different depending on insertion order.

Combine

union : Set comparable -> Set comparable -> Set comparable

Get the union of two sets. Keep all values.

intersect : Set comparable -> Set comparable -> Set comparable

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

diff : Set comparable -> Set comparable -> Set comparable

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

Lists

toList : Set k -> List k

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

fromList : List comparable -> Set comparable

Convert an association list into a set.

Min / Max

getMin : Set v -> Maybe v

Gets the smallest value.

[ 1, 2 ]
    |> fromList
    |> getMin
--> Just 1




empty
    |> getMin
--> Nothing

getMax : Set v -> Maybe v

Gets the biggest value.

[ 1, 2 ]
    |> fromList
    |> getMax
--> Just 2




empty
    |> getMax
--> Nothing

popMin : Set comparable -> Maybe ( comparable, Set comparable )

Removes the smallest value from the set, and returns it.

[ 1, 2 ]
    |> fromList
    |> popMin
--> Just ( 1, fromList [ 2 ] )




empty
    |> popMin
--> Nothing

popMax : Set comparable -> Maybe ( comparable, Set comparable )

Removes the biggest value from the set, and returns it.

[ 1, 2 ]
    |> fromList
    |> popMax
--> Just ( 2, fromList [ 1 ] )




empty
    |> popMax
--> Nothing

Transform

map : (comparable -> comparable2) -> Set comparable -> Set comparable2

Apply a function to all values in a set.

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

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

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

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

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

Keep only the values that pass the given test.

partition :

(comparable -> Bool)

-> Set comparable

-> ( Set comparable, Set comparable )

Partition a set according to some test. The first set contains all values which passed the test, and the second contains the pairs that did not.

Interoperability

toCoreSet : Set comparable -> Set comparable

Convert the set into an equivalent one from elm/core.

fromCoreSet : Set comparable -> Set comparable

Convert the set from an equivalent one from elm/core.

Advanced functions

stoppableFoldl : (v -> acc -> Step acc) -> acc -> Set v -> acc

A foldl that can stop early instead of traversing the whole set.

stoppableFoldl
    (\v acc ->
        if v >= 10 then
            Stop acc
        else
            Continue (v + acc)
    )
    0
    (fromList <| List.range 1 10000)
--> 55

stoppableFoldr : (v -> acc -> Step acc) -> acc -> Set v -> acc

A foldr that can stop early instead of traversing the whole set.

stoppableFoldr
    (\v acc ->
        if v <= 9990 then
            Stop acc
        else
            Continue (v + acc)
    )
    0
    (fromList <| List.range 1 10000)
--> 89964

miniBill/elm-fast-dict/1.2.0