#collections — bounded, ordered, value-semantic

Vec is the v1 sequence kind and is already in the language core. Map, Set, Deque and Tree are sealed designs whose rollout follows v1 — collections is the first package implemented after the language core, and the order of the packages behind it is frozen.

A language usually accumulates a zoo of collections — list, dictionary, set, tuple, ordered dictionary, counter, deque, heap — because it is chasing three orthogonal axes at once: mutable versus immutable, growable versus fixed, ordered versus unordered. Flux fixes all three by construction, and the zoo collapses. What is left is one substrate — a bounded arena — plus a discipline of access: five container kinds, one vocabulary, one order.

This page specifies that framework: the substrate, the five kinds, the uniform API, where capacity comes from, why every container is ordered and nothing is hashed, why a value-semantic API costs nothing at run time, and the frozen order in which the pieces are built.

New here? Start with Guide §5 — Kinds → — it teaches vec, the fixed-capacity substrate these five kinds are built on, and why a type may not point at itself.

#Why this framework is smaller here than elsewhere

Each of the three axes that produce the zoo is already decided, language-wide, before a single container exists:

Three decisions, three splits that never happen. One abstraction remains, and it shows three faces: sequence (reach an element by position), associative (reach it by key), and hierarchical (reach it by link). Five kinds cover the three faces; everything else composes out of them without a new kind.

And the value-semantic API is not a tax. Because Flux is pure, analysable and bounded, that API is executed in place (§ Efficiency): the ergonomics of a persistent collection with the performance of a mutable array — because of the constraints, not in spite of them.

Figure — five kinds, three faces, one bounded arena; every canonical order is a total order on the key value, never a hash order.

#The substrate — a bounded arena, and abstract kinds

Every container is a bounded arena — a vec(Slot, N) — wrapped in a structurally abstract kind: its representation is hidden. A script never matches on a container’s innards; it has only the blessed API, and that API is what maintains the invariant (the sort of a Map, the ring cursors of a Deque, the acyclicity of a Tree). Three consequences follow, and each one is a reason the design is worth the abstraction:

• The invariants are protected. There is no way, from a script, to break the sort order of a Map or corrupt the cursors of a Deque. The states that would violate the invariant are not merely rejected — they are not expressible.
• The implementation is free. The host picks the backing — a sorted array, a bounded B-tree, a pinned hash — and can change it without changing a line of user code, because no user code ever saw it.
• Every operation is a pinned routine. Container operations join the pinned set (decimal, the codecs, fmt.*, the total order over na): one routine, shared by the interpreter, the compiled module and the server. Invariant I7 — interpreter ≡ compiled module, byte for byte — therefore holds through a Map exactly as it holds through an ema, and replay stays exact.

Parameterised, monomorphic per site. Map(K, V, N) takes two kinds and a const cardinal N, exactly as vec(κ, N) takes an element kind and a length. This is kind parameterisation — instantiated at concrete K/V/N at each use site — and it is neither row polymorphism nor first-class generics. The height of the resulting kind is finite whenever its parameters are:

height(Map(K, V, N)) = max(height K, height V) + 1

so the lattice stays finite by structural family, which is what makes join, meet and the closure laws enumerable — the same argument that already carries vec and record.

#The five kinds

#Writing them down

Two spellings coexist, and it is worth separating them once:

• In kind position the sequence keeps its frozen surface form — lower-case, in parens: vec(κ, N). The other four use the ordinary parameterised-kind form: Deque(κ, N), Map(K, V, N), Set(K, N), Tree(κ, N). No new grammar is involved: these are the existing IDENT(args) kind expressions, the same shape as osc(0, 100) or decimal(18, 2).
• In value position the construction namespaces are capitalised: Vec.of, Map.of, Set.of, Deque.empty, Tree.node. The function namespace vec.* (map, fold, sortBy, topK, …) is unchanged and still lower-case.

record Scanner {
  ema20: Map(string, price, 64)
  seen:  Set(string, 64)
  recent: Deque(num, 32)
}

#Vec — the sequence

The positional face, and the one you already have: at(i), set(i, x), first / last, slice, window(n), and push / pop at the tail — the natural stack, O(1) in place. It carries the whole algebra: map / fold / scan / zip / where / mask / sortBy / topK / fill / range / setAt.

avgVol = sma(volume, 20)
hot    = vec.where(window(volume, 64), (v) -> v > avgVol)   // vec(volume, 64) — na in the holes
top3   = vec.topK(window(high, 64), (h) -> h, 3)            // vec(price, 3)

The lambda comes before the count in topK: the key function is what the operation is about, and the count is a bound on its result. Both are the ordinary vec.* calls — the same namespace, in the same shape, as vec.map and vec.fold.

Vec is the pivot: every other container projects into it through toVec (§ The uniform API), which is why the per-container API stays small — each kind carries only its structural operations, and the rest of the algebra is reached through the bridge.

#Deque — queue, stack and ring buffer, in one kind

One structure for every access discipline. The representation is a ring — ⟨buf: vec(κ, N), head, len⟩ — so at(i) is O(1) as well as both ends:

pushFront / pushBack / popFront / popBack yield the deque without the element; the element itself is read with peekFront / peekBack, which are na on an empty deque. Splitting read from removal is what keeps every operation returning exactly one value.

def rolling(q, x) = q.popFront().pushBack(x)   // fixed-size ring: one out, then one in

Why popFront comes first. Pushing onto a full deque is a rejection with a diagnostic, not a silent eviction — no container ever drops your data behind your back, and none ever grows. A ring that overwrites its oldest element is therefore written as an explicit pop followed by a push. Where eviction is the policy you want, it is declared as one: the Latest(n) back-pressure policy of net is a bounded queue whose eviction rule is part of its kind.

There are deliberately no separate Queue, Stack or Heap kinds. If intent needs a name, Queue and Stack are restricted-API aliases over Deque, not kinds of their own. And many “queue” needs are already met elsewhere: the Latest(n) policy is a bounded queue, the Sub / Cmd mailbox is the message queue, window(n) is the sliding buffer. The user-land Deque serves the remainder — a breadth-first frontier, a work-list, an animation queue.

A priority queue (Heap) is not a kind of its own here: topK already covers the top-k need, and the heap arrives with the graph-algorithms lot that actually requires it.

#Map — the ordered associative kind

The real gap the framework fills: state under a dynamic key. Per-symbol state in a multi-asset scanner, “have I already seen this id”, counts per bucket — each of them, without a Map, is a linear scan over a slotmap or a hand-sorted vec.

The backing is a sorted array of keys and values (or a bounded B-tree, at the host’s choice):

syms   = Vec.of(["BTC-USD", "ETH-USD", "SOL-USD"])              // vec(string, 3)
def bump(m, k) = m.insert(k, m.getOr(k, 0) + 1)
counts = vec.fold(syms, Map.empty(64), (m, k) -> bump(m, k))    // Map(string, num, 64)
nBtc   = counts.get("BTC-USD")                                  // num | na

range is the operation that quietly removes a whole kind from the design. A range is also a prefix on a sorted backing, so a typeahead — the classic reason to reach for a trie — is a bounded range scan:

def suggest(idx, lo, hi) = idx.range(lo, hi, k: 10)   // vec(record{ key: string ; val: num }, 10)

O(log N + k), a declared cap of k results, no trie kind anywhere.

The slotmap of the APP plane is the same idiom: it is a Map(Handle, V, N) whose keys the host assigns. The framework generalises the slotmap rather than duplicating it.

#Set — the ordered set

A Map with the value column removed: ⟨keys: vec(K, N), len⟩. It carries has, add, remove, and the algebra that does not belong on a map — union, intersect, diff, subset.

levels = Set.of(window(high, 64))   // Set(price, 64) — deduplicated, sorted, na skipped
known  = levels.has(close)          // signal — O(log N)
near   = levels.toVec().take(5)     // back into vec-land, and the whole vec algebra

#Tree — a hierarchy as a node pool

Trees exist mostly for display — a collapsible watchlist by sector, the nested conditions of a strategy, a scene or menu hierarchy — and for any data whose internal structure is a hierarchy. A tree is never a recursive type:

record Node { value: num ; children: Node }   // ✗ [ErrTotalType] — a type may not reference itself

A recursive type has no finite height, and a language that bounds its memory at compile time cannot admit one. So a Tree is a flat node pool — ⟨nodes: vec(Node, N), root⟩ where a node holds its value plus two handle indices (firstChild, nextSibling; na means absent). It is bounded by its node count N, from which the bound on depth follows. This is exactly what the display plane’s own BSP nodes already do: children are handles, not nodes.

Traversal is a catamorphism, and the host drives the recursion:

record Sector { name: string ; weight: ratio }

def totalWeight(t) = tree.fold(t, (node, kids) -> node.weight + kids.sum())   // ratio

fold hands your lambda a node’s value and the already-folded children (as a vec), walking the flat array in post-order. It terminates by construction, because N bounds the pool.

Why the script never writes the recursion. A recursive traversal written in the script would be a recursive def, and the call graph must stay acyclic ([ErrTotalRec]) for the totality proof to hold. Handing the recursion to a bounded host kernel keeps both properties: the tree is walked, and the language stays total. The lambda is second-class — eliminated at the call site — so no arrow ever enters the lattice.

The rest of the surface: map, flatten(t) -> vec(κ, N) (DFS pre-order), depth, children(node), insertChild(parent, x), prune(node). Construction is Tree.node(x, kids), or Tree.unfold(seed, step, N) — the dual anamorphism, bounded by N nodes.

leaf = Tree.node({ name: "Energy", weight: 0.18 }, [])
rows = leaf.flatten()                                     // vec(Sector, N) — DFS pre-order

#The uniform API — Foldable, and the toVec bridge

You learn it once. Every container is Foldable, and toVec is the universal lens: the moment you hold a vec, the entire vec algebra (sortBy, topK, sum, where, fold) applies. That is what keeps the per-container API tiny — each kind exposes only what is structural about it, and everything else goes through the bridge.

The vocabulary shared by all five:

Per face:

Construction is uniform too: C.of(foldable) builds a container from any foldable — a literal, a vec, another container — and C.empty(N) is the empty container at capacity N. Vec.of([…]), Set.of([…]), Map.of([(k, v) …]), Deque.empty(N), Tree.node(x, kids).

These are per-kind host routines dispatched on the kind of the receiver at the call site — the same structural dispatch the columnar Table / Col / Mat operations already use. So tree.fold(t, f) on a Tree and vec.fold(v, seed, step) on a vec are different routines behind one name, chosen by what you called it on, at compile time.

#Four rules, propagated everywhere

The totality-and-determinism envelope shows up identically in all five kinds:

1. Full ⇒ rejection and a diagnostic. Never silent growth. isFull lets you decide first.
2. Absent ⇒ na. A missing key, an empty peek, an out-of-range index — na, never an exception. na is na-aware through the rest of the algebra, so it propagates instead of trapping.
3. No shortening operation, ever. There is no filter: a data-dependent length would break the bound. where and mask are length-preserving and leave na in the holes, and iteration is na-aware, so nothing needs compacting.
4. A canonical order per container (§ Determinism).

avgVol = sma(volume, 20)
hot    = vec.where(window(volume, 64), (v) -> v > avgVol)   // ✓ same length, na where the predicate is false

hot = vec.filter(window(volume, 64), (v) -> v > avgVol)  // ✗ no such operation — the length would depend on the data

#Capacity comes from the context

The hard line of the bounded-memory rule, stated once:

• Capacity is a compile-time const: a literal (Map(price, num, 64)), a named const (MAX_BARS), or a const supplied by the host context — a chart’s maximum bar count, a declared watchlist size. This is the pattern the series kind already uses:

  FLUX

  type Series(T) = vec(T, MAX_BARS)   // the context fixes the ceiling

• Occupancy is a run-time value, always ≤ capacity. count moves; N does not.

• Capacity propagates through conversions. vec(κ, M).toSet() is a Set(κ, M): deduplication can only shrink the population, so M is the safe bound — inferred, never annotated.

• A run-time ceiling is forbidden. A capacity that varies with the data would make the compile-time memory account unprovable.

n    = count(volume > sma(volume, 20), 64)   // a RUN-TIME value: it depends on the data
seen = Set.empty(n)                          // ✗ [ErrTotal] — a capacity must const-fold

Why “it depends on the context” is not the same as “it depends on the data”. The context fixes the const ceiling — how many bars this chart holds, how many levels this tool allows. The data fixes the occupancy under that ceiling. Keep those two apart and the memory a script needs is computable before it runs; conflate them and it is not.

#Determinism — ordered by default, zero hashing

Every container has a canonical order, used by toVec, by fold, and by iteration, because I6/I7 demand that two engines produce the same bytes.

Map and Set are sorted by key — the associative kinds are ordered structures, not hash tables. Three reasons, in the order they mattered:

• Flux keys are almost always ordered kinds already (string, num, decimal), so nothing is lost.
• Sorted iteration is deterministic by construction. There is no seed to pin, no insertion-history to reproduce, no divergence to chase.
• It is usually the order you wanted anyway — rankings, per-key display.

Why a hash order is not an option. A hash order depends on a seed and on the insertion history, so two engines can iterate the same set in two different orders while both being “correct”. Under I7 — interpreter ≡ compiled module, byte for byte — and under a replay that a server re-derives to check a client’s work, “both correct” is a divergence. Sorting the keys costs O(log N) on lookup and buys back the entire property, with nothing to pin.

Keys must be comparable. A key kind must admit a total order and an equality ([CmpOrd] / [CmpEq]): string, num, dir, decimal, and records of those. Kinds with no equality — clock, ui, a lambda — cannot be keys:

record Bad { picked: Set(ui, 8) }   // ✗ [ErrArg] — `ui` has no equality, so it cannot be a key

An insertion-order or pinned-hash (seedless) backing remains available as a host implementation choice behind the same API, should a key-unordered or insert-heavy profile ever demand it. The exposed order stays deterministic either way; the decision is evidence-based, and sorted-by-default is the shipping answer.

#Efficiency — a value API, executed in place

This is where the constraints pay for themselves. A bounded immutable collection sounds slow. It is not, and the reason is mechanical.

Functional but in place. The API returns a new container — m2 = m.insert(k, v) — but the compiler already holds the DAG of uses. When m is dead after the call, the host mutates the arena in place: O(1) or O(log N), not an O(N) copy. No new machinery is involved; this is the existing liveness analysis (persistent-held versus transient-recycled buffers) applied to container updates. Nothing is annotated, nothing is borrowed — it is inferred.

def track(book, sym) = book.insert(sym, ema(close, 20))   // returns a new Map…
                                                          // …and updates the arena in place when the old one is dead

It is observably pure either way: in-place and copy produce the same value, so I6/I7 hold and the bytes are identical. The optimisation is invisible except in the profile.

No persistent trie. Unbounded immutable collections need a hash-array-mapped trie to be efficient — that is what pays for structural sharing. Bounded arenas plus in-place execution get the same effect more directly: a contiguous array, mutated in place, no garbage collector, no pointer chasing, and linear scans that are cache-friendly.

Zero allocation in steady state. The ceiling N pre-sizes the arena, so the arena is allocated once. Even the worst case — an actual copy — is a fixed-size memcpy.

toVec is often free. Where the backing already is the vector, toVec is a view, not a copy. Only a reordering (a sorted view of an insertion-ordered backing) materialises anything.

#Conversions and compositions

The of / toVec bridge makes conversion mechanical, and the capacity comes along for the ride:

Everything else composes, and adds no kind:

type Graph  = Map(num, Set(num, 16), 64)       // bounded adjacency, by handle
type Counts = Map(string, num, 64)             // a counter / bag
type Index  = Map(string, Set(num, 32), 256)   // an inverted index: token → document ids

A bounded graph walk is a bounded loop over exactly two of these kinds — a Deque frontier and a Set of visited nodes:

record Walk { frontier: Deque(num, 64) ; seen: Set(num, 64) ; order: vec(num, 64) }

Breadth-first, depth-first, topological order, connected components and cycle detection are all defs over that state. A multimap is Map(K, vec(V, M), N). A slotmap is Map(Handle, V, N). None of them is a new kind.

The compute pillar stays a separate family. Table / Col / Mat are columnar and relational — groupBy, asofJoin, stat, regression — and they are not forced into the container vocabulary, any more than a dataframe should be forced into a dictionary. The bridge between the two worlds is Col ↔ Vec: a column is a sequence. See compute.

#Planes, the firewall and replay

Containers are pure values, so they cross no plane boundary and raise no firewall question:

• In the ANALYSIS plane they are bounded and deterministic — a Map of per-asset moving averages, a Set of detected levels, a Tree of market structure.
• In the APP plane they are Model fields. The Model’s slotmap already is one, and the stable-id map beside it is the other:

record Level { id: num ; price: price ; label: string }
record Model { levels: Map(num, Level, 64) ; count: num }

No container operation reads presentation, and none reads a device-variable value, so none can breach the firewall ([ErrFirewall] is not reachable from this API — the firewall and the capability model it enforces are specified in host-services). Every operation is a pinned routine with a canonical order, so byte-identical replay — and the anti-cheat that rests on it — holds through any container; what a server re-derives from that replay, and the guarantee it proves, is server’s to state. The lambdas passed to fold / map / where are second-class, eliminated at the call site, so no arrow sort enters the lattice.

#Deliberate limits

These are design decisions, not gaps:

• No unbounded collection. The bound is always a const. Totality has no exceptions.
• No recursive type ([ErrTotalType]) — trees and graphs go through a node pool and handle indices, never a type that points at itself.
• No filter — a data-dependent length breaks the memory account. where / mask are length-preserving.
• Keys must be orderable and equatable ([CmpOrd] / [CmpEq]) — no clock, ui or lambda key.
• No run-time-variable ceiling.
• Four things sit outside v1, each with a reason and a trigger: a Heap / priority queue (topK covers the need; the heap ships with the algorithms that require it), a pinned-hash backing (sorted-by-default suffices; the decision is evidence-based), a finger-tree Deque with O(log N) split and concat (the ring’s O(1) ends suffice), and row polymorphism over the value kinds (v1 is monomorphic per site).

Five kinds, one vocabulary (Foldable plus toVec), value-semantic and executed in place, ordered and deterministic, bounded — and every one of those properties is a consequence of a decision the language had already made.

#See also

• compute — the columnar Table / Col / Mat family, and the Col ↔ Vec bridge.
• Kinds — kind parameterisation, finite height, and the [CmpOrd] / [CmpEq] classes.
• text — the Markdown AST, the named consumer of Tree.
• App plane — the slotmap, which is a Map(Handle, V, N).
• Memory model — the bounded arena, liveness, and in-place execution.
• net — Latest(n), the bounded queue whose eviction policy is part of its kind.