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");
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(forall(T : Type), where(T <: Send), 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(forall(U : Type), self : Self, f : Impl(Fn(a : T) -> U), where(U <: Send)) -> 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(forall(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_slice : (fn(s : Slice(T)) -> Self)Build a list from a slice. O(n).
Returns: Self