SetAny

A set of values unique according to a comparison function. Values can be any type.

A comparison function a -> a -> Order is used to compare values, this should uniquely identify values.

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

Sets

type Set a

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

import SetAny as Set exposing (Set)


items : Set Item
items = [ Brush, Soap, Towel ] |> Set.fromList comparer


type Item
    = Brush
    | Soap
    | Shampoo
    | Towel


itemToInt : Item -> Int
itemToInt item =
    case item of
        Brush -> 1
        Soap -> 2
        Shampoo -> 3
        Towel -> 42


comparer : Item -> Item -> Order
comparer a b = compare (itemToInt a) (itemToInt b)


items |> Set.member comparer Shampoo --> False
items |> Set.member comparer Towel  --> True
items |> Set.toList --> [ Brush, Soap, Towel ]

Build

empty : Set a

Create an empty set.

singleton : a -> Set a

Create a set with one value.

insert : (a -> a -> Order) -> a -> Set a -> Set a

Insert a value into a set.

remove : (a -> a -> Order) -> a -> Set a -> Set a

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

Query

isEmpty : Set a -> Bool

Determine if a set is empty.

member : (a -> a -> Order) -> a -> Set a -> Bool

Determine if a value is in a set.

size : Set a -> Int

Determine the number of elements in a set.

Combine

union : (a -> a -> Order) -> Set a -> Set a -> Set a

Get the union of two sets. Keep all values.

intersect : (a -> a -> Order) -> Set a -> Set a -> Set a

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

diff : (a -> a -> Order) -> 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.

Lists

toList : Set a -> List a

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

fromList : (a -> a -> Order) -> List a -> Set a

Convert a list into a set, removing any duplicates.

Transform

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

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

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

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

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

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

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

Only keep elements that pass the given test.

import SetAny as Set exposing (Set)


numbers : Set Int
numbers =
    [ -2, -1, 0, 1, 2 ] |> Set.fromList compare


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


positives --> [1,2] |> Set.fromList compare

partition : (a -> a -> Order) -> (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.

hedgehogface/dict-any-set-any/1.0.0