Hashtables in Factor are associative arrays — collections of
key/value pairs with O(1) lookup. They're part of the wider
assocs family.
H{ { "coal" 1 } { "wood" 2 } } .
H{ } is an empty hashtable. Hashtables are mutable, growing and
shrinking as you add and remove keys — clone first if you need to
leave the original alone. Printing a hashtable shows its entries, but
the order isn't tied to insertion order — hashtables are unordered.
at (in assocs) reads a value, returning f if the key
is missing:
at ( key assoc -- value/f )
key? ( key assoc -- ? )
"coal" H{ { "coal" 1 } { "wood" 2 } } at . ! => 1
"gold" H{ { "coal" 1 } { "wood" 2 } } at . ! => f
set-at adds or overwrites; delete-at removes; change-at runs a
quotation over the current value. All three mutate:
set-at ( value key assoc -- )
delete-at ( key assoc -- )
change-at ( key assoc quot: ( old -- new ) -- )
H{ } clone 5 "coal" pick set-at .
! => H{ { "coal" 5 } }
inc-at — the count-up shortcutinc-at (also in assocs) adds 1 to the existing value for a key,
inserting it as 1 when missing. Perfect for tallying:
inc-at ( key assoc -- )
H{ } clone "coal" over inc-at .
! => H{ { "coal" 1 } }
assoc-each walks every ( key value -- ) pair; cache
returns the value for a key, computing it once with the
supplied quotation if the key is missing.
assoc-each ( assoc quot: ( key value -- ) -- )
cache ( key assoc quot: ( key -- value ) -- value )
cache is the "look up or create" pattern in one word — handy
when you're building a hashtable from a stream of keys and don't
want to handle the missing-entry case at every call site.
When the input is a sequence of keys and you want to update the
hashtable once per key, iterate the sequence with each and use
a fried quotation '[ _ … ] (from fry) to bake the
hashtable into the loop body. For example, removing a list of keys:
{ "wood" "iron" } H{ { "coal" 5 } { "wood" 3 } { "iron" 2 } } clone
[ '[ _ delete-at ] each ] keep .
! => H{ { "coal" 5 } }
'[ _ delete-at ] captures the hashtable above it on the stack so
that on every iteration each only needs to supply the key.
keep runs the quotation while preserving the hashtable for the
final ..
map>assoc (in assocs) maps a quotation over a sequence
and collects the ( elt -- key value ) results into an assoc of the
exemplar's type:
map>assoc ( seq quot: ( elt -- key value ) exemplar -- assoc )
{ "wood" } [ dup length ] H{ } map>assoc .
! => H{ { "wood" 4 } }
keys and values (in assocs) return just the keys or
just the values; >alist returns the { key value } pairs.
keys ( assoc -- keys )
values ( assoc -- values )
>alist ( assoc -- alist )
H{ { "wood" 11 } { "coal" 7 } } keys . ! the keys (order not guaranteed)
H{ { "wood" 11 } { "coal" 7 } } values . ! the matching values
keys and values line up: the value at a given position belongs to
the key at the same position.
sort-keys (in sorting) returns the { key value } pairs
sorted by key:
H{ { "wood" 11 } { "coal" 7 } } sort-keys .
! => { { "coal" 7 } { "wood" 11 } }
>hashtable (in hashtables) is the inverse of
>alist: it turns any assoc — most often an alist of
{ key value } pairs — into a hashtable with O(1) lookup.
>hashtable ( assoc -- hashtable )
{ { "coal" 7 } { "wood" 11 } } >hashtable .
! => H{ { "wood" 11 } { "coal" 7 } } (entry order not guaranteed)
Handy when you've assembled or transformed a list of pairs and want to fold it back into a hashtable to look entries up by key.
You're the ship's purser, managing the pantry inventory. The inventory is a hashtable where each key is an item name and the value is the quantity in stock.
Define create-inventory to take a sequence of item names and
return a hashtable that pairs each unique name with its count.
{ "coal" "wood" "wood" "diamond" "diamond" "diamond" } create-inventory .
! => H{ { "coal" 1 } { "wood" 2 } { "diamond" 3 } }
Define add-items to take an inventory and a sequence of items and
return a new inventory whose counts have been incremented for each
listed item. The original inventory should not be modified.
H{ { "coal" 1 } } { "wood" "iron" "coal" "wood" } add-items .
! => H{ { "coal" 2 } { "wood" 2 } { "iron" 1 } }
Define decrement-items to take an inventory and a sequence of
items and return a new inventory whose counts have been decreased
by one for each listed item. Counts must never fall below zero, and
items not already in the inventory should be left out (no negative
entries are inserted).
H{ { "coal" 3 } { "diamond" 1 } { "iron" 5 } }
{ "diamond" "coal" "iron" "iron" } decrement-items .
! => H{ { "coal" 2 } { "diamond" 0 } { "iron" 3 } }
Define remove-item to take an inventory and an item and return a
new inventory with that item removed. If the item isn't present,
return an unchanged copy.
H{ { "coal" 2 } { "wood" 1 } { "diamond" 2 } } "coal" remove-item .
! => H{ { "wood" 1 } { "diamond" 2 } }
Define list-inventory to take an inventory and return an array of
{ name quantity } pairs containing only the items whose quantity
is greater than zero, sorted alphabetically by name.
H{ { "coal" 7 } { "wood" 11 } { "diamond" 2 } { "iron" 7 } { "silver" 0 } }
list-inventory .
! => { { "coal" 7 } { "diamond" 2 } { "iron" 7 } { "wood" 11 } }
Sign up to Exercism to learn and master Factor with 47 concepts163 exercises, and real human mentoring, all for free.