Documentation

Dict k v

A dictionary that lets you associate keys with values.

Inserting

The most basic way to use a dictionary is to start with an empty one and then:

1. Call Dict.insert passing a key and a value, to associate that key with that value in the dictionary.
2. Later, call Dict.get passing the same key as before, and it will return the value you stored.

Here's an example of a dictionary which uses a city's name as the key, and its population as the associated value.

populationByCity =
    Dict.empty {}
    |> Dict.insert "London" 8_961_989
    |> Dict.insert "Philadelphia" 1_603_797
    |> Dict.insert "Shanghai" 24_870_895
    |> Dict.insert "Delhi" 16_787_941
    |> Dict.insert "Amsterdam" 872_680

Accessing keys or values

We can use Dict.keys and Dict.values functions to get only the keys or only the values.

You may notice that these lists have the same order as the original insertion order. This will be true if all you ever do is Dict.insert and Dict.get operations on the dictionary, but Dict.remove operations can change this order.

Removing

We can remove an element from the dictionary, like so:

populationByCity
    |> Dict.remove "Philadelphia"
    |> Dict.keys
    ==
    ["London", "Amsterdam", "Shanghai", "Delhi"]

Notice that the order has changed. Philadelphia was not only removed from the list, but Amsterdam - the last entry we inserted - has been moved into the spot where Philadelphia was previously. This is exactly what Dict.remove does. It removes an element and moves the most recent insertion into the vacated spot.

This move is done as a performance optimization, and it lets remove have constant time complexity.

Dict is inspired by IndexMap. The internal implementation of a dictionary is similar to absl::flat_hash_map. It has a list of keys value pairs that is ordered based on insertion. It uses a list of indices into the data as the backing of a hash map.

empty : {} -> Dict * *

Return an empty dictionary.

emptyDict = Dict.empty {}

capacity : Dict * * -> Nat

Returns the max number of elements the dictionary can hold before requiring a rehash.

foodDict =
    Dict.empty {}
    |> Dict.insert "apple" "fruit"

capacityOfDict = Dict.capacity foodDict

withCapacity : Nat -> Dict * *

Return a dictionary with space allocated for a number of entries. This may provide a performance optimization if you know how many entries will be inserted.

single : k, v -> Dict k v where k implements Hash & Eq

Returns a dictionary containing the key and value provided as input.

expect
    Dict.single "A" "B"
    |> Bool.isEq (Dict.insert (Dict.empty {}) "A" "B")

fromList : List ( k, v ) -> Dict k v where k implements Hash & Eq

Returns dictionary with the keys and values specified by the input List.

expect
    Dict.single 1 "One"
    |> Dict.insert 2 "Two"
    |> Dict.insert 3 "Three"
    |> Dict.insert 4 "Four"
    |> Bool.isEq (Dict.fromList [(1, "One"), (2, "Two"), (3, "Three"), (4, "Four")])

len : Dict * * -> Nat

Returns the number of values in the dictionary.

expect
    Dict.empty {}
    |> Dict.insert "One" "A Song"
    |> Dict.insert "Two" "Candy Canes"
    |> Dict.insert "Three" "Boughs of Holly"
    |> Dict.len
    |> Bool.isEq 3

isEmpty : Dict * * -> Bool

Check if the dictinoary is empty.

Dict.isEmpty (Dict.empty {} |> Dict.insert "key" 42)

Dict.isEmpty (Dict.empty {})

clear : Dict k v -> Dict k v where k implements Hash & Eq

Clears all elements from a dictionary keeping around the allocation if it isn't huge.

songs =
       Dict.empty {}
       |> Dict.insert "One" "A Song"
       |> Dict.insert "Two" "Candy Canes"
       |> Dict.insert "Three" "Boughs of Holly"

clearSongs = Dict.clear songs

expect Dict.len clearSongs == 0

map : Dict k a, (k, a -> b) -> Dict k b where k implements Hash & Eq, b implements Hash & Eq

Convert each value in the dictionary to something new, by calling a conversion function on each of them which receives both the key and the old value. Then return a new dictionary containing the same keys and the converted values.

joinMap : Dict a b, (a, b -> Dict x y) -> Dict x y where a implements Hash & Eq, x implements Hash & Eq

Like Dict.map, except the transformation function wraps the return value in a dictionary. At the end, all the dictionaries get joined together (using Dict.insertAll) into one dictionary.

You may know a similar function named concatMap in other languages.

walk : Dict k v, state, (state, k, v -> state) -> state where k implements Hash & Eq

Iterate through the keys and values in the dictionary and call the provided function with signature state, k, v -> state for each value, with an initial state value provided for the first call.

expect
    Dict.empty {}
    |> Dict.insert "Apples" 12
    |> Dict.insert "Orange" 24
    |> Dict.walk 0 (\count, _, qty -> count + qty)
    |> Bool.isEq 36

walkUntil : Dict k v, state, (state, k, v -> [ Continue state, Break state ]) -> state where k implements Hash & Eq

Same as Dict.walk, except you can stop walking early.

Performance Details

Compared to Dict.walk, this can potentially visit fewer elements (which can improve performance) at the cost of making each step take longer. However, the added cost to each step is extremely small, and can easily be outweighed if it results in skipping even a small number of elements.

As such, it is typically better for performance to use this over Dict.walk if returning Break earlier than the last element is expected to be common.

people =
    Dict.empty {}
    |> Dict.insert "Alice" 17
    |> Dict.insert "Bob" 18
    |> Dict.insert "Charlie" 19

isAdult = \_, _, age ->
        if age >= 18 then
            Break Bool.true
        else
            Continue Bool.false

someoneIsAnAdult = Dict.walkUntil people Bool.false isAdult

expect someoneIsAnAdult == Bool.true

get : Dict k v, k -> Result v [KeyNotFound] where k implements Hash & Eq

Get the value for a given key. If there is a value for the specified key it will return Ok value, otherwise return Err KeyNotFound.

dictionary =
    Dict.empty {}
    |> Dict.insert 1 "Apple"
    |> Dict.insert 2 "Orange"

expect Dict.get dictionary 1 == Ok "Apple"
expect Dict.get dictionary 2000 == Err KeyNotFound

contains : Dict k v, k -> Bool where k implements Hash & Eq

Check if the dictionary has a value for a specified key.

expect
    Dict.empty {}
    |> Dict.insert 1234 "5678"
    |> Dict.contains 1234
    |> Bool.isEq Bool.true

insert : Dict k v, k, v -> Dict k v where k implements Hash & Eq

Insert a value into the dictionary at a specified key.

expect
    Dict.empty {}
    |> Dict.insert "Apples" 12
    |> Dict.get "Apples"
    |> Bool.isEq (Ok 12)

remove : Dict k v, k -> Dict k v where k implements Hash & Eq

Remove a value from the dictionary for a specified key.

expect
    Dict.empty {}
    |> Dict.insert "Some" "Value"
    |> Dict.remove "Some"
    |> Dict.len
    |> Bool.isEq 0

update : Dict k v, k, ( [ Present v, Missing ] -> [ Present v, Missing ]) -> Dict k v where k implements Hash & Eq

Insert or remove a value for a specified key. This function enables a performance optimization for the use case of providing a default when a value is missing. This is more efficient than doing both a Dict.get and then a Dict.insert call, and supports being piped.

alterValue : [Present Bool, Missing] -> [Present Bool, Missing]
alterValue = \possibleValue ->
    when possibleValue is
        Missing -> Present Bool.false
        Present value -> if value then Missing else Present Bool.true

expect Dict.update (Dict.empty {}) "a" alterValue == Dict.single "a" Bool.false
expect Dict.update (Dict.single "a" Bool.false) "a" alterValue == Dict.single "a" Bool.true
expect Dict.update (Dict.single "a" Bool.true) "a" alterValue == Dict.empty {}

toList : Dict k v -> List ( k, v ) where k implements Hash & Eq

Returns the keys and values of a dictionary as a List. This requires allocating a temporary list, prefer using Dict.toList or Dict.walk instead.

expect
    Dict.single 1 "One"
    |> Dict.insert 2 "Two"
    |> Dict.insert 3 "Three"
    |> Dict.insert 4 "Four"
    |> Dict.toList
    |> Bool.isEq [(1, "One"), (2, "Two"), (3, "Three"), (4, "Four")]

keys : Dict k v -> List k where k implements Hash & Eq

Returns the keys of a dictionary as a List. This requires allocating a temporary List, prefer using Dict.toList or Dict.walk instead.

expect
    Dict.single 1 "One"
    |> Dict.insert 2 "Two"
    |> Dict.insert 3 "Three"
    |> Dict.insert 4 "Four"
    |> Dict.keys
    |> Bool.isEq [1,2,3,4]

values : Dict k v -> List v where k implements Hash & Eq

Returns the values of a dictionary as a List. This requires allocating a temporary List, prefer using Dict.toList or Dict.walk instead.

expect
    Dict.single 1 "One"
    |> Dict.insert 2 "Two"
    |> Dict.insert 3 "Three"
    |> Dict.insert 4 "Four"
    |> Dict.values
    |> Bool.isEq ["One","Two","Three","Four"]

insertAll : Dict k v, Dict k v -> Dict k v where k implements Hash & Eq

Combine two dictionaries by keeping the union of all the key-value pairs. This means that all the key-value pairs in both dictionaries will be combined. Note that where there are pairs with the same key, the value contained in the second input will be retained, and the value in the first input will be removed.

first =
    Dict.single 1 "Not Me"
    |> Dict.insert 2 "And Me"

second =
    Dict.single 1 "Keep Me"
    |> Dict.insert 3 "Me Too"
    |> Dict.insert 4 "And Also Me"

expected =
    Dict.single 1 "Keep Me"
    |> Dict.insert 2 "And Me"
    |> Dict.insert 3 "Me Too"
    |> Dict.insert 4 "And Also Me"

expect
    Dict.insertAll first second == expected

keepShared : Dict k v, Dict k v -> Dict k v where k implements Hash & Eq

Combine two dictionaries by keeping the intersection of all the key-value pairs. This means that we keep only those pairs that are in both dictionaries. Note that where there are pairs with the same key, the value contained in the first input will be retained, and the value in the second input will be removed.

first =
    Dict.single 1 "Keep Me"
    |> Dict.insert 2 "And Me"

second =
    Dict.single 1 "Keep Me"
    |> Dict.insert 2 "And Me"
    |> Dict.insert 3 "But Not Me"
    |> Dict.insert 4 "Or Me"

expect Dict.keepShared first second == first

removeAll : Dict k v, Dict k v -> Dict k v where k implements Hash & Eq

Remove the key-value pairs in the first input that are also in the second using the set difference of the values. This means that we will be left with only those pairs that are in the first dictionary and whose keys are not in the second.

first =
    Dict.single 1 "Keep Me"
    |> Dict.insert 2 "And Me"
    |> Dict.insert 3 "Remove Me"

second =
    Dict.single 3 "Remove Me"
    |> Dict.insert 4 "I do nothing..."

expected =
    Dict.single 1 "Keep Me"
    |> Dict.insert 2 "And Me"

expect Dict.removeAll first second == expected