lib/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.x:171

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.x:177

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.x:157

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.x:463

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.x:472

Iter

Iter.list

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.x:1010

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.x:407

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.x:392

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.x:223

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.

Source: lib/list.x:497

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.x:255

List.contains

int List.contains(List lst, Var key)

Reports whether lst contains key by Var equality.

Source: lib/list.x:315

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.x:1023

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.x:377

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. A null fn returns the accumulator untouched, which for a void seed is the head.

Any cause raised by fn propagates.

Source: lib/list.x:353

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.x:663

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.x:626

List.getslice

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.x:736

List.head

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.x:696

List.index

int List.index(List l, Var key)

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

Source: lib/list.x:309

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.x:999

List.last

Var List.last(List lst)

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

Source: lib/list.x:301

List.len

int List.len(List lst)

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

Source: lib/list.x:318

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.x:279

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.x:333

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.x:549

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.x:292

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.x:424

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.x:449

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.x:436

List.tail

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.x:676

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.x:987

List.unique

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.x:512

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.x:780

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.x:795

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.x:942

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.x:528

Map

Map.list

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, for a caller that wants the pairs as ordinary List data rather than 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.x:484

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.x:649

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.x:187

List.caddr

inline Var List.caddr(List lst)

Returns the third element, or void.

Source: lib/list.x:193

List.cadr

inline Var List.cadr(List lst)

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

Source: lib/list.x:189

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.x:180

List.cddr

inline Self List.cddr(Self lst)

Returns the tail after two cells, or nil.

Source: lib/list.x:191

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.x:182

List.compare

int List.compare(List a, List b)

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

Source: lib/list.x:840

List.cons

List List.cons(Var head, List tail)

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

Source: lib/list.x:166

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.x:49

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.x:831

List.flatten

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.x:584

List.flatten_all

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.x:608

List.hash

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.x:814

List.nth_cdr

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.x:618

List.promote

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.

A null lst returns itself unchanged.

Source: lib/list.x:120

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.x:958

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.x:930

List.sublis

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.x:573

List.subseq

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.x:722

List.write_repr

Buffer List.write_repr(List lst, Buffer out)

Appends the readable representation of List to a Buffer.

Source: lib/list.x:965

Var

Var.caar

inline Var Var.caar(Var var)

Applies the caar selector chain to Var.

Source: lib/list.x:200

Var.caddr

inline Var Var.caddr(Var var)

Applies the caddr selector chain to Var.

Source: lib/list.x:206

Var.cadr

inline Var Var.cadr(Var var)

Applies the cadr selector chain to Var.

Source: lib/list.x:202

Var.car

Var Var.car(Var var)

Treats var as a List and returns its first element.

Source: lib/list.x:196

Var.cddr

inline List Var.cddr(Var var)

Applies the cddr selector chain to Var.

Source: lib/list.x:204

Var.cdr

List Var.cdr(Var var)

Treats var as a List and returns its tail.

Source: lib/list.x:198

Var.cons

List Var.cons(Var head, List tail)

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

Source: lib/list.x:168

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.

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

Source: lib/list.x:145

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.x:32

Design notes

List is an immutable, interned cons chain. A car may hold any non-void Var; a cdr is nil or another List. Canonical identity is the car’s exact Var bits plus the canonical tail identity, so mutating an Array or Map stored in a car does not change the identity of the cell that contains it.

Construction searches the requested pool and its ancestors. An existing cell keeps its ancestor’s lifetime; a miss belongs to the requested pool. Releasing a nested pool invalidates its unpromoted cells, while promotion preserves complete canonical List, String, and long-Atom structure without changing pointers. void is a terminal sentinel, not List data.

Tests and examples

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