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:
- Call
Dict.insert
passing a key and a value, to associate that key with that value in the dictionary. - 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