lib/list/list.x

Linked list with Var elements.

Primary API

Functions

car

inline Var car(List x)

Returns the head of x, or void when x is nil.

Source: lib/list/traversal.x:6

cdr

inline List cdr(List x)

Returns the tail of x, or nil when x is nil. Nil-safe like car. The tail is the same canonical structure the cell was built from.

Source: lib/list/traversal.x:12

cons

List cons(Var head, List tail)

Returns the canonical cons cell for head and tail. Repeating the call with the same head bits and canonical tail returns the same cell from the active pool chain. An ancestor hit remains owned there; a miss belongs to the active pool. The tail is shared, and nil is the null pointer.

Raises: <void-op> when head is void, or <alloc-fail>, <size-limit>, or <invariant> when a new canonical cell cannot be installed.

Source: lib/list/cells.x:14

Array

Array.list

List Array.list(Array arr)

Returns a new List holding the elements of arr in order. Cells are built from the end backwards through cons, so the result is canonical and shares whatever tail it already has in common with another List. arr is neither consumed nor freed.

Raises: <alloc-fail> while constructing the result.

Source: lib/list/building.x:11

Array.list_free

List Array.list_free(Array arr)

Returns arr.list() and frees arr. The conversion uses Array.list, so the result is canonical and may share existing cells, including cells owned by an ancestor pool. It does not adopt the Array’s storage. arr is released on success and when the conversion transfers an Error.

Raises: <alloc-fail> while constructing the result.

Source: lib/list/building.x:26

Iter

Iter.list

meta native List Iter.list(Iter iter)

Drains iter into a new List. The iterator is consumed to exhaustion, so this is meaningful once and never returns for an infinite source. Elements appear in iteration order.

Raises: whatever the iterator’s source raises, or <alloc-fail> while constructing the result.

Source: lib/list/building.x:64

List

List.all

int List.all(List lst, Func pred)

True when every element satisfies pred by ordinary Var truthiness. Stops at the first rejection. Nil is true; a null pred is false for a nonempty List.

Any cause raised by pred or its result’s truth operation propagates.

Source: lib/list/transformations.x:77

List.any

int List.any(List lst, Func pred)

True when at least one element satisfies pred by ordinary Var truthiness. Stops at the first accepted element. Nil and a null pred are false.

Any cause raised by pred or its result’s truth operation propagates.

Source: lib/list/transformations.x:66

List.append

Self List.append(Self a, Self b)

Returns the concatenation of a and b. Neither input is modified. b becomes the shared tail of the result, so only a’s cells are rebuilt, O(len(a)) of them. When either side is nil the other side is returned as it stands.

Raises: <alloc-fail> or <size-limit> while constructing the copied prefix.

Source: lib/list/building.x:79

List.array

Array List.array(List lst)

Returns a new Array holding the elements of lst in order. The Array is a fresh mutable container the caller owns and should free; the elements are shared, since they are only Vars. Convert when you need indexed access or in-place mutation.

Raises: <alloc-fail> or <size-limit> while constructing the result. The partial result is freed.

Source: lib/list/building.x:38

List.concat_n

List List.concat_n(unsigned list_count, ...)

Returns the concatenation of exactly list_count List arguments. Nil is a valid argument, no sentinel is read, and the final nonempty List becomes the shared tail of the result.

Raises: <size-limit> when list_count exceeds the supported index range, or <alloc-fail> while constructing the result.

Source: lib/list/building.x:92

List.contains

int List.contains(List lst, Var key)

Reports whether lst contains key by Var equality.

Source: lib/list/traversal.x:105

List.filter

Self List.filter(Self lst, Func pred)

Returns the elements pred accepts by ordinary Var truthiness. Elements are passed as values, and filtering nil gives nil without invoking or checking pred.

Raises: whatever Func.apply, pred, or result truthiness raises, or <alloc-fail> or <size-limit> while constructing the result. A null pred on nonempty input raises <bad-arg> from Func.apply.

Source: lib/list/transformations.x:27

List.find

Var List.find(List lst, Func pred)

Returns the first element pred accepts by ordinary Var truthiness, or void.

Any cause raised by pred or its result’s truth operation propagates. A null pred returns void.

Source: lib/list/transformations.x:55

List.foldl

Var List.foldl(List lst, Var seed, Func fn)

Folds fn over the elements of lst from the left, starting at seed. fn receives the accumulator and then the next element, and returns the next accumulator. A void seed means “no seed”: the first element becomes the initial accumulator and the fold starts at the second, and folding nil that way returns void. Empty input and a singleton with a void seed do not invoke fn. A null fn raises <bad-arg> when combining an element with the accumulator.

Any cause raised by fn propagates.

Source: lib/list/transformations.x:44

List.get

Var List.get(List list, Var key)

Looks up an integer index or association key in list. Integer keys use List.getindex, including negative indexes; every other key uses List.assoc. Either absent form returns void, as does an integer key outside the int index domain, which no List can reach.

Source: lib/list/traversal.x:142

List.getindex

Var List.getindex(List list, int index)

Returns list[index], or void when out of range. A negative index counts from the end and is found without a length pass.

Source: lib/list/traversal.x:118

List.getslice

meta native Self List.getslice(Self list, int start, int stop, int step)

Returns list[start:stop:step]. stop is exclusive, negative bounds count from the end, and a negative step walks backwards. A full forward slice preserves list only when its identity is canonical in the active pool chain; otherwise it rebuilds the cells there so a detached pool cannot escape through the shortcut.

Raises: <bad-arg> when step is zero, or <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list/traversal.x:228

List.head

meta native Self List.head(Self list, unsigned count)

Returns the first count elements of list. When count reaches or exceeds the length, list itself comes back, the same pointer. Lists are immutable, so sharing it is safe. Otherwise fresh canonical cells are built for the prefix.

Raises: <alloc-fail> or <size-limit> while constructing that prefix.

Source: lib/list/traversal.x:170

List.index

meta native int List.index(List l, Var key)

Returns the first index of key, or -1 when absent.

Source: lib/list/traversal.x:99

List.iter

Iter List.iter(List lst, Iter dest)

Initializes caller-owned dest as a forward iterator over lst. The iterator borrows the immutable cells and yields their stored Var bits without retaining them, so the owning pool must outlive iteration. A null dest returns NULL; nil produces an exhausted iterator.

Source: lib/list/traversal.x:68

List.last

Var List.last(List lst)

Returns the last value in lst, or void when it is empty.

Source: lib/list/traversal.x:91

List.len

int List.len(List lst)

Returns the number of cells in lst in O(n) time.

Source: lib/list/traversal.x:84

List.list_n

List List.list_n(unsigned element_count, ...)

Builds a List from exactly element_count Var arguments. Every argument is data, so void raises instead of being read as a terminator. A zero count returns nil.

Raises: <void-op> when an argument is void, or <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list/building.x:123

List.map

List List.map(List lst, Func fn)

Returns a canonical List holding fn applied front to back. Elements are passed as values, and mapping nil gives nil without invoking or checking fn. A null fn on nonempty input raises <bad-arg>, and a callback result of void raises <void-op> when the result List is built.

Raises: those causes, whatever Func.apply or fn raises, or <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list/transformations.x:13

List.map2

List List.map2(List a, List b, Func fn)

Maps fn over aligned pairs from a and b. A null callback returns nil without examining either List; otherwise this has the length, order, ownership, and failures of List.zip_with.

Source: lib/list/transformations.x:102

List.reverse

Self List.reverse(Self lst)

Returns a new List holding the elements of lst in reverse order. Fresh cells are built through cons, so the result is canonical and lst is untouched. Reversing nil gives nil.

Raises: <alloc-fail> while constructing the result.

Source: lib/list/building.x:146

List.sort

Self List.sort(Self lst)

Returns a copy of lst ordered by Var.compare. lst is unchanged. There is no comparator parameter. Var.compare orders the element tags involved, so a mixed-kind List still sorts. A List of fewer than two cells is returned as it stands.

Raises: whatever element comparison raises, or <alloc-fail> while constructing the result.

Source: lib/list/transformations.x:116

List.sort_by

Self List.sort_by(Self lst, Func key)

Returns a stable sorted copy using Array.sort_by’s callback contract. The key runs once per element in input order; an empty List invokes none. The input List is unchanged. Raises: allocation and the key’s ordinary causes, including failure to compare the resulting keys.

Source: lib/list/transformations.x:139

List.sort_with

Self List.sort_with(Self lst, Func compare)

Returns a stable sorted copy using Array.sort_with’s callback contract. The input List is unchanged. Fewer than two cells return unchanged without a callback. Raises: allocation and the comparator’s ordinary causes.

Source: lib/list/transformations.x:127

List.tail

meta native Self List.tail(Self list, unsigned count)

Returns the last count elements of list. The result is an existing tail of list, so nothing is allocated. When count reaches or exceeds the length, the whole list comes back.

Source: lib/list/traversal.x:184

List.try_next

int List.try_next(List lst, List &?cursor, Var &?out)

Writes the next element, advances cursor, and returns one. Initialize the caller-owned cursor to lst. A null pointer or an exhausted cursor returns zero without changing cursor or out. The cells are immutable, so only releasing the owning pool invalidates a cursor.

foreach (Var item, lst) compiles to this loop.

Source: lib/list/traversal.x:53

List.unique

meta native Self List.unique(Self lst)

Returns a copy of lst with later duplicates removed. The first occurrence of each value is kept and the original order is preserved. Duplicate detection runs through Iter.unique, whose state is held inside a Scope bracket that is released before returning. A List of fewer than two cells is returned as it stands.

Raises: causes from Map hashing or equality, or <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list/transformations.x:154

List.unpack_n

int List.unpack_n(List src, unsigned destination_count, ...)

Writes at most destination_count elements through List pointers. Returns the number written. Extra source cells are left unread, and a short source leaves remaining destinations untouched. Each source value is decoded as a List, so another tag writes nil; a null destination is skipped but still counted.

Raises: <size-limit> when destination_count exceeds INT_MAX. The failure occurs before any destination is written.

Source: lib/list/traversal.x:253

List.unpack_vars_n

int List.unpack_vars_n(List src, unsigned destination_count, ...)

Writes at most destination_count elements through Var pointers. Returns the number written. Extra source cells are left unread, and a short source leaves remaining destinations untouched. A null destination is skipped but still counted.

Raises: <size-limit> when destination_count exceeds INT_MAX. The failure occurs before any destination is written.

Source: lib/list/traversal.x:268

List.write_str

Buffer List.write_str(List lst, Buffer out)

Appends the List display text to out, using each element’s write_str. List.str calls this to build its result. The display form has one space inside each parenthesis, as in ( a b ), including when nested in another container. This method temporarily sets the destination Buffer’s padding to one and restores it afterward.

Source: lib/list/rendering.x:40

List.zip_with

List List.zip_with(List a, List b, Func fn)

Combines aligned values from two Lists with fn. A null fn produces two-element pair Lists. The shorter input determines the result length, and an empty input does not inspect the callback. A callback receives the left and right values and is invoked front to back.

Raises: whatever Func.apply, fn, or result canonicalization raises.

Source: lib/list/transformations.x:88

Map

Map.list

meta native List Map.list(Map map)

Returns the entries of map as a List of two-element (key value) Lists, in the map’s iteration order. This is the eager form of Map.enumerate: the pairs arrive as ordinary List data instead of through a cursor. An empty map returns nil. The pair cells are new; the keys and values are shared.

Raises: <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list/building.x:52

Advanced and interop API

List

List.assoc

Var List.assoc(List list, Var key)

Returns the second value of the first association whose key equals key. Nil entries are skipped. A missing association and a missing second value both return void, so the two cases look the same here.

Source: lib/list/traversal.x:155

List.caar

inline Var List.caar(List lst)

Returns car(car(lst)). Compound accessors read from right to left: a applies car and d applies cdr. Every step is nil-safe.

Source: lib/list/traversal.x:22

List.caddr

inline Var List.caddr(List lst)

Returns the third element, or void.

Source: lib/list/traversal.x:28

List.cadr

inline Var List.cadr(List lst)

Returns car(cdr(lst)), or void when there is no second element.

Source: lib/list/traversal.x:24

List.car

inline Var List.car(List lst)

Method form of car: the head of lst, or void when lst is nil.

Source: lib/list/traversal.x:15

List.cddr

inline Self List.cddr(Self lst)

Returns the tail after two cells, or nil.

Source: lib/list/traversal.x:26

List.cdr

inline Self List.cdr(Self lst)

Method form of cdr: the tail of lst, or nil when lst is nil.

Source: lib/list/traversal.x:17

List.compare

meta native int List.compare(List a, List b)

Compares a and b lexicographically through Var.compare. Element comparison causes propagate.

Source: lib/list/cells.x:61

List.cons

List List.cons(Var head, List tail)

Method form of cons, with the same identity, lifetime, and failures.

Source: lib/list/cells.x:20

List.cons_in

List List.cons_in(Pool pool, Var head, List tail)

Returns the canonical cell for head and tail in pool’s chain. An ancestor hit keeps that ancestor’s ownership; a miss is owned by pool. A null pool or void head returns nil without allocating. Any pool-managed graph reachable through head or tail is borrowed and must remain live for at least as long as the result.

Raises: <alloc-fail>, <size-limit>, or <invariant> while installing a new cell.

Source: lib/list/list.x:44

List.equal

int List.equal(List a, List b)

Reports equality of canonical chains by exact head and tail identity. It matches List.hash, so the same elements decide it: content for a small number, Symbol, Atom, canonical String, or nested List, and identity for a wide number boxed in a Scope, an Array, or a Map. Two Lists built from one long value hold two boxes and are unequal, while List.compare reads the values and calls them equal. Use List.compare where content has to decide.

Source: lib/list/cells.x:52

List.flatten

meta native Self List.flatten(Self lst)

Flattens one level of nested Lists into a canonical result. A nested nil contributes no element, non-List values retain their identity, and nil returns nil.

Raises: <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list/transformations.x:169

List.flatten_all

meta native Self List.flatten_all(Self lst)

Recursively flattens every nested List into a canonical result. Nested nil contributes no element and nil returns nil.

Raises: <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list/transformations.x:186

List.hash

meta native unsigned List.hash(List lst)

Returns the stable hash of List’s exact head bits and tail identity. This is a constant-time hash of one cell, which canonical cells make sound. It reaches an element’s content only when the Var word holds it: a small number, a Symbol, an Atom, a canonical String, or a nested List. An element the word points at hashes by identity, so a wide number boxed in a Scope, an Array, or a Map gives two equal-looking Lists two hashes. Mutating an object referenced by the head does not change this hash.

Source: lib/list/cells.x:35

List.nth_cdr

meta native Self List.nth_cdr(Self list, int n)

Returns the shared tail beginning n cells in. Returns nil past the end and list itself when n is nonpositive.

Source: lib/list/traversal.x:110

List.promote

meta native Self List.promote(Self lst)

Moves lst out of the innermost interning pool into its parent. Cells, nested Lists, interned String cars, and long Atom payloads all move together, so a promoted List keeps its complete identity graph across the matching Pool.close. Pointers never change and ancestor-owned structure is left where it is; the return value is lst itself.

Cells are immutable, so an ancestor-owned cell can only reference ancestor-owned cars and tails. The walk stops at the first cell the innermost pool does not own. Promoting an already-promoted List is therefore cheap. Var kinds other than String, Atom, and List are Scope-managed and outside pool jurisdiction.

When another thread’s pool promotes an equal cell first, that cell stays canonical; this one still survives, but Pool.is_permanent answers 0 for it. A null lst returns itself unchanged.

Source: lib/list/cells.x:91

List.repr

String List.repr(List lst)

Returns the re-readable rendering of lst. This is the %(...) spelling of the same data. Elements are rendered with their own repr, so Strings come back quoted and Atoms print as bare names, and nil renders as (). Long nested structure wraps at about 80 columns. The canonical result follows the active String pool chain, may already be owned by an ancestor, and remains live until that owner is released.

Raises: <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list/rendering.x:55

List.str

String List.str(List lst)

Returns the human-readable rendering of lst. Elements are rendered with their own str, so a String element appears unquoted. The writer pads inside parentheses and breaks nested structure across lines at about 80 columns. Nil renders as (). The canonical result follows the active String pool chain, may already be owned by an ancestor, and remains live until its owning pool is released. Use List.repr when the text has to read back in.

Raises: <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list/rendering.x:28

List.sublis

meta native List List.sublis(List alist, List tree)

Recursively substitutes non-List nodes in tree from alist. Each association is a List whose first value is the key and whose second value is the replacement. Unmatched leaves are shared; List structure is rebuilt canonically, and nil returns nil.

Raises: a cause from key equality, or <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list/transformations.x:207

List.subseq

meta native Self List.subseq(Self list, int start, int stop, int step)

Returns every stepth element from start up to exclusive stop. Negative bounds count from the end. step must be positive.

Raises: <bad-arg> when step is less than 1, or <alloc-fail> while constructing the result.

Source: lib/list/traversal.x:203

List.write_repr

Buffer List.write_repr(List lst, Buffer out)

Appends the readable representation of List to a Buffer.

Source: lib/list/rendering.x:62

Var

Var.caar

inline Var Var.caar(Var var)

Applies the caar selector chain to Var.

Source: lib/list/traversal.x:35

Var.caddr

inline Var Var.caddr(Var var)

Applies the caddr selector chain to Var.

Source: lib/list/traversal.x:41

Var.cadr

inline Var Var.cadr(Var var)

Applies the cadr selector chain to Var.

Source: lib/list/traversal.x:37

Var.car

Var Var.car(Var var)

Treats var as a List and returns its first element.

Source: lib/list/traversal.x:31

Var.cddr

inline List Var.cddr(Var var)

Applies the cddr selector chain to Var.

Source: lib/list/traversal.x:39

Var.cdr

List Var.cdr(Var var)

Treats var as a List and returns its tail.

Source: lib/list/traversal.x:33

Var.cons

List Var.cons(Var head, List tail)

Returns cons(head, tail), with the same identity and failures.

Source: lib/list/cells.x:22

Runtime-internal callables

These callables connect runtime translation units. They are documented for source readers but are not supported as user API.

List

List.try_own

int List.try_own(List lst)

Proves lst and its canonical children safe beyond every active pool. Returns 1 when the complete value is nil, already permanent, or can be promoted to the outermost List and String pools. Returns 0 when an active pool does not own part of the value. A zero result may follow successful promotion of an earlier cell or child. A thread that loses a concurrent promotion of an equal value still gets 1, though Pool.is_permanent answers 0 for its surviving copy.

Raises: <alloc-fail> when promotion metadata cannot be allocated.

Source: lib/list/cells.x:119

Public types

List

typedef struct List { Var car; struct List *cdr; } *List

Names an immutable canonical cons cell, or nil as NULL. A nonnull cell is borrowed from the pool that owns its exact car and tail identity; callers neither mutate nor free it. The car is never void, and the tail is nil or another live canonical List.

Source: lib/list/list.x:28

Design notes

List owns canonical immutable cons chains. A car holds any non-void Var and a cdr is nil or another List; identity is the car’s exact bits plus the canonical tail, so mutating an Array or Map stored in a car leaves the identity of its cell unchanged.

Construction searches the requested pool and its ancestors: an existing cell keeps its ancestor’s lifetime, and a miss belongs to the requested pool. Releasing a nested pool invalidates its unpromoted cells, while promotion keeps whole canonical List, String, and long-Atom structure at the same addresses. void is a terminal sentinel and never List data.

Tests and examples

make verify (unittest/test-list.x) and make examples (docs-tour).