std.hashtable

Maps from keys to values by the keys’ hashes, in flat arrays: open addressing, as Rust’s, Go’s and Python’s tables are. Import it by a name, import std.hashtable as HashTable (HashTable.insert); its names and their shapes are std.hashmap’s, so that one is changed for the other by the import.

import std.hashmap as HashMap
import std.hashtable as HashTable

-- | >>> HashTable.lookup (counted ["a", "b", "a"]) "a"
-- | Just 2
counted : List String -> HashTable.HashTable String Int
counted ws =
  List.foldl (\t w -> HashTable.update t w 1 (\new old -> new + old)) HashTable.empty ws

A table is three arrays as long as its slots, a power of 2: each slot’s key’s hash (0 where the slot is empty), its key and its value. A key starts at the slot its hash’s bits choose and goes on to the next while that one is taken (linear probing); a slot’s hash is compared before its key, so that another key is seldom looked at. Past 7/8 of the slots taken, the table doubles; withCapacity makes room at once. A key removed takes the keys after it, that started before it, back a slot, so that removing leaves nothing behind.

Where nothing else holds the table, a change is made in its arrays in place, a key found in one or two slots, side by side in memory: for a table one owner fills and reads (counting, an index), it is faster than std.hashmap’s trie, and smaller. But where something else holds it — an old version kept, the table put in two places — a change copies all its slots first, where std.hashmap’s copies one path. Keep the old versions of a map in std.hashmap.

The keys’ type has a Hash (std.hashmap’s: strings, integers, runes, booleans, pairs, lists and Maybes of them) and an Equality, each found as an instance argument is: import std.hashmap too, for its instances of Hash to be in scope. The order of toList, foldl and for is the slots’: the same on every backend, but of how the table came to be (what was bound and removed, in which order, and how many slots it has), not of what it binds: two tables of the same keys may list them in two orders, and are equal all the same. std.hashmap’s order is of the keys’ hashes alone.

HashTable

data HashTable k v = MkHashTable Int (Array Int) (Array k) (Array v)

A table: how many keys it binds; each slot’s key’s hash, made odd (0: an empty slot); each slot’s key, and value. (A slot that is empty holds a key and a value of the table’s, the first it was given, kept after the last slot as well, so that removing a key lets it go.)

empty

empty : {k v : Type} -> HashTable k v

The table of no keys (and no slots: the first key bound makes 8).

withCapacity

withCapacity : {k v : Type} -> Int -> HashTable k v

The table of no keys, with slots enough for n, so that so many keys bound do not grow it.

update

update : {k v : Type}
       -> {{hashing : HashMap.Hash k}}
       -> {{equality : Equality k}}
       -> HashTable k v
       -> k
       -> v
       -> (v -> v -> v)
       -> HashTable k v

The table with k bound to v, or, where it is bound, to f v old (Haskell’s insertWith): a value changed in its slot.

insert

insert : {k v : Type}
       -> {{hashing : HashMap.Hash k}}
       -> {{equality : Equality k}}
       -> HashTable k v
       -> k
       -> v
       -> HashTable k v

The table with k bound to v (instead of what it was, if it was).

lookup

lookup : {k v : Type}
       -> {{hashing : HashMap.Hash k}}
       -> {{equality : Equality k}}
       -> HashTable k v
       -> k
       -> Maybe v

What k is bound to, if it is.

remove

remove : {k v : Type}
       -> {{hashing : HashMap.Hash k}}
       -> {{equality : Equality k}}
       -> HashTable k v
       -> k
       -> (Maybe v, HashTable k v)

What k was bound to, if it was, and the table without it (Rust’s remove): a delete that says whether the key was there.

delete

delete : {k v : Type}
       -> {{hashing : HashMap.Hash k}}
       -> {{equality : Equality k}}
       -> HashTable k v
       -> k
       -> HashTable k v

The table without k (as it was, if k was not in it; remove says which).

alter

alter : {k v : Type}
      -> {{hashing : HashMap.Hash k}}
      -> {{equality : Equality k}}
      -> HashTable k v
      -> k
      -> (Maybe v -> Maybe v)
      -> HashTable k v

The table with k bound as f says, given what it is bound to, if it is: to f’s value, or (Nothing) to none (Haskell’s alter).

foldl

foldl : {k v b : Type} -> (b -> k -> v -> b) -> b -> HashTable k v -> b

Each key and its value, from z, in the slots’ order.

size

size : {k v : Type} -> HashTable k v -> Int

How many keys are bound: kept as they are bound and removed, not counted.

toList

toList : {k v : Type} -> HashTable k v -> List (k, v)

The keys and their values, in the slots’ order (of how the table came to be, not of the keys): sort them for another.

member

member : {k v : Type}
       -> {{hashing : HashMap.Hash k}}
       -> {{equality : Equality k}}
       -> HashTable k v
       -> k
       -> Bool

Whether k is bound in it.

>>> List.map (member (insert (empty : HashTable String Int) "a" 1)) ["a", "b"]
Cons True (Cons False Nil)

keys

keys : {k v : Type} -> HashTable k v -> List k

The keys, in toList’s order.

>>> keys (insert (empty : HashTable String Int) "a" 1)
Cons "a" Nil

values

values : {k v : Type} -> HashTable k v -> List v

The values, in toList’s order.

>>> values (insert (empty : HashTable String Int) "a" 1)
Cons 1 Nil

Slots

data Slots k v = MkSlots Int (Array Int) (Array k) (Array v)

instanceIterateHashTable

instance instanceIterateHashTable : {k v : Type} -> Iterate (HashTable k v)

A hash table, each key and its value in the slots’ order, as toList has them: for p in t goes through the slots.

fromList

fromList : {k v : Type}
         -> {{hashing : HashMap.Hash k}}
         -> {{equality : Equality k}}
         -> List (k, v)
         -> HashTable k v

The table of the pairs, a later one’s value for a key twice.

>>> lookup (fromList [MkPair "a" 1, MkPair "b" 2]) "b"
Just 2
>>> lookup (fromList [MkPair "a" 1, MkPair "b" 2]) "c"
Nothing
>>> lookup (insert (fromList [MkPair 2 "deux"]) 2 "two") 2
Just "two"
>>> size (fromList [MkPair "a" 1, MkPair "b" 2, MkPair "a" 3])
2
>>> foldl (\n k v -> n + k * v) 0 (fromList [MkPair 2 3, MkPair 4 5])
26
>>> List.sortOn (\p -> fst p) (toList (fromList [MkPair "b" 2, MkPair "a" 1]))
Cons (MkPair "a" 1) (Cons (MkPair "b" 2) Nil)
>>> toList (update (fromList [MkPair "a" 2]) "a" 1 (\new old -> new + old))
Cons (MkPair "a" 3) Nil
>>> lookup (update (fromList [MkPair "a" 2]) "b" 5 (\new old -> new + old)) "b"
Just 5
>>> toList (delete (fromList [MkPair "a" 1, MkPair "b" 2]) "a")
Cons (MkPair "b" 2) Nil
>>> size (delete (fromList [MkPair 1 "one"]) 7)
1
>>> size (delete (fromList [MkPair 1 "one", MkPair 2 "two"]) 1)
1
>>> fst (remove (fromList [MkPair "a" 1, MkPair "b" 2]) "a")
Just 1
>>> fst (remove (insert (empty : HashTable String Int) "a" 1) "c")
Nothing
>>> toList (snd (remove (fromList [MkPair "a" 1, MkPair "b" 2]) "a"))
Cons (MkPair "b" 2) Nil
>>> size (alter (fromList [MkPair 1 "one"]) 2 (\old -> Just "two"))
2
>>> toList (alter (fromList [MkPair "a" 2]) "a" (\old -> Just (maybe 1 (\n -> n + 1) old)))
Cons (MkPair "a" 3) Nil
>>> toList (alter (fromList [MkPair 1 "one"]) 1 (\old -> Nothing))
Nil
>>> lookup (alter (fromList [MkPair 1 "one"]) 3 (\old -> Just "three")) 3
Just "three"
>>> size (insert (withCapacity 100) "a" 1)
1

instanceEqualityHashTable

instance instanceEqualityHashTable : {k v : Type}
                                   -> {{hashing : HashMap.Hash k}}
                                   -> {{eqKey : Equality k}}
                                   -> {{eqValue : Equality v}}
                                   -> Equality (HashTable k v)

Two tables are equal where they bind the same keys, each to equal values, in whatever order their slots have them.

>>> equal (fromList [MkPair 1 "a", MkPair 2 "b"]) (fromList [MkPair 2 "b", MkPair 1 "a"])
True
>>> equal (fromList [MkPair 1 "a"]) (fromList [MkPair 1 "b"])
False
>>> equal (fromList [MkPair 1 "a"]) (fromList [MkPair 1 "a", MkPair 2 "b"])
False

instanceDebugHashTable

instance instanceDebugHashTable : {k v : Type}
                                -> {{showsKey : Debug k}}
                                -> {{showsValue : Debug v}}
                                -> Debug (HashTable k v)

A table as fromList of its pairs, in the slots’ order.

>>> debug (insert (empty : HashTable String Int) "a" 1)
"fromList [MkPair (\"a\") (1)]"

updateBy

updateBy : {k v q : Type}
         -> {{view : HashMap.KeyView k q}}
         -> HashTable k v
         -> q
         -> v
         -> (v -> v -> v)
         -> HashTable k v

update of the key a view stands for (std.hashmap’s KeyView): the key made of it only where it is new to the table, so that counting the parts of a string (HashMap.slice), most of them there already, makes no string for those.

>>> lookup (updateBy (fromList [MkPair "ab" 1]) (HashMap.slice "xaby" 1 3) 5 (\new old -> new + old)) "ab"
Just 6
>>> toList (updateBy (empty : HashTable String Int) (HashMap.slice "xaby" 1 3) 5 (\new old -> new + old))
Cons (MkPair "ab" 5) Nil

lookupBy

lookupBy : {k v q : Type}
         -> {{view : HashMap.KeyView k q}}
         -> HashTable k v
         -> q
         -> Maybe v

lookup of the key a view stands for (std.hashmap’s KeyView), no key made.

>>> lookupBy (fromList [MkPair "ab" 1]) (HashMap.slice "xaby" 1 3)
Just 1
>>> lookupBy (fromList [MkPair "ab" 1]) (HashMap.slice "xaby" 1 2)
Nothing