list

stdlib/list.hk: List<T> as methods on impl<T> List<T>.

Storage is a runtime-side persistent List, an RRB vector, opaque to user code. Four intrinsics bottom out in Rust: empty / append : fresh persistent lists; append is O(1)-amortized and leaves the original unchanged length : returns i32 length get : bounds-checked indexed read, returns Option<T>

The surface is method-style: xs.append(x), xs.length, xs.get(i), plus List<T>.empty() as an associated function. The C-ABI symbols are hanki_intrinsic_list_list_* (per intrinsic_c_abi_symbol's qualification of the new list.List.NAME qualified name).

option.Option, option.Some, option.None are reached bare through this open option directive: get returns Option<T> and find / map / each! pattern-match on Some/None.

List

type List<T>
end

impl<T> List<T>

empty

def empty() -> List<T>

The empty list. The element type is fixed by the binding it flows into.

xs: List<i32> = List.empty()
xs.length => 0

append

def append(self, x: T) -> List<T>

Returns a new list with x appended; the original is unchanged (persistent).

xs: List<i32> = List.empty().append(7i32)
xs.get(0) => Some(7i32)

length

prop length(self) -> int

The number of elements.

xs: List<i32> = List.empty().append(1i32).append(2i32)
xs.length => 2

empty?

prop empty?(self) -> bool

True when the list has no elements. xs.empty? is xs.length == 0.

xs: List<i32> = List.empty()
xs.empty?              => true
xs.append(1i32).empty? => false

get

def get(self, i: int) -> Option<T>

The element at index i, or None when i is out of bounds (including a negative index).

xs: List<i32> = List.empty().append(7i32)
xs.get(0) => Some(7i32)
xs.get(9) => None

get_or

def get_or(self, i: int, fallback: T) -> T

The element at index i, or fallback when i is out of bounds.

xs.get_or(i, d) is xs.get(i).unwrap_or(d) without the Option. That is why it exists: get allocates a Some on the heap for every read, and a caller that immediately unwraps it has paid for a value it discards. In a scan over a table or a buffer that allocation is most of the cost.

xs: List<i32> = List.empty().append(7i32)
xs.get_or(0, 0i32) => 7i32
xs.get_or(9, 0i32) => 0i32

first

prop first(self) -> Option<T>

The first element, or None for the empty list. xs.first is xs.get(0).

xs: List<i32> = List.empty().append(7i32).append(8i32)
xs.first => Some(7i32)
empty: List<i32> = List.empty()
empty.first => None

last

prop last(self) -> Option<T>

The last element, or None for the empty list. A thin get(length - 1): the empty list's -1 index is out of bounds, and it is therefore None.

xs: List<i32> = List.empty().append(7i32).append(8i32)
xs.last => Some(8i32)
empty: List<i32> = List.empty()
empty.last => None

concat

def concat(self, other: List<T>) -> List<T>

The concatenation of self and other, in order; both inputs are unchanged (persistent). O(log n).

xs: List<i32> = List.empty().append(1i32).append(2i32)
ys: List<i32> = List.empty().append(3i32)
xs.concat(ys).get(2) => Some(3i32)

slice

def slice(self, lo: int, hi: int) -> List<T>

The sub-list [lo, hi), clamped to the list bounds (a negative or past-the-end endpoint is pulled into range). The source is unchanged. O(log n).

xs: List<i32> = List.empty().append(10i32).append(20i32).append(30i32)
xs.slice(1, 3).get(0) => Some(20i32)
xs.slice(1, 3).length => 2

update

def update(self, i: int, x: T) -> List<T>

A new list with index i replaced by x; an out-of-bounds i yields the list unchanged. The original is untouched (persistent). O(log n).

xs: List<i32> = List.empty().append(1i32).append(2i32)
xs.update(1, 9i32).get(1) => Some(9i32)
xs.get(1) => Some(2i32)

prepend

def prepend(self, x: T) -> List<T>

A new list with x at the front, followed by every element of self.

xs: List<i32> = List.empty().append(2i32).append(3i32)
xs.prepend(1i32).get(0) => Some(1i32)
xs.prepend(1i32).length => 3

find

def find(self, pred: (T) -> bool) -> Option<T>

The first element satisfying pred, or None if none does.

xs: List<i32> = List.empty().append(1i32).append(5i32).append(9i32)
xs.find(|x: i32| x > 3i32) => Some(5i32)

A counting loop, like every linear walk below: per-element recursion would consume call stack proportional to the length: a native stack overflow on the AOT tier for ordinary long lists.

find!

def find!(self, pred: (T) -> bool [e]) -> Option<T> [e]

find with an effectful predicate: the first element for which pred accepts, or None. It short-circuits, and pred runs only up to the match.

xs: List<i32> = List.empty().append(1i32).append(5i32).append(9i32)
xs.find!(|x: i32| x > 3i32) => Some(5i32)

find_map

def find_map(self, f: (T) -> Option<U>) -> Option<U>

The first Some that f produces, or None when f yields None for every element: find and map fused. It short-circuits: f is applied to each element only until the first Some. O(n) worst case.

xs: List<i32> = List.empty().append(2i32).append(3i32)
xs.find_map(|x: i32| Some(x * 10i32)) => Some(20i32)
os: List<Option<i32>> = List.empty().append(None).append(Some(5i32))
os.find_map(|o: Option<i32>| o) => Some(5i32)

find_map!

def find_map!(self, f: (T) -> Option<U> [e]) -> Option<U> [e]

find_map with an effectful f: the first Some it produces, or None. It short-circuits, f is applied only up to the first Some, and the remaining elements' effects never happen.

xs: List<i32> = List.empty().append(2i32).append(3i32)
xs.find_map!(|x: i32| Some(x * 10i32)) => Some(20i32)

map

def map(self, f: (T) -> U) -> List<U>

A new list with f applied to every element, in order; the source is unchanged.

xs: List<i32> = List.empty().append(1i32).append(2i32)
ys = xs.map(|x: i32| x * 10i32)
ys.get(0) => Some(10i32)
ys.get(1) => Some(20i32)

map!

def map!(self, f: (T) -> U [e]) -> List<U> [e]

map with an effectful transform: the results of f over every element, in order. f runs once per element, left to right, and a transform that also prints or writes does so in that order.

xs: List<i32> = List.empty().append(1i32).append(2i32)
ys = xs.map!(|x: i32| x * 10i32)
ys.get(0) => Some(10i32)
ys.get(1) => Some(20i32)

each!

def each!(self, f: (T) -> () [e]) -> () [e]

Applies the effectful f to every element in order, for its effects. @no-doctest: effectful iteration returning unit; no value to assert; see io for effectful-callback examples

eachwithindex!

def each_with_index!(self, f: (T, int) -> () [e]) -> () [e]

Applies the effectful f to each element with its index, in order. @no-doctest: effectful iteration returning unit; no value to assert; see io for effectful-callback examples

fold

def fold(self, init: U, f: (U, T) -> U) -> U

The left fold of f over the elements: f(…f(f(init, x₀), x₁)…, xₙ). An empty list folds to init.

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
xs.fold(0i32, |acc: i32, x: i32| acc + x) => 6i32

fold!

def fold!(self, init: U, f: (U, T) -> U [e]) -> U [e]

fold with an effectful step. This is the combinator to reach for when an accumulator has to survive an effectful traversal: a closure captures by value (HANKI.md §13), and accumulating into a var from inside an each! block cannot work and is rejected (H0209); fold! threads the accumulator through instead and returns it.

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
xs.fold!(0i32, |acc: i32, x: i32| acc + x) => 6i32

try_fold

def try_fold(self, init: U, f: (U, T) -> Result<U, E>) -> Result<U, E>

fold that can stop: the step returns Result, and the first Err ends the traversal as the result; later elements are not visited. An empty list gives Ok(init). The composition this improves on - fold with the Result threaded through and_then - answers the same value but cannot stop: and_then passes the first Err untouched to the end, and the step still runs once per element. Here a long list that fails early costs only the elements before the failure.

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
xs.try_fold(0i32, |acc: i32, x: i32| Ok(acc + x)) => Ok(6i32)
xs.try_fold(0i32, |acc: i32, x: i32| if x == 2i32 then Err("two") else Ok(acc + x)) => Err("two")
ys: List<i32> = List.empty()
ys.try_fold(7i32, |acc: i32, x: i32| Err("never")) => Ok(7i32)

try_each

def try_each(self, f: (T) -> Result<(), E>) -> Result<(), E>

A validation sweep that can stop: applies the pure f in order and answers the first Err, or Ok(()) when every element passes. As with try_fold, the and_then composition answers the same value but runs f once per element regardless; this stops at the failure.

xs: List<i32> = List.empty().append(2i32).append(4i32)
xs.try_each(|x: i32| if x % 2i32 == 0i32 then Ok(()) else Err(x)) => Ok(())
xs.try_each(|x: i32| if x < 3i32 then Ok(()) else Err(x)) => Err(4i32)

try_fold!

def try_fold!(self, init: U, f: (U, T) -> Result<U, E> [e]) -> Result<U, E> [e]

fold! that can stop: the step returns Result, and the first Err ends the traversal as the result. Later elements are not visited, and their effects never happen. An empty list gives Ok(init). This is the combinator for a fallible effectful pass; threading failure through a plain fold! means a poisoned accumulator every later step must re-check, and accumulating into a var from inside each! is rejected (H0209).

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
xs.try_fold!(0i32, |acc: i32, x: i32| Ok(acc + x)) => Ok(6i32)
xs.try_fold!(0i32, |acc: i32, x: i32| if x == 2i32 then Err("two") else Ok(acc + x)) => Err("two")
ys: List<i32> = List.empty()
ys.try_fold!(7i32, |acc: i32, x: i32| Err("never")) => Ok(7i32)

try_each!

def try_each!(self, f: (T) -> Result<(), E> [e]) -> Result<(), E> [e]

each! that can stop: f returns Result<(), E>, and the first Err ends the traversal as the result; later elements are not visited. The unit-accumulator convenience over try_fold! for the majority case: perform each element's effect, stop at the first failure.

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
xs.try_each!(|x: i32| if x == 2i32 then Err("two") else Ok(())) => Err("two")
xs.try_each!(|x: i32| if x > 0i32 then Ok(()) else Err("nonpositive")) => Ok(())

fold_right

def fold_right(self, init: U, f: (T, U) -> U) -> U

A right-associative fold: f(x0, f(x1, … f(xn, init))). f takes the element first and the accumulator second, and elements are visited right-to-left. On an associative f this matches fold; on a non-associative one (e.g. subtraction) it differs. O(n).

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
xs.fold_right(0i32, |x: i32, acc: i32| x - acc) => 2

scan

def scan(self, init: U, f: (U, T) -> U) -> List<U>

The successive accumulator values of a left fold: element i is f applied across elements 0..=i starting from init (an inclusive running fold; fold returns the final value alone). The result has the same length as self; the empty list yields the empty list. O(n).

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
ys: List<i32> = xs.scan(0i32, |acc: i32, x: i32| acc + x)
ys.length => 3
ys.get(0)   => Some(1i32)
ys.get(2)   => Some(6i32)

filter

def filter(self, pred: (T) -> bool) -> List<T>

The elements satisfying pred, in their original order.

xs: List<i32> = List.empty().append(1i32).append(8i32).append(2i32)
xs.filter(|x: i32| x < 5i32).length        => 2
xs.filter(|x: i32| x < 5i32).get(1)    => Some(2i32)

filter!

def filter!(self, pred: (T) -> bool [e]) -> List<T> [e]

filter with an effectful predicate: the elements pred accepts, in their original order. pred is evaluated once per element, and one that reads the filesystem or the clock is called length times.

xs: List<i32> = List.empty().append(1i32).append(8i32).append(2i32)
xs.filter!(|x: i32| x < 5i32).length => 2
xs.filter!(|x: i32| x < 5i32).get(1) => Some(2i32)

filter_map

def filter_map(self, f: (T) -> Option<U>) -> List<U>

Map and retain the Somes, in order: filter and map fused, and the shape of every parse-a-row-or-skip-it loop. The alternative is a flat_map whose f answers a one- or zero-element list, which allocates a list per element in order to discard most of them.

ns: List<i32> = List.empty().append(10i32).append(0i32).append(4i32)
ns.filter_map(|n: i32| 100i32.checked_div(n)).length => 2
ns.filter_map(|n: i32| 100i32.checked_div(n)).get(1) => Some(25i32)
os: List<Option<i32>> = List.empty().append(Some(1i32)).append(None)
os.filter_map(|o: Option<i32>| o).length => 1

filter_map!

def filter_map!(self, f: (T) -> Option<U> [e]) -> List<U> [e]

filter_map with an effectful transform: f's Some results, in order. f is applied once per element, and one that reads the filesystem or the clock is called length times.

ns: List<i32> = List.empty().append(10i32).append(0i32).append(4i32)
ns.filter_map!(|n: i32| 100i32.checked_div(n)).length => 2
ns.filter_map!(|n: i32| 100i32.checked_div(n)).get(0) => Some(10i32)

reverse

def reverse(self) -> List<T>

The elements in reverse order.

xs: List<i32> = List.empty().append(1i32).append(2i32)
xs.reverse().get(0) => Some(2i32)
xs.reverse().get(1) => Some(1i32)

take

def take(self, n: int) -> List<T>

The first n elements. A thin slice(0, n), and n is therefore clamped: a negative n gives the empty list, an n past the end gives the whole list. The source is unchanged. O(log n).

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
xs.take(2).length => 2
xs.take(2).get(1)   => Some(2i32)
xs.take(9).length => 3

drop

def drop(self, n: int) -> List<T>

Every element after the first n. A thin slice(n, length()), and n is clamped: a negative n gives the whole list, an n past the end gives the empty list. The source is unchanged. O(log n).

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
xs.drop(1).length => 2
xs.drop(1).get(0)   => Some(2i32)
xs.drop(9).length => 0

take_last

def take_last(self, n: int) -> List<T>

The last n elements. A thin slice(length() - n, length()), and n is clamped: a non-positive n gives the empty list, an n past the end gives the whole list. The source is unchanged. O(log n).

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
xs.take_last(2).length => 2
xs.take_last(2).get(0)   => Some(2i32)
xs.take_last(9).length => 3

drop_last

def drop_last(self, n: int) -> List<T>

Every element except the last n. A thin slice(0, length() - n), and n is clamped: a non-positive n gives the whole list, an n past the end gives the empty list. The source is unchanged. O(log n).

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
xs.drop_last(1).length => 2
xs.drop_last(1).get(1)   => Some(2i32)
xs.drop_last(9).length => 0

any?

def any?(self, pred: (T) -> bool) -> bool

True when some element satisfies pred. Short-circuits on the first match (via find); false for the empty list.

xs: List<i32> = List.empty().append(1i32).append(5i32).append(9i32)
xs.any?(|x: i32| x > 8i32) => true
xs.any?(|x: i32| x > 9i32) => false

any!

def any!(self, pred: (T) -> bool [e]) -> bool [e]

any? with an effectful predicate. Short-circuits on the first element that satisfies pred, and the effects of the remaining elements never happen.

xs: List<i32> = List.empty().append(1i32).append(5i32).append(9i32)
xs.any!(|x: i32| x > 8i32) => true
xs.any!(|x: i32| x > 9i32) => false

all?

def all?(self, pred: (T) -> bool) -> bool

True where every element satisfies pred, and vacuously true for the empty list. Short-circuits on the first element that fails.

xs: List<i32> = List.empty().append(2i32).append(4i32).append(6i32)
xs.all?(|x: i32| x > 1i32) => true
xs.all?(|x: i32| x > 3i32) => false

all!

def all!(self, pred: (T) -> bool [e]) -> bool [e]

all with an effectful predicate, vacuously true for the empty list. It short-circuits on the first element that fails, and the effects of the remaining elements never happen.

xs: List<i32> = List.empty().append(2i32).append(4i32).append(6i32)
xs.all!(|x: i32| x > 1i32) => true
xs.all!(|x: i32| x > 3i32) => false

count

def count(self, pred: (T) -> bool) -> int

The number of elements satisfying pred, and 0 for the empty list. Like filter(pred).length but without building the intermediate list.

xs: List<i32> = List.empty().append(1i32).append(5i32).append(9i32)
xs.count(|x: i32| x > 4i32) => 2
xs.count(|x: i32| x > 9i32) => 0

count!

def count!(self, pred: (T) -> bool [e]) -> int [e]

count with an effectful predicate. It visits every element, and pred's effect happens length times; there is nothing to short-circuit.

xs: List<i32> = List.empty().append(1i32).append(5i32).append(9i32)
xs.count!(|x: i32| x > 4i32) => 2
xs.count!(|x: i32| x > 9i32) => 0

partition

def partition(self, pred: (T) -> bool) -> Pair<List<T>, List<T>>

Split into the elements satisfying pred (first) and those that do not (second), each in input order: filter and its complement in one O(n) walk. The predicate counterpart to no single existing method.

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32).append(4i32)
p: Pair<List<i32>, List<i32>> = xs.partition(|x: i32| x % 2i32 == 0i32)
p.first.length  => 2
p.first.get(0)  => Some(2i32)
p.second.length => 2
p.second.get(0) => Some(1i32)

partition!

def partition!(self, pred: (T) -> bool [e]) -> Pair<List<T>, List<T>> [e]

partition with an effectful predicate: the elements pred accepts (first) and those for which it does not (second), each in input order. pred is evaluated once per element, in one walk.

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32).append(4i32)
p: Pair<List<i32>, List<i32>> = xs.partition!(|x: i32| x % 2i32 == 0i32)
p.first.length  => 2
p.first.get(0)  => Some(2i32)
p.second.length => 2
p.second.get(0) => Some(1i32)

position

def position(self, pred: (T) -> bool) -> Option<int>

The index of the first element satisfying pred, or None where none do: bound-free, predicate counterpart to index_of. Short-circuits on the first match.

xs: List<i32> = List.empty().append(3i32).append(5i32).append(8i32)
xs.position(|x: i32| x > 4i32) => Some(1)
xs.position(|x: i32| x > 9i32) => None

take_while

def take_while(self, pred: (T) -> bool) -> List<T>

The longest prefix whose every element satisfies pred; stops before the first element that fails, or at the end. The complement of drop_while: position locates the first failing element, and take then takes the prefix before it. O(n) worst case (the prefix scan).

xs: List<i32> = List.empty().append(2i32).append(4i32).append(5i32).append(6i32)
xs.take_while(|x: i32| x < 5i32).length => 2
xs.take_while(|x: i32| x > 9i32).length => 0

take_while!

def take_while!(self, pred: (T) -> bool [e]) -> List<T> [e]

take_while with an effectful predicate: the longest prefix whose elements all satisfy pred. It stops at the first element that fails, and the rest of the list's effects never happen.

xs: List<i32> = List.empty().append(2i32).append(4i32).append(5i32).append(6i32)
xs.take_while!(|x: i32| x < 5i32).length => 2
xs.take_while!(|x: i32| x > 9i32).length => 0

A direct walk and no position plus take as the pure form uses: position takes a pure predicate, and the effectful one cannot be handed to it.

drop_while

def drop_while(self, pred: (T) -> bool) -> List<T>

The suffix left after dropping the longest prefix whose elements satisfy pred, the complement of take_while. Every element is dropped where they all satisfy pred; none are when the first already fails.

xs: List<i32> = List.empty().append(2i32).append(4i32).append(5i32).append(6i32)
xs.drop_while(|x: i32| x < 5i32).length => 2
xs.drop_while(|x: i32| x > 9i32).length => 4

min_by

def min_by(self, less: (T, T) -> bool) -> Option<T>

The minimum element by the less strict-before comparator (the one no element less-precedes), or None for the empty list. On a tie the earliest such element wins. The bound-free counterpart to min.

xs: List<i32> = List.empty().append(3i32).append(1i32).append(2i32)
xs.min_by(|a, b| a < b) => Some(1i32)
empty: List<i32> = List.empty()
empty.min_by(|a, b| a < b) => None

max_by

def max_by(self, less: (T, T) -> bool) -> Option<T>

The maximum element by the less strict-before comparator, or None for the empty list; on a tie the earliest wins. The maximum under less is the minimum under the reversed comparator, and this delegates to min_by.

xs: List<i32> = List.empty().append(1i32).append(3i32).append(2i32)
xs.max_by(|a, b| a < b) => Some(3i32)
empty: List<i32> = List.empty()
empty.max_by(|a, b| a < b) => None

enumerate

def enumerate(self) -> List<Pair<int, T>>

Each element paired with its index, in order: the pure indexed view. each_with_index! is an action and cannot take an index into a pure fold or map chain; this can.

xs: List<string> = List.empty().append("a").append("b")
xs.enumerate().get(1).map(|p| p.first)  => Some(1)
xs.enumerate().get(1).map(|p| p.second) => Some("b")

flat_map

def flat_map(self, f: (T) -> List<U>) -> List<U>

The concatenation of f's result lists, in element order.

xs: List<i32> = List.empty().append(1i32).append(2i32)
xs.flat_map(|x: i32| List.empty().append(x).append(x * 10i32)).length => 4

flat_map!

def flat_map!(self, f: (T) -> List<U> [e]) -> List<U> [e]

flat_map with an effectful transform: the concatenation of f's result lists, in element order.

xs: List<i32> = List.empty().append(1i32).append(2i32)
xs.flat_map!(|x: i32| List.empty().append(x).append(x * 10i32)).length => 4

zip_with

def zip_with(self, other: List<U>, f: (T, U) -> V) -> List<V>

Combine two lists element-wise with f, stopping at the shorter length: element i of the result is f(self[i], other[i]). This is zip without the Pair allocation: f consumes both elements at once. O(min of the two lengths).

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
ys: List<i32> = List.empty().append(10i32).append(20i32)
zs: List<i32> = xs.zip_with(ys, |a: i32, b: i32| a + b)
zs.length => 2
zs.get(0)   => Some(11i32)

zip

def zip(self, other: List<U>) -> List<Pair<T, U>>

Pair up two lists element-wise, stopping at the shorter length: element i of the result is Pair(first=self[i], second=other[i]). To combine the sides without allocating a Pair, use zip_with.

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
ys: List<string> = List.empty().append("a").append("b")
zs = xs.zip(ys)
zs.length => 2
zs.get(0).map(|p| p.first) => Some(1i32)
zs.get(1).map(|p| p.second) => Some("b")

appendall

def _append_all(self, src: List<U>, acc: List<U>) -> List<U>

Append every element of src onto acc, in order. append is O(1)-amortized, and this O(|src|) walk therefore beats concat's larger constant for the small per-element lists flat_map typically produces.

intersperse

def intersperse(self, sep: T) -> List<T>

sep inserted between every pair of adjacent elements; the empty and single-element lists are returned unchanged. O(n).

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
xs.intersperse(0i32).length => 5
xs.intersperse(0i32).get(1)   => Some(0i32)
xs.intersperse(0i32).get(2)   => Some(2i32)

chunk

def chunk(self, size: int) -> List<List<T>>

Consecutive sublists of at most size elements, in order; the final chunk is shorter when the length is not a multiple of size. A size of zero or less yields the empty list (no valid chunking). O(n).

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32).append(4i32).append(5i32)
xs.chunk(2).length                                 => 3
xs.chunk(2).first.unwrap_or(List.empty()).length => 2
xs.chunk(2).last.unwrap_or(List.empty()).length  => 1

windows

def windows(self, size: int) -> List<List<T>>

Every contiguous sublist of size elements, sliding one element at a time ([1, 2, 3].windows(2) is [[1, 2], [2, 3]]). A size past the length, or zero or less, yields the empty list. O(n log n): n slices, each an O(log n) structural view.

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32).append(4i32)
xs.windows(2).length => 3
xs.windows(3).length => 2
xs.windows(9).length => 0

sort_by

def sort_by(self, less: (T, T) -> bool) -> List<T>

A new list with the same elements ordered by less, a strict-before predicate, true when its first argument should sort ahead of its second. A top-down merge sort: O(n log n) calls to less, stable (elements less ranks equal keep their input order), source unchanged (persistent). The bound-free counterpart to sort, for ordering by a projected key or a custom order without a T: Ord impl.

xs: List<i32> = List.empty().append(1i32).append(3i32).append(2i32)
ys = xs.sort_by(|a, b| a > b)
ys.get(0) => Some(3i32)
ys.get(2) => Some(1i32)

mergeby

def _merge_by(self, other: List<T>, less: (T, T) -> bool) -> List<T>

Merge two less-sorted lists. On a tie (neither side less-precedes the other) the self (left) element wins, keeping a full sort_by stable. The exhausted side's remainder attaches via O(log n) concat (one of the two tails is empty).

impl<T: Eq> List<T>

contains? needs T: Eq; like sort's Ord block below, the bound gets its own inherent block, which leaves the rest of List unbounded.

contains?

def contains?(self, x: T) -> bool

True where some element equals x under Eq<T>: any? with an equality test. Short-circuits on the first match; false for the empty list.

xs: List<i32> = List.empty().append(1i32).append(2i32)
xs.contains?(2i32) => true
xs.contains?(9i32) => false

dedup

def dedup(self) -> List<T>

Consecutive runs of equal elements collapsed to one: [1, 1, 2, 3, 3, 1] becomes [1, 2, 3, 1]; non-adjacent duplicates are kept. Compares under Eq<T> (§10), like contains?. O(n).

xs: List<i32> = List.empty().append(1i32).append(1i32).append(2i32).append(3i32).append(3i32)
xs.dedup().length => 3
xs.dedup().get(0)   => Some(1i32)
xs.dedup().get(2)   => Some(3i32)

unique

def unique(self) -> List<T>

Every element with all later duplicates removed, keeping the first occurrence of each in order: [1, 2, 1, 3, 2] becomes [1, 2, 3]. Compares under Eq<T> (§10), like contains?. Unlike dedup (which only collapses consecutive runs) this drops non-adjacent duplicates too, at O(n²): each element is checked against those already taken; for a large input a Set is the O(n) alternative.

xs: List<i32> = List.empty().append(1i32).append(2i32).append(1i32).append(3i32).append(2i32)
xs.unique().length => 3
xs.unique().get(0)   => Some(1i32)
xs.unique().get(2)   => Some(3i32)

index_of

def index_of(self, x: T) -> Option<int>

The index of the first element equal to x under Eq<T>, or None when no element matches. The positional counterpart to contains?: a position with an equality test.

xs: List<i32> = List.empty().append(5i32).append(7i32).append(7i32)
xs.index_of(7i32) => Some(1)
xs.index_of(9i32) => None

impl<T: Ord> List<T>

sort needs T: Ord and the rest of List does not, and it therefore sits in its own bounded inherent block (mixing bounded + unbounded inherent impls on one type is not allowed). A free function would also work, but xs.sort() is the method spelling the surface wants.

min

def min(self) -> Option<T>

The minimum element by Ord, or None for the empty list; on a tie the earliest wins. The bound counterpart to min_by.

xs: List<i32> = List.empty().append(3i32).append(1i32).append(2i32)
xs.min() => Some(1i32)

max

def max(self) -> Option<T>

The maximum element by Ord, or None for the empty list; on a tie the earliest wins. The bound counterpart to max_by.

xs: List<i32> = List.empty().append(3i32).append(1i32).append(2i32)
xs.max() => Some(3i32)

sort

def sort(self) -> List<T>

A new list with the same elements in non-decreasing Ord<T> order, by a top-down merge sort, O(n log n) comparisons. Stable: equal elements keep their input order. The source list is unchanged (persistent).

xs: List<i32> = List.empty().append(3i32).append(1i32).append(2i32)
ys = xs.sort()
ys.get(0) => Some(1i32)
ys.get(2) => Some(3i32)

_merge

def _merge(self, other: List<T>) -> List<T>

Merge two Ord-sorted lists into one sorted list. On a tie the element from self, the left half, whose elements came first, wins, and a full sort therefore remains stable. The exhausted side's remainder attaches through O(log n) concat (one of the two tails is empty).

impl<T: Numeric> List<T>

sum

def sum(self) -> T

The sum of the elements, a fold from T.zero() through add, and the empty list sums to zero. Each step is the element type's native +: fixed widths wrap like the operator, and the lowercase tier's in-band inf/undefined sentinels propagate unchanged.

xs: List<int> = List.empty().append(1).append(2).append(3)
xs.sum() => 6
empty: List<int> = List.empty()
empty.sum() => 0

product

def product(self) -> T

The product of the elements, a fold from T.one() through mul, so the empty list multiplies to one.

xs: List<int> = List.empty().append(2).append(3).append(4)
xs.product() => 24
empty: List<int> = List.empty()
empty.product() => 1

impl<T: Display> Display<List<T>>

to_string

def to_string(self) -> string

[e1, e2, e3]: each element through its own Display, comma-separated; the empty list is []. Written by hand because List is an opaque intrinsic with no variants, and auto-derived Display therefore has nothing to match and traps at runtime.

xs: List<i32> = List.empty().append(1i32).append(2i32).append(3i32)
xs.to_string() => "[1, 2, 3]"