Dict

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

Return an empty dictionary.

emptyDict = Dict.empty {}

capacity

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

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

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

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

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

clear

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

walk

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

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

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

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

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

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

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

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

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

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

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

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

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