std.list

List operations module. Pay special attention to move semantics: there are two kinds of functions — those that only read-borrow the source list, and those that consume (move) the source list. The automatic borrow rules for & parameters are described in RFC-009 §2.8: when the argument is still used after the call, the compiler automatically creates a read-only token.

use std.list

Semantic classification

Parameters with & in the signature are read-only borrows, and the source value remains usable after the call; parameters without & are passed by value, and after the call the source value has been moved; using it again will report E2014.

Category	Functions	Behavior
Consume source list	push append prepend set pop remove_at	Source list is moved, cannot be used afterwards
Read-only borrow	len is_empty get first last slice reverse concat contains find_index map filter reduce	Source list can be reused
Iterator protocol	iter (consume source list, return iterator) has_next next (borrow / mutable borrow the iterator)	See below

use std.assert
use std.list

main: () -> Void = {
    nums = [1, 2, 3]

    // Read-only borrow: nums can be reused
    assert(list.len(nums) == 3)
    assert(list.len(nums) == 3)
    assert(list.contains(nums, 2))

    // Consume: base cannot be used after this
    base = [1, 2]
    extended = list.push(base, 3)
    assert(list.len(extended) == 3)
}

Function overview

Function	Signature
push	(A: Type) -> (list: Vec(A), item: A) -> Vec(A)
pop	(A: Type) -> (list: Vec(A)) -> Vec(A)
append	(A: Type) -> (list: Vec(A), item: A) -> Vec(A)
prepend	(A: Type) -> (list: Vec(A), item: A) -> Vec(A)
remove_at	(A: Type) -> (list: Vec(A), index: Int) -> Vec(A)
reverse	(A: Type) -> (list: &Vec(A)) -> Vec(A)
concat	(A: Type) -> (a: &Vec(A), b: &Vec(A)) -> Vec(A)
map	(T: Type, R: Type) -> (list: &Vec(T), f: (item: T) -> R) -> Vec(R)
filter	(T: Type) -> (list: &Vec(T), keep: (item: T) -> Bool) -> Vec(T)
reduce	(T: Type, Acc: Type) -> (list: &Vec(T), f: (acc: Acc, item: T) -> Acc, init: Acc) -> Acc
len	(A: Type) -> (list: &Vec(A)) -> Int
is_empty	(A: Type) -> (list: &Vec(A)) -> Bool
get	(A: Type) -> (list: &Vec(A), index: Int) -> A
set	(A: Type) -> (list: Vec(A), index: Int, value: A) -> Vec(A)
first	(A: Type) -> (list: &Vec(A)) -> A
last	(A: Type) -> (list: &Vec(A)) -> A
slice	(A: Type) -> (list: &Vec(A), start: Int, end: Int) -> Vec(A)
contains	(A: Type) -> (list: &Vec(A), item: A) -> Bool
find_index	(A: Type) -> (list: &Vec(A), item: A) -> Int
iter	(T: Type) -> (list: Vec(T)) -> Iter(T)
next	(T: Type) -> (it: &mut Iter(T)) -> T
has_next	(T: Type) -> (it: &Iter(T)) -> Bool
empty	(T: Type) -> Vec(T)
of	(T: Type) -> (data: Vec(T)) -> Vec(T)

## Functions

push

push: (A: Type) -> (list: Vec(A), item: A) -> Vec(A)

Returns a new list with item appended to the end of list. list is passed by value, and is moved after the call; it cannot be used again.

use std.assert
use std.list

main: () -> Void = {
    base = [1, 2]
    extended = list.push(base, 3)
    assert(list.len(extended) == 3)
}

append

append: (A: Type) -> (list: Vec(A), item: A) -> Vec(A)

An alias for push, with identical behavior.

use std.assert
use std.list

main: () -> Void = {
    extended = list.append([1, 2], 3)
    assert(list.len(extended) == 3)
}

prepend

prepend: (A: Type) -> (list: Vec(A), item: A) -> Vec(A)

Returns a new list with item inserted at the head of list. list is passed by value and is moved after the call.

use std.assert
use std.list

main: () -> Void = {
    l = list.prepend([2, 3], 1)
    assert(list.first(l) == 1)
}

pop

pop: (A: Type) -> (list: Vec(A)) -> Vec(A)

Removes the last element and returns the shortened list (value semantics). The source list is consumed, and is no longer the native form's exceptional case of "signature with & that mutates the source in place".

Returns: a new list with the last element removed; if the list is empty, returns it as is. To read the removed element, use last to get the value before calling.

use std.assert
use std.list

main: () -> Void = {
    l = [1, 2, 3]
    rest = list.pop(l)               // l is consumed; rest is the new shortened list
    assert(list.len(rest) == 2)
    assert(list.last(rest) == 2)     // the last element 3 has been removed

    // To read the removed element, get the value with last before popping
    l2 = [1, 2, 3]
    removed = list.last(l2)
    assert(removed == 3)

    empty = list.empty(Int)
    assert(list.is_empty(list.pop(empty)))
}

remove_at

remove_at: (A: Type) -> (list: Vec(A), index: Int) -> Vec(A)

Removes the element at index index and returns a new shortened list (value semantics). The source list is consumed.

• index — element index

Returns: a new list with that element removed. Errors: throws E6003 (index out of bounds) when the index is negative or ≥ length.

use std.assert
use std.list

main: () -> Void = {
    l = [10, 20, 30]
    got = list.remove_at(l, 1)
    assert(list.len(got) == 2)
    assert(list.get(got, 0) == 10)
    assert(list.get(got, 1) == 30)
}

set

set: (A: Type) -> (list: Vec(A), index: Int, value: A) -> Vec(A)

Returns a new list with index index overwritten with value. list is passed by value and is moved after the call.

• index — index; defaults to 0
• value — new value; defaults to Void

Errors: throws E6003 when the index is negative or ≥ length (out-of-bounds writes are no longer silently dropped).

use std.assert
use std.list

main: () -> Void = {
    l = list.set([1, 2, 3], 1, 99)
    assert(list.get(l, 1) == 99)
}

get

get: (A: Type) -> (list: &Vec(A), index: Int) -> A

Reads the element at index index (read-only borrow; list can be reused).

• index — index; defaults to 0

Returns: the element value; returns Void on out-of-bounds (no error thrown). Errors: throws E6007 when the index is negative.

use std.assert
use std.list

main: () -> Void = {
    nums = [1, 2, 3, 4]
    assert(list.get(nums, 1) == 2)
}

first

first: (A: Type) -> (list: &Vec(A)) -> A

Returns the first element; returns Void for an empty list.

use std.assert
use std.list

main: () -> Void = {
    assert(list.first([1, 2, 3]) == 1)
}

last

last: (A: Type) -> (list: &Vec(A)) -> A

Returns the last element; returns Void for an empty list.

use std.assert
use std.list

main: () -> Void = {
    assert(list.last([1, 2, 3]) == 3)
}

slice

slice: (A: Type) -> (list: &Vec(A), start: Int, end: Int) -> Vec(A)

Takes a sublist over the interval [start, end).

• start — start index; defaults to 0
• end — end index (exclusive); defaults to the end of the list

Returns: a new list. Boundaries are clamped to the valid range, no error is thrown. Errors: throws E6007 when start or end is negative.

use std.assert
use std.list

main: () -> Void = {
    sub = list.slice([1, 2, 3, 4], 1, 3)
    assert(list.len(sub) == 2)
    assert(list.first(sub) == 2)
}

reverse

reverse: (A: Type) -> (list: &Vec(A)) -> Vec(A)

Returns a new list with elements in reverse order; the source list is unchanged.

use std.assert
use std.list

main: () -> Void = {
    rev = list.reverse([1, 2, 3])
    assert(list.first(rev) == 3)
}

concat

concat: (A: Type) -> (a: &Vec(A), b: &Vec(A)) -> Vec(A)

Concatenates two lists and returns a new list. Neither source list is changed.

Errors: throws E6007 when the second argument is not a list.

use std.assert
use std.list

main: () -> Void = {
    joined = list.concat([1, 2], [3, 4])
    assert(list.len(joined) == 4)
}

len

len: (A: Type) -> (list: &Vec(A)) -> Int

Number of elements. Read-only borrow; list can be reused.

Errors: throws E6007 when the argument is not a list.

use std.assert
use std.list

main: () -> Void = {
    nums = [1, 2, 3]
    assert(list.len(nums) == 3)
    assert(list.len(nums) == 3)      // can be reused
}

is_empty

is_empty: (A: Type) -> (list: &Vec(A)) -> Bool

Whether the list is empty.

Errors: throws E6007 when the argument is not a list.

use std.assert
use std.list

main: () -> Void = {
    assert(list.is_empty([]))
    assert(!list.is_empty([1]))
}

contains

contains: (A: Type) -> (list: &Vec(A), item: A) -> Bool

Whether item is in the list (compared by value equality; the element type must support == — primitive types support it natively; for record types, it is provided by automatic derivation or explicit instantiation of Equal per RFC-011b).

Returns: true if present; false if the argument is not a list.

use std.assert
use std.list

main: () -> Void = {
    nums = [1, 2, 3, 4]
    assert(list.contains(nums, 3))
    assert(!list.contains(nums, 99))
}

find_index

find_index: (A: Type) -> (list: &Vec(A), item: A) -> Int

The index of the first occurrence of item.

Returns: the index if found; -1 if not found.

use std.assert
use std.list

main: () -> Void = {
    assert(list.find_index([1, 2, 3, 4], 3) == 2)
    assert(list.find_index([1, 2], 99) == -1)
}

map

map: (T: Type, R: Type) -> (list: &Vec(T), f: (item: T) -> R) -> Vec(R)

Calls fn on each element and returns a new list of the results. Passing a function value uses the curried form: list.map(nums, x => x * 2). The source list is unchanged.

Errors: throws E6007 when the second argument is not a function.

use std.assert
use std.list

main: () -> Void = {
    doubled = list.map([1, 2, 3], x => x * 2)
    assert(list.get(doubled, 0) == 2)
}

filter

filter: (T: Type) -> (list: &Vec(T), keep: (item: T) -> Bool) -> Vec(T)

Keeps the elements for which fn returns true. The source list is unchanged.

Errors: throws E6007 when the second argument is not a function.

use std.assert
use std.list

main: () -> Void = {
    evens = list.filter([1, 2, 3, 4], x => x % 2 == 0)
    assert(list.len(evens) == 2)
}

reduce

reduce: (T: Type, Acc: Type) -> (list: &Vec(T), f: (acc: Acc, item: T) -> Acc, init: Acc) -> Acc

Folds from left to right: starting with init, fn(acc, item) is called in turn.

• fn — the reduce function (accumulator, element) -> new accumulator
• init — the initial accumulator

Returns: the final accumulator. Returns init when the list is empty.

Errors: throws E6007 when the second argument is not a function.

use std.assert
use std.list

main: () -> Void = {
    total = list.reduce([1, 2, 3, 4], (acc, x) => acc + x, 0)
    assert(total == 10)
}

iter

iter: (T: Type) -> (list: Vec(T)) -> Iter(T)

Creates an iterator. The iterator is a (list, index) tuple carrying state, and after creation it is consumed sequentially in next. The source list is held by read-only borrow and remains usable during iteration.

Returns: an iterator tuple, to be used with next / has_next.

use std.assert
use std.list

main: () -> Void = {
    it = list.iter([1, 2, 3])
    assert(list.has_next(it))
}

next

next: (T: Type) -> (it: &mut Iter(T)) -> T

Takes the current element and advances the internal index by one.

Returns: the current element; returns Void when iteration ends.

Both next and has_next move the iterator (the signature has no &), so every access requires recreating the iterator, or simply using for ... in to traverse. This differs from the borrow form of std.range.next.

use std.assert
use std.list

main: () -> Void = {
    it = list.iter([7, 8])
    assert(list.next(it) == 7)
}

has_next

has_next: (T: Type) -> (it: &Iter(T)) -> Bool

Whether there are still unconsumed elements.

use std.assert
use std.list

main: () -> Void = {
    it = list.iter([1])
    assert(list.has_next(it))
}

Iterating with for ... in

Lists can be iterated directly with for ... in, without manually calling next:

use std.assert

main: () -> Void = {
    mut sum = 0
    for x in [1, 2, 3] {
        sum = sum + x
    }
    assert(sum == 6)
}

Related

• std.range — range iteration and lazy adapters
• std.assert — assertion utility used in the examples