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.

population_by_city =
    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:

population_by_city
    |> 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 almost identical to ankerl::unordered_dense. 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.

empty_dict = Dict.empty({})

with_capacity : U64 -> 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.

reserve : Dict k v, U64 -> Dict k v

Enlarge the dictionary for at least capacity additional elements

release_excess_capacity : Dict k v -> Dict k v

Shrink the memory footprint of a dictionary such that capacity is as small as possible. This function will require regenerating the metadata if the size changes. There will still be some overhead due to dictionary metadata always being a power of 2.

capacity : Dict * * -> U64

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

food_dict =
    Dict.empty({})
    |> Dict.insert("apple", "fruit")

capacity_of_dict = Dict.capacity(food_dict)

single : k, v -> Dict k v

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

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

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

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.is_eq(Dict.from_list([(1, "One"), (2, "Two"), (3, "Three"), (4, "Four")]))

Performance Details

This will build up from an empty dictionary to minimize totally memory use. If the list has few duplicate keys, it would be faster to allocate a dictionary with the same capacity of the list and walk it calling Dict.insert

len : Dict * * -> U64

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.is_eq(3)

is_empty : Dict * * -> Bool

Check if the dictionary is empty.

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

Dict.is_empty(Dict.empty({}))

clear : Dict k v -> Dict k v

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")

clear_songs = Dict.clear(songs)

expect Dict.len(clear_songs) == 0

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

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.

join_map : Dict a b, (a, b -> Dict x y) -> Dict x y

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.insert_all) into one dictionary.

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

walk : Dict k v, state, (state, k, v -> state) -> state

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.is_eq(36)

walk_until : Dict k v, state, (state, k, v -> [ Continue state, Break state ]) -> state

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)

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

someone_is_an_adult = Dict.walk_until(people, Bool.false, is_adult)

expect someone_is_an_adult == Bool.true

keep_if : Dict k v, ( ( k, v ) -> Bool) -> Dict k v

Run the given function on each key-value pair of a dictionary, and return a dictionary with just the pairs for which the function returned Bool.true.

expect Dict.empty({})
    |> Dict.insert("Alice", 17)
    |> Dict.insert("Bob", 18)
    |> Dict.insert("Charlie", 19)
    |> Dict.keep_if(\(_k, v) -> v >= 18)
    |> Dict.len
    |> Bool.is_eq(2)

drop_if : Dict k v, ( ( k, v ) -> Bool) -> Dict k v

Run the given function on each key-value pair of a dictionary, and return a dictionary with just the pairs for which the function returned Bool.false.

expect Dict.empty({})
    |> Dict.insert("Alice", 17)
    |> Dict.insert("Bob", 18)
    |> Dict.insert("Charlie", 19)
    |> Dict.drop_if(\(_k, v) -> v >= 18)
    |> Dict.len
    |> Bool.is_eq(1)

get : Dict k v, k -> Result v [KeyNotFound]

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,s "Apple")
    |> Dict.insert(2,s "Orange")

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

contains : Dict k v, k -> Bool

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

expect
    Dict.empty({})
    |> Dict.insert(1234, "5678")
    |> Dict.contains(1234)
    |> Bool.is_eq(Bool.true)

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

Insert a value into the dictionary at a specified key.

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

remove : Dict k v, k -> Dict k v

Remove a value from the dictionary for a specified key.

expect
    Dict.empty({})
    |> Dict.insert("Some", "Value")
    |> Dict.remove("Some")
    |> Dict.len
    |> Bool.is_eq(0)

update : Dict k v, k, (Result v [Missing] -> Result v [Missing]) -> Dict k v

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.

alter_value : Result Bool [Missing] -> Result Bool [Missing]
alter_value = \possible_value ->
    when possible_value is
        Err Missing -> Ok(Bool.false)
        Ok value -> if value then Err(Missing) else Ok(Bool.true)

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

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

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

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

keys : Dict k v -> List k

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

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

values : Dict k v -> List v

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

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

insert_all : Dict k v, Dict k v -> Dict k v

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.insert_all(first, second) == expected

keep_shared : Dict k v, Dict k v -> Dict k v where v implements 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. Both the key and value must match to be kept.

first =
    Dict.single(1, "Keep Me")
    |> Dict.insert(2, "And Me")
    |> Dict.insert(3, "Not this one")

second =
    Dict.single(1, "Keep Me")
    |> Dict.insert(2, "And Me")
    |> Dict.insert(3, "This has a different value")
    |> Dict.insert(4, "Or Me")

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

expect Dict.keep_shared(first, second) == expected

remove_all : Dict k v, Dict k v -> Dict k v

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.remove_all(first, second) == expected