DictAny

A dictionary mapping unique keys to values. Keys can be any type.

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

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

Dictionaries

type Dict k v

A dictionary of keys and values. So a Dict Key Value is a dictionary that lets you look up a unique Key and find the associated Value.

import DictAny as Dict exposing (Dict)


type ID
    = ID Int


comparer : ID -> ID -> Order
comparer (ID a) (ID b) =
    compare a b


type alias Museum =
    { name : String, rating : Int }


museums : Dict ID Museum
museums =
    [ ( ID 1, { name = "Natural History", rating = 4 } )
    , ( ID 8, { name = "Tate Modern", rating = 3 } )
    , ( ID 42, { name = "Science", rating = 5 } )
    ]
        |> Dict.fromList comparer


museums |> Dict.get comparer (ID 42)
    --> Just { name = "Science", rating = 5 }

Build

empty : Dict k v

Create an empty dictionary.

singleton : k -> v -> Dict k v

Create a dictionary with one key-value pair.

insert : (k -> k -> Order) -> k -> v -> Dict k v -> Dict k v

Insert a key-value pair into a dictionary. Replaces value when there is a collision.

update : (k -> k -> Order) -> k -> (Maybe v -> Maybe v) -> Dict k v -> Dict k v

Update the value of a dictionary for a specific key with a given function.

remove : (k -> k -> Order) -> k -> Dict k v -> Dict k v

Remove a key-value pair from a dictionary. If the key is not found, no changes are made.

Query

isEmpty : Dict k v -> Bool

Determine if a dictionary is empty.

isEmpty empty == True

member : (k -> k -> Order) -> k -> Dict k v -> Bool

Determine if a key is in a dictionary.

get : (k -> k -> Order) -> k -> Dict k v -> Maybe v

Get the value associated with a key. If the key is not found, return Nothing. This is useful when you are not sure if a key will be in the dictionary.

import DictAny as Dict exposing (Dict)


type Animal = Cat | Dog | Mouse


animalToInt : Animal -> Int
animalToInt animal =
    case animal of
        Cat -> 0
        Dog -> 1
        Mouse -> 2


comparer : Animal -> Animal -> Order
comparer a b = compare (animalToInt a) (animalToInt b)


animals : Dict Animal String
animals = [ (Cat, "Tom"), (Mouse, "Jerry") ]
                |> fromList comparer


animals |> Dict.get comparer Cat --> Just "Tom"
animals |> Dict.get comparer Dog --> Nothing
animals |> Dict.get comparer Mouse --> Just "Jerry"

size : Dict k v -> Int

Determine the number of key-value pairs in the dictionary.

Lists

keys : Dict k v -> List k

Get all of the keys in a dictionary, sorted from lowest to highest.

keys (fromList compare [ ( 0, "Alice" ), ( 1, "Bob" ) ])
    --> [0,1]

values : Dict k v -> List v

Get all of the values in a dictionary, in the order of their keys.

values
    (fromList compare [ ( 0, "Alice" ), ( 1, "Bob" ) ])
        --> ["Alice", "Bob"]

toList : Dict k v -> List ( k, v )

Convert a dictionary into an association list of key-value pairs, sorted by keys.

fromList : (k -> k -> Order) -> List ( k, v ) -> Dict k v

Convert an association list into a dictionary.

Transform

map : (k -> a -> b) -> Dict k a -> Dict k b

Apply a function to all values in a dictionary.

foldl : (k -> v -> b -> b) -> b -> Dict k v -> b

Fold over the key-value pairs in a dictionary from lowest key to highest key.

import DictAny as Dict exposing (Dict)


type alias User = { age : Int }


getAges : Dict String User -> List Int
getAges dict =
    dict |> Dict.foldl consAge []


consAge : String -> User -> List Int -> List Int
consAge _ user ages =
    user.age :: ages


users : Dict String User
users =
    [ ("Fred", {age=33})
    , ("Bert", {age=19})
    , ("Adam", {age=42})
    ] |> Dict.fromList compare


getAges users --> [33,19,42]

foldr : (k -> v -> b -> b) -> b -> Dict k v -> b

Fold over the key-value pairs in a dictionary from highest key to lowest key.

import DictAny as Dict exposing (Dict)


type alias User = { age : Int }


getAges : Dict String User -> List Int
getAges dict =
    dict |> Dict.foldr consAge []


consAge : String -> User -> List Int -> List Int
consAge _ user ages =
    user.age :: ages


users : Dict String User
users =
    [ ("Fred", {age=33})
    , ("Bert", {age=19})
    , ("Adam", {age=42})
    ] |> Dict.fromList compare


getAges users -->  [42,19,33]

filter : (k -> k -> Order) -> (k -> v -> Bool) -> Dict k v -> Dict k v

Keep only the key-value pairs that pass the given test.

partition : (k -> k -> Order) -> (k -> v -> Bool) -> Dict k v -> ( Dict k v, Dict k v )

Partition a dictionary according to some test. The first dictionary contains all key-value pairs which passed the test, and the second contains the pairs that did not.

Combine

union : (k -> k -> Order) -> Dict k v -> Dict k v -> Dict k v

Combine two dictionaries. If there is a collision, preference is given to the first dictionary.

intersect : (k -> k -> Order) -> Dict k v -> Dict k v -> Dict k v

Keep a key-value pair when its key appears in the second dictionary. Preference is given to values in the first dictionary.

diff : (k -> k -> Order) -> Dict k a -> Dict k b -> Dict k a

Keep a key-value pair when its key does not appear in the second dictionary.

merge :

(k -> k -> Order)

-> (k -> a -> result -> result)

-> (k -> a -> b -> result -> result)

-> (k -> b -> result -> result)

-> Dict k a

-> Dict k b

-> result

The most general way of combining two dictionaries. You provide three accumulators for when a given key appears:

Only in the left dictionary.
In both dictionaries.
Only in the right dictionary.

You then traverse all the keys from lowest to highest, building up whatever you want.

hedgehogface/dict-any-set-any/1.0.0