Generated from /std/table.deed and the module's own tests.
A keyed table, written in Deed.
examples/logs.deed counts how many times it has seen each level and each
source, and doing that with a plain list took two walks and a branch: one to
find out whether the key was already there, another to bump it, and a
separate case to add it the first time. That is the shape a table is for,
and the question is where a table belongs.
Not in the prelude. The test for that is whether it can be written here, the
same test trim passed and contains failed, and this file is the answer:
it can. A record takes type parameters, a fn takes type parameters, and
a for walks the list underneath. The compiler knows nothing about any of
this.
What it costs is what a list costs. Every lookup walks, so a table of a thousand keys does a thousand comparisons, and the log analyser has a handful of levels and a handful of sources. When something here holds enough keys for that to matter, the answer is a better table rather than a different language, and that is the point of this file being in Deed.
Measured rather than argued (#614, crates/deed-driver/examples/interpreting.rs):
a lookup or an insert of a key not already there costs about 350ns per key
already in the table, flat across 16, 64, 256 and 1024 keys, which is the
straight line the shape above predicts rather than something worse. set
costs about the same as or_else because it does the same walk holds
does before copying. Below a few hundred keys this is noise next to
anything reading a line of input; past a few thousand it is the slowest
part of a program that uses one, which is the number a tree would need to
beat rather than an assumption about when a tree is worth having.
One invariant holds it together: a key appears at most once. set is the
only way anything gets in and it replaces rather than appends, so get can
stop caring which match it finds because there is only ever one.
It lived under examples/ to begin with, and a module's name says where it
lives, so the only way to import it was use examples/table and a program
outside this repository had to copy the file. Nothing about the table
changed to fix that. It ships now, so the name a program writes is the name
it has here.
Whether anything under this key is already here.
Stops at the first match, which is what a while on the accumulator is for:
the answer cannot change once it is true.
fn holds<K, V>(entries: Table<K, V>, key: K) -> Bool
none
pure
pure
assert holds(t, "b") == false
assert holds(t, "a")
assert holds(empty, "a") == false
assert holds(without, "b") == false
What is under this key, or an error saying there is nothing.
A Result rather than a value, for the reason at hands one back: a key
that is not there is not a mistake in the caller, and nothing in this
language traps.
fn get<K, V>(entries: Table<K, V>, key: K) -> Result<V, String>
none
pure
pure
assert get(t, "a") == ok(1)
assert get(t, "b") == ok(2)
assert get(t, "a") == ok(9)
assert get(t, "b") == err("no such key")
assert get(twice, "e") == ok(2)
assert get(t, 20) == ok("twenty")
This key holding this value, whether or not it held one before.
Replaces rather than appends, which is the invariant every other function here leans on.
fn set<K, V>(entries: Table<K, V>, key: K, value: V) -> Table<K, V>
none
pure
pure
let t = set(set([], "a", 1), "b", 2)
let t = set(set([], "a", 1), "a", 9)
let t = set([], "a", 1)
let once = set(empty, "e", or_else(empty, "e", 0) + 1)
let twice = set(once, "e", or_else(once, "e", 0) + 1)
let t = set(set(set([], "a", 1), "b", 2), "c", 3)
let t = set(set([], 10, "ten"), 20, "twenty")
let t = set(set(set([], "a", 1), "b", 2), "c", 3)
What is under this key, or fallback if there is nothing.
The shape a counter wants: set(t, k, or_else(t, k, 0) + 1) adds the first
one and bumps the rest without asking which case it is in.
fn or_else<K, V>(entries: Table<K, V>, key: K, fallback: V) -> V
none
pure
pure
let once = set(empty, "e", or_else(empty, "e", 0) + 1)
let twice = set(once, "e", or_else(once, "e", 0) + 1)
Every key in insertion order.
Replacing a value keeps the key where it was, because set rewrites in
place rather than removing and appending.
fn keys<K, V>(entries: Table<K, V>) -> List<K>
none
pure
pure
assert keys(t) == ["a", "b", "c"]
assert keys(t) == [10, 20]
assert keys(empty) == []
assert keys(without) == ["a", "c"]
Every value in the same order keys answers its keys.
fn values<K, V>(entries: Table<K, V>) -> List<V>
none
pure
pure
assert values(t) == [1, 2, 3]
assert values(empty) == []
assert values(without) == [1, 3]
How many entries are in the table.
The count is the underlying list's length, which is also the reason lookup cost stays linear in the number of keys.
fn size<K, V>(entries: Table<K, V>) -> Int
none
pure
pure
assert size(t) == 2
assert size(t) == 1
assert size(twice) == 1
assert size(empty) == 0
assert size(without) == 2
Without this key, whether or not it was there. Missing is quiet: the table
after is the table that does not hold the key, and asking twice is the same
as asking once. set is the only way anything gets in; this is the only way
anything gets out.
fn remove<K, V>(entries: Table<K, V>, key: K) -> Table<K, V>
none
pure
pure
let without = remove(t, "b")
assert remove(without, "b") == without
assert remove([], "a") == []