| name | data-structures |
| description | Master Hoon's built-in data structures including lists, sets, maps, mops (ordered maps), jars, jugs, and trees with their operations and performance characteristics. Use when choosing data structures, optimizing algorithms, building complex applications, or understanding standard library collections. |
| user-invocable | true |
| disable-model-invocation | false |
| validated | safe |
| checked-by | ~sarlev-sarsen |
Data Structures Skill
Master Hoon's built-in data structures including lists, trees, sets, maps, mops
(ordered maps), queues, jars, and jugs. Use when choosing data structures,
optimizing algorithms, or building complex applications.
Overview
Hoon provides functional data structures built on the noun foundation. This
skill covers the eight standard containers — list, tree, set, map,
mop, qeu, jar, jug — with their engine cores and conversions.
set, map, qeu, mop, jar, and jug are all treap-shaped: a treap
is a binary tree that is simultaneously a search tree (horizontally, by key) and
a heap (vertically, by the +mug hash of the key, via +mor). The validated
molds wrap a tree as $|((tree …) …apt…). Each container has a door
(+in, +by, +to, +on, +ja, +ju) holding its operation arms.
Most stdlib containers live in hoon.hoon and are documented in the stdlib
pages (2h–2o). The ordered map (+mop / +on) is defined in Zuse and
documented in hoon/zuse/2m.md. That is purely a citation difference — mop is
a first-class container with the same standing as the others.
| Container | Mold | Engine door | Reference |
|---|
| list | (list a) | (list functions, 2b) | stdlib 2b |
| tree | (tree a) | — | stdlib 1c |
| set | (set a) | +in | stdlib 2h, 2o |
| map | (map k v) | +by | stdlib 2i, 2o |
| mop | ((mop k v) cmp) | +on | zuse 2m |
| qeu | (qeu a) | +to | stdlib 2k, 2o |
| jar | (jar k v) | +ja | stdlib 2j, 2o |
| jug | (jug k v) | +ju | stdlib 2j, 2o |
Learning Objectives
- Choose appropriate data structures for tasks
- Perform efficient operations on each structure
- Understand performance trade-offs
- Use standard library functions effectively
- Convert between containers
- Use ordered maps (
mop) for ordered, historical, and range access
1. Lists
Structure
Lists are null-terminated linked lists:
+$ list [item]
$@(~ [i=item t=(list item)])
:: Examples
~ :: Empty list (null)
~[1] :: [i=1 t=~]
~[1 2 3] :: [i=1 t=[i=2 t=[i=3 t=~]]]
Construction
:: Empty list
~
*(list @ud)
:: From elements
~[1 2 3 4 5]
:: Cons (prepend)
[0 ~[1 2 3]] :: ~[0 1 2 3]
:: Convert from other structures
~(tap in (silt ~[3 1 2])) :: Set → list
~(tap by (my ~[[%a 1]])) :: Map → list of pairs
Accessing i. and t. — CRITICAL RULE
(list a) is the fork $@(~ [i=a t=(list a)]). The faces i and t only
exist in the non-null branch. The only rune that narrows a list to its
non-null variant and makes i. and t. accessible is ?~.
lent comparisons, ?= assertions, and ?. guards on lent do NOT narrow
the type. Using i. after any of these will produce a find-fork error.
:: WRONG — lent does not narrow the type; find-fork on i.xs
?. =(1 (lent xs))
!!
=/ head i.xs :: find-fork!
:: CORRECT — ?~ narrows to non-null; i. and t. are now valid
?~ xs
~|("empty" !!)
=/ head i.xs :: ok
:: Exactly-one check: ?~ first, then check t. is ~
?~ xs
~|("empty" !!)
?. =(~ t.xs)
~|("more than one" !!)
=/ only i.xs :: ok — xs has exactly one element
Deep wings and find-fork
Even after ?~ narrows a list, accessing a face inside i. via a deep wing
path (e.g. data.i.some-list) can still produce find-fork when the
compiler encounters multiple data faces in the subject (e.g. if both
indexed-row and joined-row in scope both have a data field).
Fix: bind i.xs to an explicitly-typed intermediate first, then access
the face on that binding:
:: WRONG — find-fork if 'data' appears in multiple types in scope
=/ val (~(got by data.i.indexed-rows.st) col-name)
:: CORRECT — bind to typed intermediate; data.irow is unambiguous
=/ irow=indexed-row i.indexed-rows.st
=/ val (~(got by data.irow) col-name)
Core Operations
(lent ~[1 2 3 4]) :: 4 length
(flop ~[1 2 3]) :: ~[3 2 1] reverse
(weld ~[1 2] ~[3 4]) :: ~[1 2 3 4] concatenate
(snoc ~[1 2 3] 4) :: ~[1 2 3 4] append (O(n) — avoid in loops!)
(scag 2 ~[1 2 3 4]) :: ~[1 2] take first N
(slag 2 ~[1 2 3 4]) :: ~[3 4] drop first N
(snag 2 ~[10 20 30]) :: 30 element at index (0-indexed)
(find ~[2 3] ~[1 2 3 4]) :: [~ 1] index of sublist, as a unit
Higher-Order Functions
:: Map (transform each)
(turn ~[1 2 3] |=(n=@ud (mul n 2))) :: ~[2 4 6]
:: Filter (keep matching)
(skim ~[1 2 3 4 5] |=(n=@ud =(0 (mod n 2)))) :: ~[2 4]
:: Reject (remove matching)
(skip ~[1 2 3 4 5] |=(n=@ud =(0 (mod n 2)))) :: ~[1 3 5]
:: Fold left (accumulate)
(roll ~[1 2 3 4] |=([n=@ud acc=@ud] (add acc n))) :: 10
:: Fold right
(reel ~[1 2 3 4] |=([n=@ud acc=@ud] (add n acc))) :: 10
Prefer turn to extract or transform a field across a list; never hand-roll
|- recursion for that. Example: (turn cases |=(c=case-when-then:ast when.c)).
Performance
| Operation | Cost |
|---|
| Prepend (cons) / head / tail | constant |
| Length / index / search / append | linear |
| Concatenate | linear in both inputs |
Best for: Sequential access, stacks, small collections.
Avoid for: Random access, frequent appends, large lookup-heavy datasets.
2. Trees
Structure
The tree is the binary-tree foundation under sets, maps, queues, and mops:
++ tree
|$ [node]
$@(~ [n=node l=(tree node) r=(tree node)])
A node n, with left l and right r subtrees, or ~ for empty.
You rarely build a bare tree directly. The standard containers wrap a tree
with a validating mold and an engine door, of the form
$|((tree …) |=(a (tree)) …apt…) — a tree plus a correctness check. Knowing
the shape helps read pretty-printed output and balance/ordering arms
(+apt, +mor).
3. Sets — +in
Structure
A +set is an unordered treap of unique items:
++ set |$ [item] $|((tree item) |=(a=(tree) ?:(=(~ a) & ~(apt in a))))
Construction
*(set @ud) :: empty
(silt ~[1 2 3 2 1]) :: {1 2 3} from list (dedups)
(~(put in *(set @ud)) 1)
Core Operations (+in)
=/ s (silt ~[1 2 3 4 5])
(~(has in s) 3) :: %.y membership
(~(put in s) 6) :: add element
(~(del in s) 3) :: remove element
~(tap in s) :: list (unordered)
~(wyt in s) :: 5 size
(~(gas in s) ~[6 7]) :: insert many
:: map / fold over a set
(~(run in s) |=(n=@ud (mul n 2))) :: {2 4 6 8 10}
(~(rep in s) |=([n=@ud acc=@ud] (add n acc))) :: 15
:: set algebra
(~(int in (silt ~[1 2 3])) (silt ~[2 3 4])) :: {2 3} intersection
(~(uni in (silt ~[1 2 3])) (silt ~[3 4 5])) :: {1..5} union
(~(dif in (silt ~[1 2 3])) (silt ~[2 3 4])) :: {1} difference
| Operation | Cost |
|---|
| has / put / del | logarithmic (treap) |
| uni / int / dif | linear in inputs |
| tap / wyt | linear |
Best for: Unique elements, membership testing, set algebra.
Avoid for: Associating data with keys (use map), ordered iteration, or
preserving insertion order — ~(tap in) order is hash order, not insertion.
4. Maps — +by
Structure
A +map is a treap of key-value pairs, ordered by +mug hash of the key:
++ map
|$ [key value]
$| (tree (pair key value))
|=(a=(tree (pair)) ?:(=(~ a) & ~(apt by a)))
Construction
*(map @tas @ud) :: empty
(my ~[[%a 1] [%b 2] [%c 3]]) :: from a literal pair list
(malt key-value-list) :: from a (list [key value])
(~(put by *(map @tas @ud)) %a 1)
Core Operations (+by)
=/ m (my ~[[%a 1] [%b 2] [%c 3]])
(~(get by m) %a) :: [~ 1] lookup → unit
(~(got by m) %a) :: 1 lookup, crash if missing
(~(gut by m) %z 0) :: 0 lookup with default
(~(has by m) %a) :: %.y key exists?
(~(put by m) %d 4) :: insert / update
(~(del by m) %b) :: remove
~(tap by m) :: ~[[%a 1] [%b 2] [%c 3]] list of pairs
~(key by m) :: {%a %b %c} set of keys
~(val by m) :: ~[1 2 3] list of values
(~(gas by m) ~[[%d 4] [%e 5]]) :: insert many
:: transform
(~(run by m) |=(v=@ud (mul v 2))) :: values → values
(~(urn by m) |=([k=@tas v=@ud] (add v 10))) :: over key+value
(~(rep by m) |=([[k=@tas v=@ud] acc=@ud] (add v acc))) :: fold
:: combine (right operand wins on key conflict for uni)
(~(uni by (my ~[[%a 1]])) (my ~[[%a 10] [%b 2]])) :: {[%a 10] [%b 2]}
(~(int by (my ~[[%a 1] [%b 2]])) (my ~[[%b 20]])) :: {[%b 2]} (left vals)
(~(dif by (my ~[[%a 1] [%b 2]])) (my ~[[%b 20]])) :: {[%a 1]}
| Operation | Cost |
|---|
| get / got / gut / has / put / del | logarithmic (treap) |
| tap / run / urn / rep / key / val | linear |
Best for: Key-value storage, dictionaries, caches, indexed data — when key
ordering does not matter.
Avoid for: Ordered iteration, ranges, min/max, or "as-of" lookups — ~(tap by) yields hash order, not key order. Use a mop for any of those.
5. Mops (Ordered Maps) — +on
A +mop is a treap of key-value pairs ordered by a comparator gate of your
choosing, rather than by the +mug hash of the key. It is defined in Zuse,
not the core stdlib; +on (alias +ordered-map) is its operation door.
Why the comparator is part of construction
++ mop
|* [key=mold value=mold]
|= ord=$-([key key] ?) :: comparator gate baked into the mold
|= a=* ... ?> (apt:((on key value) ord) b) b
The comparator $-([key key] ?) returns %.y if its first argument should sort
before the second. It defines the tree's horizontal order, so it is supplied
both when building the mold and when building the operation door — and the two
must be the same gate. Construct with ((mop key value) cmp) and operate
with ((on key value) cmp).
Warning: a mop is corrupt if two keys can be unequal under noun equality
yet equal under the comparator. The comparator must impose a strict total
order on keys — total (any two distinct keys compare), and strict (never
report %.y in both directions, i.e. no ties). A non-strict or partial
comparator silently breaks lookups and traversal.
Construction
:: empty mop, ascending @ keys
*((mop @ @) lth)
:: operation door bound to the same comparator
=/ m-on ((on @ @) lth)
:: build by inserting key^value pairs with gas (or put one at a time)
=/ m (gas:m-on *((mop @ @) lth) ~[1^10 2^20 3^30])
(tap:m-on m) :: ~[[key=1 val=10] [key=2 val=20] [key=3 val=30]] in key order
There is no +malt-style constructor for mops — ordinary map constructors
produce hash order and will fail the mop's +apt check. Build with gas:on /
put:on, and never read a mop with the +by map door.
Core Operations (+on)
=/ on ((on @ @) gth) :: descending keys
=/ m (gas:on *((mop @ @) gth) ~[1^1 2^2 3^3 4^4 5^5])
:: lookup
(get:on m 3) :: [~ 3] value at key → unit
(got:on m 3) :: 3 crash if missing
(has:on m 3) :: %.y
:: insert / delete
(put:on m 7 7) :: add/replace one pair
(gas:on m ~[6^6 7^7]) :: add many
(del:on m 2) :: [(unit val) mop] produces deleted value + new mop
:: ends and ordered traversal
(pry:on m) :: (unit item) leftmost (head) item
(ram:on m) :: (unit item) rightmost (tail) item
(pop:on m) :: [head=item rest=mop] pop leftmost, crash if empty
(tap:on m) :: (list item) left-to-right
(bap:on m) :: (list item) right-to-left
:: range / window
(lot:on m `4 ~) :: subset with keys strictly past `4` (start/end exclusive)
(lot:on m `3 `7) :: subset strictly between 3 and 7
(tab:on m `4 100) :: up to N items starting after key `4
:: bulk
(run:on m succ) :: transform every value in place
(all:on m |=([k=@ v=@] (gte 3 v))) :: logical AND over items
(any:on m |=([k=@ v=@] =(1 v))) :: logical OR over items
lot and tab give range/window access — the reason to reach for a mop over a
map. pry/pop/ram give cheap min/max/head-pop because items are kept in
comparator order.
| Operation | Cost |
|---|
| get / got / has / put / del | logarithmic (treap) |
| pry / ram / pop | logarithmic (descend one edge) |
| lot / tab / tap / bap / run / all / any | linear in the range or map |
When to use mop instead of map
- Ordered keys — you need to iterate or output in key order.
- Historical / time-travel lookup — key by
@da; fetch "the latest at or
before T" with a range query.
- Index structures — secondary indexes keyed by composite sort keys.
- Time series — append-ordered events, scanned by time window.
- Range-adjacent access — "next/previous", "first N after K", min/max.
If you only ever look up by exact key and never care about order, a plain map
is simpler.
Obelisk pattern: rebuilding a primary-key index
Real-world (desk/lib/crud.hoon, generalized). The primary index is a
((mop (list @) (map @tas @)) comparator) whose comparator is derived per-table
from the key columns via ~(order idx-comp …). To re-key after a mutation, build
an empty mop with that comparator and gas the row pairs in:
:: comparator built from the table's key-column descriptors
=/ comparator
~(order idx-comp `(list [@ta ?])`(reduce-key key.pri-indx.table))
:: pri-key wraps ((on (list @tas) (map @tas @)) comparator)
=/ primary-key (pri-key key.pri-indx.table)
=. pri-idx.file
%+ gas:primary-key *((mop (list @) (map @tas @)) comparator)
(turn indexed-rows.file |=(a=indexed-row +.a))
Key points: the same comparator builds the empty *((mop …) comparator) and
backs the gas:primary-key door; rows become [key value] pairs via turn.
Obelisk pattern: historical lookup and a view cache
Real-world (desk/lib/selections.hoon, generalized). Schema versions are stored
in a mop keyed by @da, ordered descending (gth). "Get the schema effective at
time" is a range query: trim everything after time with lot, then take the
head with pop:
++ get-schema
|= [sys=((mop @da schema) gth) time=@da]
^- schema
=/ time-key (add time 1)
->:(pop:schema-key (lot:schema-key sys `time-key ~))
A view cache keyed by a composite ns-rel-key uses tab to read the most
recent entry and put:on to write:
:: read: most-recent cache entry at or before the key's time
(tab:view-cache-key q `[ns.key rel.key (add time.key 1)] 1)
:: write: insert with the door bound to the cache's comparator
=/ gate put:((on ns-rel-key cache) ns-rel-comp)
db(view-cache (gate view-cache.db [key value]))
These illustrate the standard idioms: keep the comparator with the mold, use
lot/tab for "as-of" range reads, and pop/pry to take the boundary item.
6. Queues — +to
Structure
A +qeu is an ordered treap used as a FIFO queue:
++ qeu |$ [item] $|((tree item) |=(a=(tree) ?:(=(~ a) & ~(apt to a))))
Prefer this standard queue over hand-rolled front/back-list queues.
Operations (+to)
=/ q (~(gas to *(qeu @ud)) ~[1 2 3 4 5]) :: insert a list
~(top to q) :: produces the head item
~(get to q) :: [head rest] head-rest pair
(~(put to q) 6) :: insert a new tail
~(nap to q) :: remove the root/head, producing the rest
~(tap to q) :: convert to list
Best for: FIFO processing, work queues, breadth-first traversal.
Avoid for: Random access or lookup by value (no membership arm); keyed
storage (use map). For a plain LIFO stack a bare list with cons/?~ is
simpler.
7. Jars and Jugs
Jar (Map of Lists) — +ja
++ jar |$ [key value] (map key (list value))
=/ j *(jar @tas @ud)
=/ j (~(add ja j) %group 1) :: prepend to the list at %group
=/ j (~(add ja j) %group 2)
(~(get ja j) %group) :: ~[2 1] all values for key (empty list if none)
~(get ja j) returns the empty list ~ for an absent key (never crashes), so
no unit to unwrap. ~(add ja j) prepends, so the value list is in
reverse-insertion order.
Best for: Multi-valued mappings, grouping, inverted indexes (ordered, dups
allowed).
Avoid for: Membership/dedup of values (use jug); single-valued keys (use
map).
Jug (Map of Sets) — +ju
++ jug |$ [key value] (map key (set value))
=/ j *(jug @tas @ud)
=/ j (~(put ju j) %group 1)
=/ j (~(put ju j) %group 2)
=/ j (~(put ju j) %group 1) :: duplicate ignored
(~(has ju j) %group 1) :: %.y
(~(get ju j) %group) :: {1 2}
(~(del ju j) %group 1) :: remove one value from the set
(~(gas ju j) ~[[%a 1] [%a 2]]) :: insert many
~(get ju j) returns the empty set for an absent key. ~(put ju j) dedups
within the value set.
Best for: Many-to-many relationships, tagging, categorization (unique values).
Avoid for: Preserving order or duplicates among values (use jar);
single-valued keys (use map).
8. Conversions
:: list → set
(silt ~[1 2 3 2 1]) :: {1 2 3}
:: list → map
(malt ~[[%a 1] [%b 2]]) :: from a (list [key value])
(molt ~[[%a 1] [%b 2]]) :: from a (list (pair …)); +malt's helper
:: raw/literal noun → container (no explicit (list …) cast needed)
(my ~[[%a 1] [%b 2]]) :: map from a literal pair list
(sy ~[1 2 3]) :: set from a literal list
(ly ~[1 2 3]) :: list from a raw noun (see caveat below)
:: container → list
~(tap in some-set) :: set → list (unordered)
~(tap by some-map) :: map → list of [key value] pairs
(tap:on some-mop) :: mop → list of items, in key order
+nl is the noun-to-container helper core behind these literal builders.
+ly caveat: +ly uses the crash type for the empty list, so
(scag 0 (ly ~)) produces a find-fork/mull-grow error where
(scag 0 ((list @) ~)) is fine. Prefer limo/an explicit (list …) cast for
lists you will pattern-match on.
Mops have no list-based constructor — see §5; build them with gas:on.
9. Which structure should I use?
| Need | Use |
|---|
| Sequential access, stack, small collection | list |
| Unique elements, membership, set algebra | set |
| Lookup by key, order irrelevant | map |
| Lookup by key in key order, ranges, head/tail, time-travel | mop |
| FIFO queue, breadth-first | qeu |
| One key → many values (ordered, dups) | jar |
| One key → set of values (unique) | jug |
Decision shortcuts:
- Ordered processing?
list for sequential; mop for sorted/ranged keys.
map vs mop? Exact-key lookup only → map. Need order, ranges,
min/max, or "as-of" history → mop.- Multi-valued keys?
jar (lists) or jug (sets).
10. Common Patterns
Convert between structures
(silt ~[1 2 3 2 1]) :: list → set
~(tap by (my ~[[%a 1] [%b 2]])) :: map → list of pairs
~(tap in (silt ~[1 2 3])) :: set → list
Count occurrences (roll + map)
++ count-occurrences
|= items=(list @t)
^- (map @t @ud)
%+ roll items
|= [item=@t counts=(map @t @ud)]
(~(put by counts) item +((~(gut by counts) item 0)))
Group by property (roll + jar)
++ group-by-age
|= users=(list [name=@t age=@ud])
^- (jar @ud @t)
%+ roll users
|= [[name=@t age=@ud] groups=(jar @ud @t)]
(~(add ja groups) age name)
Build an inverted index (roll + jug)
++ build-index
|= documents=(list [id=@ud words=(list @t)])
^- (jug @t @ud)
%+ roll documents
|= [[id=@ud words=(list @t)] index=(jug @t @ud)]
%+ roll words
|= [word=@t idx=(jug @t @ud)]
(~(put ju idx) word id)
11. Non-standard: mip (map of maps)
mip is not part of the stdlib. It is a separate library; in Obelisk it is
imported as mip and its arms must be qualified with the file, e.g. bi:mip,
mip:mip. Use only where that library is in scope.
++ mip |$ [kex key value] (map kex (map key value))
=/ m *(mip:mip @tas @tas @ud)
(~(put bi:mip m) %a %b 4) :: insert by outer+inner key
(~(get bi:mip m) %a %b) :: [~ 4] lookup → unit
(~(got bi:mip m) %a %b) :: 4 crash if missing
(~(gut bi:mip m) %z %d 42) :: 42 default
(~(has bi:mip m) %a %b) :: %.y
(~(key bi:mip m) %a) :: {%b} inner keys under an outer key
(~(del bi:mip m) %a %b) :: remove
~(tap bi:mip m) :: list of [outer inner value]
Resources
Summary
Hoon's standard containers:
- list — sequential, constant-time prepend, good for small collections
- tree — binary-tree foundation under the treap containers
- set (
+in) — unique elements, logarithmic membership
- map (
+by) — key-value, hash-ordered, logarithmic lookup
- mop (
+on) — key-value ordered by a comparator; ordered/range/history
- qeu (
+to) — FIFO queue
- jar (
+ja) / jug (+ju) — one key to a list / set of values
- Convert with
silt, malt, molt, my, sy, ly, nl; build mops
with gas:on
- Choose by access pattern: exact-key →
map; ordered/ranged/historical
keys → mop
Mastering data structure selection and usage is key to writing efficient Hoon.
