Module imm/list
Persistent immutable singly-linked list with O(1) prepend, head, and tail.
List(T) is a cons list backed by atomic object nodes for thread-safe
structural sharing. Multiple lists can share tails with no copying.
All elements must implement Send to guarantee thread safety.
Examples
{ List } :: import "std/imm/list";
xs := List(i32).new();
xs = xs.prepend(i32(3)).prepend(i32(2)).prepend(i32(1));
assert((xs.head().unwrap() == i32(1)), "head is 1");
assert((xs.len() == usize(3)), "length is 3");
head/tail/prepend are O(1) and share the tail, so keeping an older
version of a list costs nothing. Everything positional — get, len,
contains, reverse, concat — walks the chain and is O(n); imm.Vec
is the one to reach for when indexing is the access pattern.
Stability
stable — this is the one imm container with nothing open against it in
plans/STD_API_STABILIZATION.md §4: the cons-list surface is complete
(prepend/head/tail plus the functional combinators), IntoIterator
landed 2026-09-08 walking the chain at O(1) per step, and the remove
shape question that holds up imm.Map / imm.Set does not arise —
removal from a cons list is filter. tests/imm_list.test.yo and
tests/imm_iterators.test.yo cover it. Additions such as append or
zip would be additive.
Types
Persistent immutable singly-linked list.
A value-type wrapper around an optional chain of ListNode atomic objects.
Cheap to copy (just a pointer + length). All "modification" operations
return a new List that shares structure with the original.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: (Send, Acyclic)), List(T), Acyclic())
impl(generic(T : Type), where(T <: (Send, Acyclic)), List(T), ...)
new : (fn() -> Self)Create an empty list.
Returns: Self
len : (fn(self : Self) -> usize)Return the number of elements.
Returns: usize
is_empty : (fn(self : Self) -> bool)Return true if the list is empty.
Returns: bool
prepend : (fn(self : Self, value : T) -> Self)Return a new list with value at the front. O(1).
Returns: Self
head : (fn(self : Self) -> Option(T))Return the first element, or .None if empty. O(1).
Returns: Option(T)
tail : (fn(self : Self) -> Self)Return a new list without the first element. O(1). Returns an empty list if already empty.
Returns: Self
get : (fn(self : Self, index : usize) -> Option(T))Access element at index. O(n).
Returns .None if index is out of bounds.
Returns: Option(T)
reverse : (fn(self : Self) -> Self)Return a new list with elements in reverse order. O(n).
Returns: Self
concat : (fn(self : Self, other : Self) -> Self)Concatenate two lists. O(n) where n = self.len().
The resulting list contains all elements of self followed by other.
Returns: Self
map : (fn(generic(U : Type), self : Self, f : Impl(Fn(a : T) -> U), where(U <: (Send, Acyclic))) -> List(U))Apply a function to each element, producing a new list. O(n).
Returns: List(U)
filter : (fn(self : Self, f : Impl(Fn(a : T) -> bool)) -> Self)Keep only elements satisfying the predicate. O(n).
Returns: Self
fold : (fn(generic(U : Type), self : Self, init : U, f : Impl(Fn(acc : U, item : T) -> U)) -> U)Left fold over the list. O(n).
Returns: U
for_each : (fn(self : Self, f : Impl(Fn(a : T) -> unit)) -> unit)Execute a function for each element. O(n).
Returns: unit
contains : (fn(self : Self, value : T, where(T <: Eq(T))) -> bool)Check if the list contains a value. O(n). Requires T to implement Eq.
Returns: bool
from_list : (fn(l : ArrayList(T)) -> Self)Build a list from a slice. O(n).
Returns: Self
impl(generic(T : Type), where(T <: (Send, Acyclic, Eq(T))), List(T), Eq(List(T))(...))
impl(generic(T : Type), where(T <: (Send, Acyclic)), List(T), Index(usize)(...))
Output : Tindex : (fn(inout(self) : Self, idx : usize) -> *Self.Output)impl(generic(T : Type), where(T <: (Send, Acyclic)), List(T), IntoIterator(...))
Item : TIntoIter : ListIter(T)into_iter : (fn(self : Self) -> ListIter(T))Returns: ListIter(T)
impl(generic(T : Type), where(T <: (Send, Acyclic)), List(T), Default(...))
default : (fn() -> Self)The default value of the type.
Returns: Self
Internal cons cell — atomic object for thread-safe structural sharing.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: (Send, Acyclic)), ListNode(T), Acyclic())
Iterator over a List's elements, head to tail.
Walks the cons chain, so it is O(1) per step and allocates nothing — the
nodes already exist. This is also the iterator the four hash/tree
containers reach for: Map.entries(), Set.to_list() and friends already
return a List, so their into_iter is this one over that list.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: (Send, Acyclic)), ListIter(T), Iterator(...))
Item : Tnext : (fn(inout(self) : Self) -> Option(T))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(T)