Native Collections

Grid collections retain the behavior of the structure they represent. An Array is rectangular, a List is indexed, a Deque has two efficient ends, a Map has keys, and a Set has unique members. Grid does not silently turn every structure into a generic array or object between formulas.

Collection values are immutable. An operation such as VECTOR_SET, DEQUE_PUSH_BACK, or MAP_PUT returns a revised value; it does not change the value supplied as its input. This makes collection formulas safe to reuse in a reactive model.

Choosing A Structure

Use explicit conversion functions when crossing structure boundaries. For example, DEQUE_TO_ARRAY and VECTOR_TO_ARRAY publish sequence values as workbook arrays; Grid does not perform that conversion implicitly.

Deque

DEQUE constructs an immutable double-ended queue:

pending = DEQUE("compile", "test")
ready = DEQUE_PUSH_FRONT(pending, "parse")
 
first = DEQUE_FRONT(ready)       # "parse"
last = DEQUE_BACK(ready)         # "test"
count = DEQUE_LENGTH(ready)      # 3
empty = DEQUE_IS_EMPTY(ready)    # FALSE

An update returns a new value. The original remains unchanged:

before = DEQUE(1, 2)
after = DEQUE_PUSH_BACK(before, 3)
 
before_count = DEQUE_LENGTH(before) # 2
after_count = DEQUE_LENGTH(after)   # 3

Pop operations return a two-element Array containing the removed value (or BLANK) and the remaining Deque:

result = DEQUE_POP_FRONT(DEQUE("a", "b", "c"))
removed = INDEX(result, 1, 1)   # "a"
remaining = INDEX(result, 1, 2) # DEQUE("b", "c")

Use DEQUE_FROM_ARRAY to consume a range or Array in row-major order and DEQUE_TO_ARRAY to publish a Deque as one row. End reads and end pushes are constant-time operations; concatenation, splitting, taking, dropping, and conversion are linear in the values traversed.

Tuple And List

TUPLE creates a fixed-position product:

point = TUPLE(12.5, -4.0, "EPSG:4326")
crs = TUPLE_GET(point, 3)
moved = TUPLE_SET(point, 1, 13.0)
arity = TUPLE_LENGTH(point)
published = TUPLE_TO_ARRAY(point)

Positions are one-based. ISTUPLE distinguishes a Tuple from an Array or List.

List is the type name for the indexed sequence constructed by VECTOR:

before = VECTOR(10, 20)
after = VECTOR_SET(before, 2, 30)
value = VECTOR_GET(after, 2)       # 30
grown = VECTOR_PUSH(after, 40)
[last, smaller] = VECTOR_POP(grown)

List positions are one-based. Indexed access and updates are logarithmic in the sequence size; length and empty checks are constant time. Use VECTOR_FROM_ARRAY and VECTOR_TO_ARRAY at workbook boundaries.

Map And Set

Map and Set keys are type-sensitive. A tagged USD value, a metre value, and an untagged number do not become the same key merely because their numeric payloads match. Finite numbers are valid keys; signed zero is normalized, and NaN and infinity are rejected.

prices = MAP_OF("apple", 2.5, "pear", 3)
updated = MAP_PUT(prices, "apple", 2.75)
pear = MAP_GET(updated, "pear")
maybe = MAP_GET_OPTION(updated, "plum") # NONE()
 
seen = SET_OF("a", "b", "a")
seen2 = SET_ADD(seen, "c")
common = SET_INTERSECT(seen2, allowed)

Iteration uses canonical key order rather than insertion order. Lookup and single-key updates are logarithmic; MAP_KEYS, MAP_VALUES, and set algebra return deterministic values.

Membership, Set Relations, And Ordered Containment

Grid deliberately separates element membership, set-like relations, and ordered containment:

These operations preserve structure rather than recursively flattening it. A one-dimensional Array exposes its cells. A two-dimensional Array exposes its rows. Tuple, List, and Deque expose their items. Set and Map membership uses canonical keys. A scalar is a singleton collection when used by IN, SUBSET, SUPERSET, or OVERLAPS.

A column literal is a two-dimensional Array, so [1; 2; 3] exposes three one-cell rows rather than three numbers. Membership against a column needs a row on the other side, and orientation must match on both operands. This holds for every element type, numbers and text included.

row_member = [1, 2] IN [[1, 2], [3, 4]]       # TRUE
inverse = [[1, 2], [3, 4]] HAS [1, 2]          # TRUE
not_flat = 1 IN [[1, 2], [3, 4]]               # FALSE: elements are rows
column_rows = 1 IN [1; 2; 3]                   # FALSE: a column exposes rows
column_row_match = [1] IN [1; 2; 3]            # TRUE
orientation = [1, 2] SUBSET OF [1; 2; 3]       # FALSE: scalars are not rows
unordered = [3, 1] SUBSET OF [1, 2, 3]         # TRUE
contiguous = [1, 2, 3, 4] CONTAINS [2, 3]      # TRUE
wrong_order = [1, 2, 3, 4] CONTAINS [3, 2]     # FALSE
text_match = "Grid language" CONTAINS "language" # TRUE: case-sensitive

Structural equality is type- and tag-sensitive. Error values match by error code, while diagnostic message text is ignored. Signed zero values match; NaN never matches any value, including another NaN; infinities match only when their signs agree. Consequently, NA() IN [NA()] is true, while NA() IN [#VALUE!] is false.

An empty ordered pattern always matches, and a scalar right operand to CONTAINS is a one-element pattern. CONTAINS rejects unordered Sets and Maps. Callable IN needs a value and at least one candidate. CONTAINS, SUBSET, SUPERSET, and OVERLAPS require exactly two arguments.

The runtime indexes the candidate side of set-like relations and verifies hash collisions with exact structural equality. Duplicate members occupy one index entry. Ordered collection CONTAINS uses linear-time sequence matching, with a direct scan for a one-element pattern; native text uses case-sensitive substring search. Work is proportional to the direct elements and any nested structures that equality must inspect.

Ranked Sets, Bitmaps, And Cardinality

ZSET(member, score, ...) constructs a ranked set. ZADD, ZREM, ZSCORE, ZRANK, ZREVRANK, ZCARD, ZCOUNT, ZRANGE, ZREVRANGE, ZRANGEBYSCORE, ZINCRBY, ZUNION, ZINTER, ZDIFF, ZPOPMIN, and ZPOPMAX provide the ranked-set surface. Ranks and range endpoints are zero-based. Equal scores use Grid's canonical member order.

BITMAP(bit...) represents sparse non-negative integer positions. BITMAP_SET, BITMAP_CLEAR, BITMAP_GET, BITMAP_COUNT, BITMAP_OR, BITMAP_AND, BITMAP_XOR, BITMAP_RANK, and BITMAP_SELECT operate without allocating every preceding position. BITMAP_NOT requires an explicit finite domain and rejects excessively large complements. Formula positions must be exactly representable integers.

HLL([precision]) creates an approximate cardinality value. PFADD, PFCOUNT, and PFMERGE follow the familiar HyperLogLog vocabulary. The value reports an estimate and uncertainty information; callers should not present it as an exact count after it has entered approximate mode.

Streams And Probabilistic Structures

STREAM() creates an ordered stream. XADD returns TUPLE(id, revised_stream), with monotonic millis-sequence IDs. XRANGE, XREVRANGE, and XREAD read by ID; XDEL, XTRIM, and XTRIM_MINID return revised streams. XLEN reports logical length.

Live Stream execution distinguishes event time from processing time. Event-time sources declare out-of-order tolerance, allowed lateness, and a late-event policy (drop, side output, or update). Watermarks close bounded tumbling, sliding, and keyed session windows; bounded keyed interval joins accept either arrival order. Queue overflow is explicit (drop oldest, drop newest, block, or reject).

Resident event-time state checkpoints its watermark, open windows, stable event IDs, and source partition offsets. This makes replay idempotent. Grid's production exactly-once boundary covers the durable source receipt cursor, checkpointed model state, and latest durable local sink-effect batch in one transaction. Realtime notifications retain latest-value delivery, and Grid cannot make an arbitrary webhook, remote queue, or database mutation exactly once; those effects remain at least once unless their adapter provides a shared transaction or deduplicates by event identity.

The binding in FROM_PIPE(binding, ...) is also the exact HTTP ingress :sourceId after URL decoding; leading/trailing whitespace is unsupported. When at least one model is registered for that exact source, accepted batches enter a host-owned durable source log before admission succeeds. Legacy or currently unsubscribed event traffic stays on the existing realtime lane and is not retained as a future Stream backlog; registration is the start of the durable subscription boundary. Polls are provisional and carry an opaque receipt. A failed evaluation or checkpoint transaction restores the region's checkpointed model/Frame state, leaves its latest durable sink batch and cursor unchanged, and later polls again from that cursor in source order. A restart can choose a different batch boundary and receipt. With checkpoint: false, Grid publishes the local model update and then acknowledges the receipt; an acknowledgement failure keeps that update visible and replays from the unchanged source cursor, so this mode is explicitly at least once. Best-effort rule and render follow-ons run after that acknowledgement and are not part of the source transaction. A source-triggered resolve evaluates all Stream regions in its selected model; Grid publishes every structured Stream output from that resolve before acknowledging any uncheckpointed receipt, including retained work from another source in the same model.

Restore fails closed when window bounds/keys, retained records, remembered IDs, source offsets, or watermark/maximum-observed progress disagree. Checkpoints are isolated by model, compiled Stream contract, and region. If publication succeeds but its final durability sync is uncertain, Grid keeps the state committed and reports a durability warning instead of retrying an already visible checkpoint.

Checkpoint publication also uses an exact compare-and-swap against the snapshot loaded before evaluation, so a delayed concurrent resolve cannot replace newer offset and watermark progress.

FROM_PIPE(binding, options) is the authoring boundary for live Stream state. Its options are compile-time data: timeDomain, outOfOrdernessMs, allowedLatenessMs, latePolicy, delivery, window, queueCapacity, queuePolicy, maxWindowsPerEvent, maxOpenWindows, maxSeenEventIds, checkpoint, and an optional bounded join. Tumbling windows use {kind: "tumbling", sizeMs, offsetMs}, sliding windows add slideMs, and sessions use {kind: "session", gapMs}. A join declares {source, beforeMs, afterMs, maxRecords}. Unknown options and nonpositive bounds fail compilation. delivery: "exactlyOnce" requires checkpoint: true. The versioned region checkpoint includes unmatched interval-join state as well as per-source windows, IDs, offsets, and watermarks, so recovery does not silently discard one side of a join.

The compiled Stream region carries a shared Collection/Dataflow plan: keyed windows use the Group delta law, interval joins use the Join arrangement law, and both terminate at Publish. Event clocks and state bounds remain Stream semantics; there is no parallel batch-only interpretation.

XGROUP, XREADGROUP, XACK, XCLAIM, and XPENDING provide persistent consumer-group state. Their return values must be rebound like any other immutable collection revision.

BLOOM(expected_items, false_positive_rate) creates a bounded Bloom filter. Inserted values have no false negatives; a positive result remains probabilistic. Filters merge only when their dimensions match.

COUNT_MIN(width, depth) creates a Count-Min sketch. CMS_ADD, CMS_ESTIMATE, CMS_MERGE, and CMS_TOTAL provide mergeable frequency counting. Estimates never undercount; CMS_TOTAL remains the exact total inserted weight.

Indexes, Multiplicity, And Summaries

TRIE supports exact lookup, prefix enumeration, deletion, and longest-prefix matching. INTERVAL_INDEX supports point and overlap queries over finite, non-reversed numeric intervals.

MULTISET retains exact duplicate counts and supports max-union, min-intersection, additive sum, and saturating difference. MULTIMAP maps a canonical key to multiple ordered values.

KLL(capacity) maintains a bounded, mergeable quantile summary. TOP_K maintains bounded heavy-hitter estimates and publishes each estimate with its replacement error. MERKLE_SET provides deterministic content identity, differences, and membership proofs.

Record, Option, And Result

Records are fixed-shape named products:

person = RECORD("name", "Ada", "score", 7)
revised = RECORD_SET(person, "score", 9)
name = RECORD_GET(revised, "name")

Unknown or duplicate fields are errors.

SOME(value) and NONE() distinguish optional absence from BLANK. OK(value) and ERR(value) represent ordinary success or failure data; ERR does not trigger workbook error propagation.

Option and Result participate in constructor-pattern MATCH:

answer = MATCH(maybe,
  SOME(value) -> value,
  NONE() -> "missing")
 
status = MATCH(outcome,
  OK(value) -> value,
  ERR(reason) -> "failed: " & reason)

Grid warns when a match over either closed family is non-exhaustive and rejects a single match that mixes Option and Result patterns.

User-defined payload-bearing alternatives use algebraic CHOICE declarations:

CHOICE Outcome = Accepted(value: number) | Rejected(reason: string)
outcome = Outcome.Accepted(7)
answer = MATCH(
  outcome,
  Outcome.Accepted(value) -> value,
  Outcome.Rejected(reason) -> reason
)

These values are immutable native records with closed constructor identity. Constructor matches are exhaustively checked. See algebraic-data-types.md.

Collection Type Contracts

Collection kinds may be used without an element contract:

mixed IS List = VECTOR(1, "two", {name: "three"})
pending IS Deque = DEQUE()

Use of for element types and to for Map key/value types:

names IS List of String = VECTOR("Ada", "Edsger")
orders IS Map of Customer Id to List of Order = MAP_OF()
outcome IS Result of Number or String = OK(42)

The compatibility forms Vector<number>, Map<string, Vector<number>>, Option<Record<Person>>, and Result<number, string> are also accepted. The formatter emits the natural-language forms. Under strict refinement, Grid checks nested authored contracts; warn mode returns the value with a diagnostic.

Higher-Order Operations

MAP, REDUCE, and SCAN preserve collection meaning where possible:

• MAP over List or Deque returns the same sequence kind.
• MAP over Map retains its keys and maps its values.
• MAP over Record retains its schema.
• MAP over Option or Result retains the active variant.
• REDUCE consumes each supported collection in deterministic order.
• SCAN over List or Deque preserves the input sequence kind.

All folds are bounded by finite collection size. ITERATE is the explicit bounded state-transition operation and rejects more than one million steps.

Grid gives collection pipelines one compositional meaning. MAP, FILTER, flattening maps, zips, partitions, scans, folds, groups, joins, collection, and publication lower to a shared Dataflow algebra. Every stage records whether it preserves order, changes cardinality, requires state, can fuse, and can process inserts/removes incrementally. This is why a pure unpublished MAP/FILTER chain can run without intermediate collections, while SCAN, a published intermediate, or an effectful callback remains an explicit boundary.

Job-queue effects are inferred from lambda and named-function bodies. They remain illegal in ordinary MAP/FILTER/fold callbacks; use TRAVERSE(source, callback [, limit]) for one-at-a-time effects or PAR_TRAVERSE(source, callback, concurrency [, limit]) for a bounded sliding window. Both preserve source-order results and fail before launch when the runtime source exceeds the static limit. Arrays traverse row-major; native iterable collections use the same stable logical elements as REDUCE; sketches and streams fail before launching an effect. An algebraic choice is one sealed scalar element, not the fields of its resident record. See reference.md for the complete failure, ordering, and retry contract.

Fold behavior follows the reducer's algebra rather than a blanket "parallelizable" label. Source-ordered floating-point folds preserve authored order. Associative reducers may merge cached partials; commutative reducers may regroup them; only reducers with an exact inverse may subtract old contributions. In particular, filtered COUNT/COUNTA can update changed persistent-vector pages exactly, while floating-point SUM/AVERAGE replay in source order.

Native collection kinds declare capabilities through one shared contract. Runtime operations use that contract rather than independent per-function allow-lists, and compiler passes can query the same stable kind discriminant:

Named-function inference uses these capabilities as protocols. For example, same_shape(values) = MAP(values, value => value) infers Mappable f => f<a> -> f<a> and rejects a known non-mappable constructor at the call site. See named-functions.md.

Approximate summaries and stream state are not ordinary element collections. MAP, REDUCE, or SCAN therefore returns #VALUE! when the required capability is absent; a sketch is never folded as though its estimate or internal samples were authored elements, and an unsupported MAP never silently returns the original value.

Named trailing blocks

For a multi-line callback, put its parameter names after the call and write a normal DO ... END block:

cleaned = MAP(rows) WITH row DO
  amount = row.amount DEFAULT 0
  ROUND(amount * exchange_rate, 2)
END
 
total = REDUCE(0, cleaned) WITH total, value DO
  total + value
END

These lower exactly to MAP(rows, row => DO ... END) and REDUCE(0, cleaned, (total, value) => DO ... END). Multi-source MAP takes one name per source. SCAN, ITERATE, BYROW, BYCOL, and MAKEARRAY use the same form with the arity of their existing lambda contract.

This is distinct from a leading WITH value DO step THEN step expression, which is whole-value pipeline sugar. A named trailing block belongs to the collection helper immediately before it and names callback arguments.

Functional pipelines

Use a named lambda when a pipe step applies a predicate to each element:

positive_count = values |> MAP(value => value * 2) |> FILTER(value => value > 0) |> COUNT()

Inside a pipe, FILTER(predicate [, if_empty]) is functional sugar for the ordinary mask call FILTER(values, MAP(values, predicate) [, if_empty]). The lambda parameter names one element. Outside a pipe, FILTER keeps its spreadsheet signature FILTER(values, include_mask [, if_empty]):

positive = FILTER(values, values > 0, "empty")

The older pipe spelling FILTER(_, _ > 0) remains accepted for existing models, but new code should use a named lambda. This keeps _ unambiguous: in SORT(_, -1) it denotes the whole piped value, while value in FILTER(value => value > 0) denotes one element.

Pipe lowering happens before optimization, so optimized and generic execution have the same result, ordering, error behavior, and if_empty behavior. For an unpublished homogeneous numeric chain ending in SUM, AVERAGE, COUNT, or COUNTA, the compiler may execute supported total MAP/FILTER stages as one ordered native pipeline without publishing intermediate collections. A direct numeric scalar capture such as value > threshold remains a live dependency; changing it replays the complete pipeline, while sparse source edits may still use page deltas when the capture is unchanged. Publication, mixed representations, unsupported operations, dynamic or computed predicates, and observable empty-result behavior remain exact fallback boundaries.

Numeric SUM and AVERAGE always retain authored source order because floating-point addition is not associative. Filtered numeric COUNT and COUNTA may update from a bounded sparse set of changed persistent-vector pages because their carried state is exact cardinality; dense edits safely recompute the complete fused pipeline. These are physical optimizations, not different language semantics.

Graphs, Frames, And Tensors

Graph, Frame, and Tensor are specialized structures rather than generic nested arrays:

• Graph preserves topology, stable identity, property schemas, and bounded traversal.
• Frame preserves named columns and relational operations over large tabular values.
• Tensor preserves homogeneous element type, rank, shape, and numerical operations.

Conversions and projections are explicit so formulas do not accidentally materialize large structures into workbook cells. See graph-authoring.md for graph authoring and relational-authoring.md for choosing a relational surface.

Reactive Collection State

Formula collection operations are immutable. Use STATE when rules are allowed to replace the current collection value:

STATE pending = DEQUE()
 
WHEN new_job THEN
  pending = DEQUE_PUSH_BACK(pending, job)
END

RESET pending restores the declared base expression. CLEAR pending pins the state to BLANK. Pure collection calls never mutate the value passed to them.

Limits And Errors

Collection constructors and operations enforce bounds on dimensions, nested type depth, iteration, and structures whose dense materialization could be surprising. Invalid keys, incompatible merges, malformed records, out-of-range positions, and exceeded bounds return named diagnostics or documented error values rather than partial results.

For exact signatures and limits, use the functions.md catalog. For scalar equality and coercion rules, see coercion.md.