Dict

Core

A dictionary mapping unique keys to values. The keys 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

Dict

type Dict k v = Dict

A dictionary of keys and values. So a Dict String User is a dictionary that lets you look up a String (such as user names) and find the associated User.

Examples

users : Dict String User
users =
    Dict.fromList
        [ ("Alice", User "Alice" 28 1.65)
        , ("Bob", User "Bob" 19 1.82)
        , ("Chuck", User "Chuck" 33 1.75)
        ]

type alias User =
    { name : String
    , age : Int
    , height : Float
    }

Values

empty

empty : Dict k v

Create an empty dictionary.

Examples

isEmpty empty == True

singleton

singleton : k -> v -> Dict k v

Create a dictionary with one key-value pair.

Examples

singleton "Tom" 42
    |> get "Tom" == Just 42

insert

insert : k -> v -> Dict k v -> Dict k v

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

Examples

insert "Sue" 28 (singleton "Tom" 42)
    |> size == 2

update

update : 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.

Examples

update "Tom" (Maybe.map (\n -> n + 1)) (singleton "Tom" 42)
    |> get "Tom" == Just 43

update "Sue" (\_ -> Just 28) (singleton "Tom" 42)
    |> get "Sue" == Just 28

remove

remove : 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.

Examples

remove "Tom" (fromList [("Tom", 42), ("Sue", 28)])
    |> member "Tom" == False

isEmpty

isEmpty : Dict k v -> Bool

Determine if a dictionary is empty.

Examples

isEmpty empty == True

member

member : k -> Dict k v -> Bool

Determine if a key is in a dictionary.

Examples

member "Tom" (singleton "Tom" 42) == True
member "Sue" (singleton "Tom" 42) == False

get

get : 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.

Examples

animals = fromList [ ("Tom", Cat), ("Jerry", Mouse) ]

get "Tom" animals == Just Cat
get "Jerry" animals == Just Mouse
get "Spike" animals == Nothing

size

size : Dict k v -> Int

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

Examples

size empty == 0
size (fromList [("a", 1), ("b", 2)]) == 2

keys

keys : Dict k v -> List k

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

Examples

keys (fromList [(0, "Alice"), (1, "Bob")]) == [0, 1]

values

values : Dict k v -> List v

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

Examples

values (fromList [(0, "Alice"), (1, "Bob")]) == ["Alice", "Bob"]

toList

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

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

Examples

toList (fromList [(1, "b"), (0, "a")]) == [(0, "a"), (1, "b")]

fromList

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

Convert an association list into a dictionary.

Examples

fromList [("a", 1), ("b", 2)]
    |> size == 2

map

map : (k -> v -> w) -> Dict k v -> Dict k w

Apply a function to all values in a dictionary.

Examples

map (\_ v -> v * 2) (fromList [("a", 1), ("b", 2)])
    |> values == [2, 4]

foldl

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.

Examples

getAges : Dict String User -> List Int
getAges users =
    Dict.foldl addAge [] users

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

-- getAges users == [33, 19, 28]

foldr

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.

Examples

getAges : Dict String User -> List Int
getAges users =
    Dict.foldr addAge [] users

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

-- getAges users == [28, 19, 33]

filter

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

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

Examples

filter (\k _ -> k > 0) (fromList [(-1, "a"), (1, "b")])
    |> keys == [1]

partition

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

Examples

partition (\k _ -> k < 0) (fromList [(-1, "a"), (1, "b")])
    |> (\(yes, no) -> (keys yes, keys no))
    == ([-1], [1])

union

union : Dict k v -> Dict k v -> Dict k v

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

Examples

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

intersect

intersect : 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.

Examples

intersect (fromList [("a", 1), ("b", 2)]) (fromList [("a", 9)])
    |> toList == [("a", 1)]

diff

diff : Dict k v -> Dict k v -> Dict k v

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

Examples

diff (fromList [("a", 1), ("b", 2)]) (fromList [("a", 9)])
    |> toList == [("b", 2)]