Skip to content

std::lists

A List<T> is an ordered, immutable sequence of values of one type, written [1, 2, 3]. [0, ..xs] is xs with 0 in front: it takes constant time and shares xs. A List keeps its length, so List.length does not walk it.

Import with import std::lists.

This module holds the functions that depend on how a List is built: length, first, tail, concat, remove_at, remove, starts_with, ends_with, split_while and contains. Transforming, filtering, sorting, folding and reading by index are functions of Iter, which work on a List as on every other collection. Iter.map, Iter.filter and the other adapters are lazy: they do no work until something reads the result. End a pipeline with Iter.to_list() to get a List back.

names = ["cy", "ann", "bo"]

Iter.count(names) // 3

Iter.get(names, 1) // Some("ann")

Iter.sort(names) // ["ann", "bo", "cy"]

Iter.contains(names, "bo") // True

names
|> Iter.map(String.uppercase)
|> Iter.to_list() // ["CY", "ANN", "BO"]

The Iter functions used most with a List:

  • Reading: Iter.first, Iter.last, Iter.get, Iter.count, Iter.is_empty, Iter.find, Iter.contains.
  • Transforming (lazy): Iter.map, Iter.filter, Iter.flat_map, Iter.take, Iter.drop, Iter.zip, Iter.with_index, Iter.chunks.
  • Folding: Iter.reduce, Iter.sum, Iter.min, Iter.max, Iter.any_match, Iter.all_match.
  • Rebuilding: Iter.sort, Iter.sort_by, Iter.reverse, Iter.partition, Iter.group_by, Iter.frequencies.
type List<T>

Ordered, immutable sequence of elements.

names = ["Alice", "Bob"]
names = ["Carol", ..names]
assert names == ["Carol", "Alice", "Bob"]

// Iter.filter and Iter.map are lazy; Iter.sum reads the result.
total =
    [1, 2, 3, 4, 5]
    |> Iter.filter(fn x -> x > 2)
    |> Iter.map(fn x -> x * 2)
    |> Iter.sum()

assert total == 24

// Iter.to_list collects the result into a List.
doubled =
    [1, 2, 3, 4, 5]
    |> Iter.filter(fn x -> x > 2)
    |> Iter.map(fn x -> x * 2)
    |> Iter.to_list()

assert doubled == [6, 8, 10]
fn next_item<T>(list: List<T>) -> Maybe<(T, List<T>)>

type function on List

Returns the first element and the rest of the list, or None if the list is empty.

assert List.next_item([1, 2, 3]) == Some((1, [2, 3]))
assert List.next_item([]) == None
fn length<T>(list: List<T>) -> NonNegativeInt

type function on List

Returns the number of elements. O(1): a List keeps its length. Iter.count gives the same for any iterable.

assert List.length(["a", "b"]) == 2
assert List.length([]) == 0
fn concat<T>(a: List<T>, b: List<T>) -> List<T>

type function on List

Concatenates two lists, yielding all elements of a followed by all of b.

assert List.concat([1, 2], [3, 4]) == [1, 2, 3, 4]
fn first<T>(list: List<T>) -> Maybe<T>

type function on List

Returns the first element, or None if the list is empty. Iter.first gives the same for any iterable, and NonEmptyList.first returns the element itself.

assert List.first([1, 2, 3]) == Some(1)
assert List.first([]) == None
fn tail<T>(list: List<T>) -> Maybe<List<T>>

type function on List

Returns all elements except the first, or None if the list is empty.

assert List.tail([1, 2, 3]) == Some([2, 3])
assert List.tail([]) == None
fn remove_at<T>(list: List<T>, index: Int) -> Maybe<List<T>>

type function on List

Some of the list without the element at zero-based index, or None when the index is outside the list. O(n): the elements before index are copied, and the ones after it are shared. For an index the code knows is in range, List.remove_at(list, index)! returns the list and traps on any other index.

assert List.remove_at(["a", "b", "c"], 1) == Some(["a", "c"])
assert List.remove_at(["a", "b", "c"], 0)! == ["b", "c"]
assert List.remove_at(["a", "b", "c"], 3) == None
fn remove<T>(list: List<T>, value: T) -> List<T> where T: Equatable

type function on List

The list without the first element == to value, or the same list when no element is. O(n).

assert List.remove([1, 2, 3, 2], 2) == [1, 3, 2]
assert List.remove([1, 2, 3], 9) == [1, 2, 3]
fn starts_with<T>(list: List<T>, prefix: List<T>) -> Bool where T: Equatable

type function on List

True if list begins with the elements of prefix, in order, each == to its counterpart. Every list starts with []. The list form of String.starts_with.

assert List.starts_with([1, 2, 3], [1, 2])
refute List.starts_with([1, 2, 3], [2, 3])
assert List.starts_with([1, 2], [])
refute List.starts_with([1], [1, 2])
fn ends_with<T>(list: List<T>, suffix: List<T>) -> Bool where T: Equatable

type function on List

True if list ends with the elements of suffix, in order, each == to its counterpart. Every list ends with []. The list form of String.ends_with.

assert List.ends_with([1, 2, 3], [2, 3])
refute List.ends_with([1, 2, 3], [1, 2])
assert List.ends_with([1, 2], [])
refute List.ends_with([3], [2, 3])
fn split_while<T>(list: List<T>, pred: (T) -> Bool) -> (List<T>, List<T>)

type function on List

Splits list after its leading run of elements where pred is true: that run, and the rest from the first element where it is false. The rest is the list’s own tail, shared, not copied; the run is a new list. Iter.take_while and Iter.drop_while give the two halves lazily, for any iterable.

assert List.split_while([1, 2, 3, 1], &(&1 < 3)) == ([1, 2], [3, 1])
assert List.split_while([5, 6], &(&1 < 3)) == ([], [5, 6])
assert List.split_while([1, 2], &(&1 < 3)) == ([1, 2], [])

impl Iter for List<T>

fn each_while(list: List<T>, yield: (T) -> Bool) -> Bool

impl Iter.each_while

impl Iter for List<T>

fn known_count(list: List<T>) -> Maybe<Int>

impl Iter.known_count

impl Contains for List<T>

fn contains(c: List<T>, x: T) -> Bool

impl Contains.contains

True if an element of the list is == to x. A linear scan that the runtime runs, comparing each element as == does; convert to a Set for repeated lookups.

assert List.contains([1, 2, 3], 2)
refute List.contains([1, 2, 3], 9)
refute List.contains([], 1)

impl Add<List<T>, List<T>> for List<T>

fn add(lhs: List<T>, rhs: List<T>) -> List<T>

impl Add.add

impl Summable for List<T>

fn empty_sum() -> List<T>

impl Summable.empty_sum

The sum of no Lists: []. Summing Lists concatenates them in order.

none: List<Int> = List.empty_sum()
assert none == []
assert [1, 2] + List.empty_sum() == [1, 2]
assert Iter.sum([[1], [2, 3], []]) == [1, 2, 3]

impl Display for List<T>

fn to_string(value: List<T>) -> String

impl Display.to_string

impl Debug for List<T>

fn inspect(value: List<T>) -> String

impl Debug.inspect

impl Equatable for List<T>

fn equal(a: List<T>, b: List<T>) -> Bool

impl Equatable.equal

impl Hashable for List<T>

fn hash(list: List<T>) -> Int

impl Hashable.hash

impl Comparable for List<T>

fn compare(a: List<T>, b: List<T>) -> Ordering

impl Comparable.compare

subtype NonEmptyList<T> List<T> when fn list -> not Iter.is_empty(list)

A List with at least one element, so its first, last, largest and smallest elements are plain values, not Maybes. A literal is checked when the program is compiled, so [] where a NonEmptyList is expected is an error before the program runs; NonEmptyList.try_from(xs) checks a List computed at run time, and NonEmptyList.of(first, rest) builds one that cannot fail. A NonEmptyList is a List and passes wherever one is expected; a NonEmptyList passes as a NonEmptyList when Circle implements Shape. It is in the prelude.

subtype: NonEmptyList is a subtype of List<T>. A literal where a NonEmptyList is expected is checked when the program is compiled; NonEmptyList.try_from(...) checks a value when it runs.

scores: NonEmptyList<Int> = [70, 95, 82]
assert NonEmptyList.first(scores) == 70
assert NonEmptyList.max(scores) == 95
assert List.length(scores) == 3

none: List<Int> = []
assert NonEmptyList.try_from(none) == None
assert NonEmptyList.try_from([1]) == Some([1])
fn of<T>(first: T, rest: List<T>) -> NonEmptyList<T>

type function on NonEmptyList

A NonEmptyList of first followed by the elements of rest, which may be empty.

assert NonEmptyList.of(1, [2, 3]) == [1, 2, 3]
assert NonEmptyList.of("a", []) == ["a"]
fn first<T>(list: NonEmptyList<T>) -> T

type function on NonEmptyList

The first element.

assert NonEmptyList.first([4, 5]) == 4
fn last<T>(list: NonEmptyList<T>) -> T

type function on NonEmptyList

The last element.

assert NonEmptyList.last([4, 5]) == 5
fn tail<T>(list: NonEmptyList<T>) -> List<T>

type function on NonEmptyList

The elements after the first, a List that may be empty.

assert NonEmptyList.tail([4, 5, 6]) == [5, 6]
assert NonEmptyList.tail([4]) == []
fn length<T>(list: NonEmptyList<T>) -> PositiveInt

type function on NonEmptyList

The number of elements, at least one.

assert NonEmptyList.length(["a", "b"]) == 2
fn max<T>(list: NonEmptyList<T>) -> T where T: Comparable

type function on NonEmptyList

The largest element; the first of several equal ones.

assert NonEmptyList.max([3, 9, 4]) == 9
fn min<T>(list: NonEmptyList<T>) -> T where T: Comparable

type function on NonEmptyList

The smallest element; the first of several equal ones.

assert NonEmptyList.min([3, 9, 4]) == 3
fn max_by<T, K>(list: NonEmptyList<T>, key: (T) -> K) -> T where K: Comparable

type function on NonEmptyList

The element whose key is largest.

assert NonEmptyList.max_by(["bb", "a", "ccc"], String.length) == "ccc"
fn min_by<T, K>(list: NonEmptyList<T>, key: (T) -> K) -> T where K: Comparable

type function on NonEmptyList

The element whose key is smallest.

assert NonEmptyList.min_by(["bb", "a", "ccc"], String.length) == "a"
fn mean<T, R>(list: NonEmptyList<T>) -> R where T: Averageable<R>

type function on NonEmptyList

The arithmetic mean of the elements, rounded as Iter.mean rounds; a value, since there is at least one.

assert NonEmptyList.mean([1, 2]) == 1.5
assert NonEmptyList.mean([1.50d, 2.25d]) == 1.875d
fn reduce<T>(list: NonEmptyList<T>, f: (T, T) -> T) -> T

type function on NonEmptyList

Combines the elements left to right with f, starting from the first, so it needs no starting value: [a, b, c] is f(f(a, b), c).

assert NonEmptyList.reduce([1, 2, 3], fn acc, n -> acc + n) == 6
assert NonEmptyList.reduce(["x"], fn acc, s -> acc + s) == "x"
fn map<T, U>(list: NonEmptyList<T>, f: (T) -> U) -> NonEmptyList<U>

type function on NonEmptyList

Applies f to each element; the result has as many elements.

assert NonEmptyList.map([1, 2], fn n -> n * 10) == [10, 20]
fn with_index<T>(list: NonEmptyList<T>) -> NonEmptyList<(NonNegativeInt, T)>

type function on NonEmptyList

Each element with its index, from 0.

assert NonEmptyList.with_index(["a", "b"]) == [(0, "a"), (1, "b")]
fn reverse<T>(list: NonEmptyList<T>) -> NonEmptyList<T>

type function on NonEmptyList

The elements in reverse order.

assert NonEmptyList.reverse([1, 2, 3]) == [3, 2, 1]
fn sort<T>(list: NonEmptyList<T>) -> NonEmptyList<T> where T: Comparable

type function on NonEmptyList

The elements in ascending order; the sort is stable.

assert NonEmptyList.sort([3, 1, 2]) == [1, 2, 3]
fn prepend<T>(list: List<T>, item: T) -> NonEmptyList<T>

type function on NonEmptyList

item before the elements of list, which may be empty. O(1).

assert NonEmptyList.prepend([2, 3], 1) == [1, 2, 3]
assert NonEmptyList.prepend([], 1) == [1]
fn push<T>(list: List<T>, item: T) -> NonEmptyList<T>

type function on NonEmptyList

The elements of list, which may be empty, then item. O(n).

assert NonEmptyList.push([1, 2], 3) == [1, 2, 3]
assert NonEmptyList.push([], 3) == [3]
fn concat<T>(a: NonEmptyList<T>, b: List<T>) -> NonEmptyList<T>

type function on NonEmptyList

The elements of a, then those of b, which may be empty.

assert NonEmptyList.concat([1], [2, 3]) == [1, 2, 3]
assert NonEmptyList.concat([1], []) == [1]
fn try_from<T>(value: List<T>) -> Maybe<NonEmptyList<T>>

type function on NonEmptyList

Some of the value when it satisfies NonEmptyList’s rules, None when it does not.