Dict

Dict Builtin.Dict(k, v) :: # (opaque)

is_eq : Dict(k, v), Dict(k, v) -> Bool
    where [
        k.is_eq : k, k -> Bool,
        k.to_hash : k, Hasher -> Hasher,
        v.is_eq : v, v -> Bool,
    ]

Returns True if the two dictionaries contain the same key-value pairs, and False otherwise.

to_hash : Dict(k, v), Hasher -> Hasher
    where [
        k.to_hash : k, Hasher -> Hasher,
        v.to_hash : v, Hasher -> Hasher,
    ]

Feed a Dict into a Hasher. The hash is independent of insertion order.

empty : () -> Dict(_k, _v)

Returns an empty Dict.

empty_dict = Dict.empty()

with_capacity : U64 -> Dict(_k, _v)

Returns an empty Dict with room for at least the requested number of entries.

capacity : Dict(_k, _v) -> U64

Returns the number of entries the dictionary can hold before growing.

reserve : Dict(k, v), U64 -> Dict(k, v) where [k.to_hash : k, Hasher -> Hasher]

Ensure this dictionary has room for at least this many additional entries.

release_excess_capacity : Dict(k, v) -> Dict(k, v) where [k.to_hash : k, Hasher -> Hasher]

Reduce unused dictionary capacity.

clear : Dict(k, v) -> Dict(k, v)

Remove every entry while preserving the current capacity.

single : k, v -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

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

expect Dict.single("A", "B") == Dict.empty().insert("A", "B")

len : Dict(_k, _v) -> U64

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

expect Dict.empty()
           .insert("One", "A Song")
           .insert("Two", "Candy Canes")
           .insert("Three", "Boughs of Holly")
           .len() == 3

is_empty : Dict(_k, _v) -> Bool

Check if the dictionary is empty.

expect !Dict.empty().insert("key", 42).is_empty()

expect Dict.empty().is_empty()

get : Dict(k, v), k -> Try(v, [KeyNotFound, ..]) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

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

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

contains : Dict(k, _v), k -> Bool where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

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

expect Dict.empty().insert(1234, "5678").contains(1234)

insert : Dict(k, v), k, v -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Insert a value into the dictionary at a specified key. If the key already exists, the existing value is replaced.

expect Dict.empty()
           .insert("Apples", 12)
           .get("Apples") == Ok(12)

remove : Dict(k, v), k -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Remove a value from the dictionary for a specified key.

expect Dict.empty()
           .insert("Some", "Value")
           .remove("Some")
           .len() == 0

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

Returns the key-value pairs of a dictionary as a List.

expect Dict.single(1, "One")
           .insert(2, "Two")
           .to_list() == [(1, "One"), (2, "Two")]

from_list : List((k, v)) -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Create a Dict from a List of key-value pairs. If the list contains duplicate keys, later values overwrite earlier ones.

expect Dict.from_list([(1, "One"), (2, "Two")]) ==
	Dict.single(1, "One").insert(2, "Two")

keys : Dict(k, _v) -> List(k)

Returns the keys of a dictionary as a List.

expect Dict.single(1, "One")
           .insert(2, "Two")
           .keys() == [1, 2]

values : Dict(_k, v) -> List(v)

Returns the values of a dictionary as a List.

expect Dict.single(1, "One")
           .insert(2, "Two")
           .values() == ["One", "Two"]

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

Build a value by folding through each key-value pair in the dictionary. Starting with a given state value, this runs the given step function on each pair, using its return value as the new state. It returns the final state at the end.

expect Dict.empty()
           .insert("Apples", 12.U64)
           .insert("Oranges", 24)
           .fold(0, |count, _key, qty| count + qty) == 36

keep_if : Dict(k, v), ((k, v) -> Bool) -> Dict(k, v) where [k.to_hash : k, Hasher -> Hasher]

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()
           .insert("Alice", 17.U64)
           .insert("Bob", 18)
           .insert("Charlie", 19)
           .keep_if(|(_k, v)| v >= 18)
           .len() == 2

drop_if : Dict(k, v), ((k, v) -> Bool) -> Dict(k, v) where [k.to_hash : k, Hasher -> Hasher]

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()
           .insert("Alice", 17.U64)
           .insert("Bob", 18)
           .insert("Charlie", 19)
           .drop_if(|(_k, v)| v >= 18)
           .len() == 1

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.

expect Dict.empty()
           .insert("a", 1.I64)
           .insert("b", 2)
           .map(|_k, v| v * 10)
           == Dict.empty()
                  .insert("a", 10)
                  .insert("b", 20)

join_map : Dict(a, b), (a, b -> Dict(x, y)) -> Dict(x, y) where [x.is_eq : x, x -> Bool, x.to_hash : x, Hasher -> Hasher]

Like Dict.map, except the transformation function returns a dictionary. At the end, all the dictionaries are joined together (using Dict.insert_all) into one dictionary.

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

insert_all : Dict(k, v), Dict(k, v) -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Combine two dictionaries by keeping the union of all the key-value pairs. Where the same key is present in both dictionaries, the value from the second input is kept.

expect {
	first = Dict.single(1, "Not Me").insert(2, "And Me")
	second = Dict.single(1, "Keep Me").insert(3, "Me Too")
	expected = Dict.single(1, "Keep Me").insert(2, "And Me").insert(3, "Me Too")
	Dict.is_eq(Dict.insert_all(first, second), expected)
}

keep_shared : Dict(k, v), Dict(k, v) -> Dict(k, v)
    where [
        k.is_eq : k, k -> Bool,
        k.to_hash : k, Hasher -> Hasher,
        v.is_eq : v, v -> Bool,
    ]

Combine two dictionaries by keeping the intersection of all the key-value pairs. Only pairs where the key exists in both dictionaries and the values are equal are kept.

expect {
	first = Dict.single(1, "Keep Me").insert(2, "And Me").insert(3, "Not this one")
	second = Dict.single(1, "Keep Me").insert(2, "And Me").insert(3, "Different")
	expected = Dict.single(1, "Keep Me").insert(2, "And Me")

	Dict.is_eq(Dict.keep_shared(first, second), expected)
}

remove_all : Dict(k, v), Dict(k, _w) -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Remove the key-value pairs in the first input whose keys are also in the second using the set difference.

expect {
	first = Dict.single(1, "Keep Me").insert(2, "And Me").insert(3, "Remove Me")
	second = Dict.single(3, "Remove Me").insert(4, "I do nothing...")
	expected = Dict.single(1, "Keep Me").insert(2, "And Me")

	Dict.is_eq(Dict.remove_all(first, second), expected)
}

update : Dict(k, v), k, (Try(v, [Missing]) -> Try(v, [Missing])) -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Insert, update or remove a value for a specified key. This is more efficient than doing a Dict.get and then a Dict.insert call.

The provided function receives: - Ok(value) if the key is currently in the dictionary. - Err(Missing) if the key is not currently in the dictionary.

It should return: - Ok(new_value) to insert or update the value at the key. - Err(Missing) to remove the key (or leave it absent).

alter = |possible_value| match possible_value {
	Err(Missing) => Ok(Bool.False)
	Ok(value) => if value Err(Missing) else Ok(Bool.True)
}

expect Dict.is_eq(
	Dict.update(Dict.empty(), "a", alter),
	Dict.single("a", Bool.False),
)

DictBucket : { dist_and_fingerprint : U32, entry_index : U32 }

DictData : {
    entries : List((k, v)),
    buckets : List(DictBucket),
    max_entries_before_grow : U64,
    shifts : U8,
}

DictMetadata : {
    buckets : List(DictBucket),
    max_entries_before_grow : U64,
    shifts : U8,
}