Skip to content

· 6 min read

Betting on lists

Blot's lists put adding, removing, and iterating first. Dense leaves and shared tree branches make that a different bet from a contiguous array.

A branching brass specimen stand holds four wooden seed trays beneath a magnifying lens, with a fifth tray detached beside it.
Illustration generated with GPT Image

Collect some diagnostics, discard the ones that no longer apply, then walk what remains. A lot of the collection code I want to write has that shape. The size emerges as the program runs. Things arrive, things leave, and eventually somebody needs to read them in order.

Those are the operations I want Blot's lists to be good at: adding, removing, and iterating. The language keeps List and Array separate, with different storage and different interfaces. That gives the implementation room to take each job seriously.

A tree with dense leaves#

Blot's runtime list is a persistent AVL tree. Branches connect smaller sequences; the elements live together in dense leaves. A leaf grows through allocation sizes up to a limit of 244 storage words. For U32, that means up to 244 elements. A packed record uses several words, so fewer records fit. Small lists start with small leaves.

This puts nearby elements next to each other in memory while leaving room to rearrange larger pieces through the tree. There is a branch structure to maintain, but the walk between individual elements within a leaf is a walk through contiguous storage. The tradeoff is already visible: some overhead between chunks buys flexibility around them.

Both lists and arrays have immutable value semantics. Keeping an earlier value keeps its contents. Underneath that promise, Blot can reuse storage when ownership proves nobody else needs the old version. Persistence describes what the program can observe; ownership decides how much copying is necessary.

Adding at the edges#

The ordinary spellings are [...values, item] and [item, ...values]. The library also exposes list.append and list.prepend. An exclusively owned end edit can reuse the leaf's spare capacity and the tree nodes leading to it. Growth may still allocate a larger leaf or another branch, and the tree must remain balanced.

When an older version remains shared, the runtime copies the affected leaf and tree path. Unchanged subtrees remain shared. That makes the size of the edited path relevant instead of requiring every existing element to move on every append.

earlier rootleftrightappended rootleftrightshared leafvalues: 0 … 243earlier tailvalues: 244, 245new tailvalues: 244, 245, 246

Two list roots share the unchanged left leaf and point to different right leaves after an append.

  • earlier root: left points to shared leaf; right points to earlier tail
  • appended root: left points to shared leaf; right points to new tail
  • shared leaf: values: 0 … 243
  • earlier tail: values: 244, 245
  • new tail: values: 244, 245, 246
A schematic two-leaf list with its earlier version retained. Appending copies the right leaf and root; both versions still use the same left leaf.

The sharing costs something too: ownership checks, tree navigation, and copies when versions diverge. I would measure a private builder separately from a builder that saves every intermediate result. They ask quite different things of the same append expression.

Removing pieces#

The useful operation for a known range is list.splice. Give it a start, a deletion count, a replacement list, and the original list. An empty replacement deletes the range. A zero deletion count inserts at that position.

Add, remove, then walk
import * as list from "std/list"const revise = fn (last: U32) => do:  let original: List U32 = [10, 20, 30, 40]  let longer = [...original, last]  let shorter = list.splice 1 2 [] longer  let total = 0  for value in shorter:    total := self + value  return (original, shorter, total)
  1. 1Append the runtime argument to the list.
  2. 2Starting at zero-based position 1, remove two elements.
  3. 3Read the remaining elements in sequence.
  4. 4Return the earlier value alongside the edited one.
With last set to 50, the shorter list contains 10, 40, 50 and the total is 100. The original still contains all four starting values.

The implementation builds that edit from slices and concatenations. Whole subtrees can survive; partial boundary leaves are copied, and boundary paths are rebuilt. A small slice also gets its own boundary storage, so retaining one element does not require retaining its large discarded leaf or the original root.

Removing by a condition has a different cost. list.filter must visit the elements and evaluate the predicate to discover what survives. Knowing where to cut and searching for what to remove are separate workloads. For several known edits, list.splice_many accepts ordered, nonoverlapping ranges expressed in the original list's coordinates.

The walk matters#

Efficient edits would be a poor bargain if every later read paid heavily for them. Blot's direct list loops consume a leaf before finding the next one. The private tree walk remembers pending right subtrees and visits each tree edge at most once. Sequential traversal can use that knowledge instead of searching from the root for every element.

Small, flat scalar records and tuples can also store their fields directly in the leaves. That avoids a separate heap object per row for eligible layouts. Reference-bearing and more complicated values keep their boxed representation. Element shape matters alongside collection size.

An explicit cursor has another obligation: copying it must preserve its position, and later collection edits must preserve its snapshot. Some private cursor uses can be optimized, but a cursor that escapes needs those guarantees. A fast direct-loop result therefore does not establish the cost of every iterator pipeline.

Leave arrays their job#

Blot's arrays keep contiguous storage and constant-time indexing. They suit a known size, repeated positional reads, or a calculation that updates particular slots. An indexed update can reuse exclusively owned local storage; an observable earlier array must remain intact. Immutability applies to both collection types.

OperationListArray
Grow at an endReuse owned storage or copy an edited pathRuntime append copies the contents
Slice or joinShare whole subtrees; copy boundariesCopy contiguous storage
TraverseDense leaves with tree transitionsOne contiguous sequence
Read by indexNo public indexingConstant-time access
The runtime choices in the current implementation, pinned to revision 6b21965. Constant evaluation uses a separate representation.

Repeated runtime array appends pay for copying the growing prefix. If the final size is known, allocate it directly. If it emerges during filtering or generation, a list can collect the result before one explicit Array.from_list conversion. That conversion copies, so doing it repeatedly inside a loop would undo much of the point.

My bet is that growing, cutting, and walking deserve a collection designed around them. The measurements I care about follow those operations: bytes copied while building, storage retained after a cut, and time per element for the next traversal. Run them with and without saved versions, and with the actual element types. That is where this choice has to earn its place.