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.
Exports
Section titled “Exports”Types
List and Iter
Section titled “List and Iter”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
Section titled “type List”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]
List.next_item
Section titled “List.next_item”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
List.length
Section titled “List.length”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
List.concat
Section titled “List.concat”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]
List.first
Section titled “List.first”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
List.tail
Section titled “List.tail”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
List.remove_at
Section titled “List.remove_at”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
List.remove
Section titled “List.remove”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]
List.starts_with
Section titled “List.starts_with”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])
List.ends_with
Section titled “List.ends_with”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])
List.split_while
Section titled “List.split_while”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], [])
List.each_while
Section titled “List.each_while”impl Iter for List<T>
fn each_while(list: List<T>, yield: (T) -> Bool) -> Bool
impl Iter.each_while
List.known_count
Section titled “List.known_count”impl Iter for List<T>
fn known_count(list: List<T>) -> Maybe<Int>
impl Iter.known_count
List.contains
Section titled “List.contains”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)
List.add
Section titled “List.add”impl Add<List<T>, List<T>> for List<T>
fn add(lhs: List<T>, rhs: List<T>) -> List<T>
impl Add.add
List.empty_sum
Section titled “List.empty_sum”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]
List.to_string
Section titled “List.to_string”impl Display for List<T>
fn to_string(value: List<T>) -> String
impl Display.to_string
List.inspect
Section titled “List.inspect”impl Debug for List<T>
fn inspect(value: List<T>) -> String
impl Debug.inspect
List.equal
Section titled “List.equal”impl Equatable for List<T>
fn equal(a: List<T>, b: List<T>) -> Bool
impl Equatable.equal
List.hash
Section titled “List.hash”impl Hashable for List<T>
fn hash(list: List<T>) -> Int
impl Hashable.hash
List.compare
Section titled “List.compare”impl Comparable for List<T>
fn compare(a: List<T>, b: List<T>) -> Ordering
impl Comparable.compare
type NonEmptyList
Section titled “type NonEmptyList”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
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])
NonEmptyList.of
Section titled “NonEmptyList.of”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"]
NonEmptyList.first
Section titled “NonEmptyList.first”fn first<T>(list: NonEmptyList<T>) -> T
type function on NonEmptyList
The first element.
assert NonEmptyList.first([4, 5]) == 4
NonEmptyList.last
Section titled “NonEmptyList.last”fn last<T>(list: NonEmptyList<T>) -> T
type function on NonEmptyList
The last element.
assert NonEmptyList.last([4, 5]) == 5
NonEmptyList.tail
Section titled “NonEmptyList.tail”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]) == []
NonEmptyList.length
Section titled “NonEmptyList.length”fn length<T>(list: NonEmptyList<T>) -> PositiveInt
type function on NonEmptyList
The number of elements, at least one.
assert NonEmptyList.length(["a", "b"]) == 2
NonEmptyList.max
Section titled “NonEmptyList.max”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
NonEmptyList.min
Section titled “NonEmptyList.min”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
NonEmptyList.max_by
Section titled “NonEmptyList.max_by”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"
NonEmptyList.min_by
Section titled “NonEmptyList.min_by”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"
NonEmptyList.mean
Section titled “NonEmptyList.mean”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
NonEmptyList.reduce
Section titled “NonEmptyList.reduce”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"
NonEmptyList.map
Section titled “NonEmptyList.map”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]
NonEmptyList.with_index
Section titled “NonEmptyList.with_index”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")]
NonEmptyList.reverse
Section titled “NonEmptyList.reverse”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]
NonEmptyList.sort
Section titled “NonEmptyList.sort”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]
NonEmptyList.prepend
Section titled “NonEmptyList.prepend”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]
NonEmptyList.push
Section titled “NonEmptyList.push”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]
NonEmptyList.concat
Section titled “NonEmptyList.concat”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]
NonEmptyList.try_from
Section titled “NonEmptyList.try_from”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.