Tracks
/
Factor
Factor
/
Exercises
/
Purser's Pantry
Purser's Pantry

Purser's Pantry

Learning Exercise

Introduction

Hashtables in Factor are associative arrays — collections of key/value pairs with O(1) lookup. They're part of the wider assocs family.

Hashtable literals

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.

Reading

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

Writing

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 shortcut

inc-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 } }

Iteration and lazy insertion

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.

Applying a hashtable update across a sequence of keys

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 ..

Building a hashtable from a sequence

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, values, and pairs

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 } }

From pairs back to a hashtable

>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.

Instructions

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.

1. Build an inventory from a list

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 } }

2. Add more items

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 } }

3. Decrement counts

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 } }

4. Remove an item entirely

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 } }

5. List the available items

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 } }
Edit via GitHub The link opens in a new window or tab
Factor Exercism

Ready to start Purser's Pantry?

Sign up to Exercism to learn and master Factor with 47 concepts163 exercises, and real human mentoring, all for free.