std/list
Functions for List(A), the built-in type of lists that may not be
changed.
Every function that walks a whole list is tail-recursive (§11.6), so it works on lists of any length without using more stack. Functions that build a new list build it in reverse and then turn it round, which takes one more pass.
Functions that may find nothing give an Option (first, find,
at, …). Functions that take a function as an argument have the errors
and the environment of that function (^ E ! N), so the argument may
itself raise errors or need services.
ContinueOrStop
What fold_until does next: go on with the new accumulator, or stop
with it.
ContinueOrStop(A) = Continue(A) | Stop(A) length
The number of elements. It walks the whole list.
list.length([1, 2, 3]) // 3 length = <A>(of : List(A)) -> Int { count
The number of elements for which the function gives True.
count = <A, N>(list : List(A), where : (A) <- N -> Bool) -> Int { reverse
The elements in the other order.
list.reverse([1, 2, 3]) // [3, 2, 1] reverse = <A>(list : List(A)) -> List(A) { reverse_onto(list, []) } is_empty
True for the empty list. It takes one step.
is_empty = <A>(list : List(A)) -> Bool { list == [] } contains
True when an element is == to any.
list.contains([1, 2], 2) // True contains = <A>(list : List(A), any : A) -> Bool { first
The first element, or None for the empty list.
first = <A>(list : List(A)) -> Option(A) { rest
The list without its first element, or None for the empty list.
rest = <A>(list : List(A)) -> Option(List(A)) { last
The last element, or None for the empty list.
last = <A>(list : List(A)) -> Option(A) { at
The element at an index, counting from 0, or None when the index is
not in the list.
list.at([10, 20, 30], 1) // Some(20) at = <A>(list : List(A), index : Int) -> Option(A) { index_of
The index of the first element that is == to item, counting from
0, or None.
index_of = <A>(list : List(A), item : A) -> Option(Int) { group
Puts the elements into groups by a key function, in a dict. Each group keeps the elements in the order of the list.
list.group([1, 2, 3, 4], (x) { x % 2 }) // {1 -> [1, 3], 0 -> [2, 4]} group = <V, K, N>(list : List(V), by : (V) <- N -> K) -> Dict(K, List(V)) { filter
Keeps the elements for which the function gives True, in order.
list.filter([1, 2, 3, 4], int.is_even) // [2, 4] filter = <A, N>(list : List(A), keeping : (A) <- N -> Bool) -> List(A) { filter_map
Calls a function on every element, and keeps the values of the Some
results.
list.filter_map(["1", "x", "3"], (s) { option.from_result(int.parse(s)) }) // [1, 3] filter_map = <A, B, N>(list : List(A), with : (A) <- N -> Option(B)) -> List( map
Calls a function on every element, and gives the list of the results.
list.map([1, 2, 3], (x) { x * 2 }) // [2, 4, 6] map = <A, B, N>(list : List(A), with : (A) <- N -> B) -> List(B) { map2
Calls a function on the elements of two lists at the same places. When one list is longer, its other elements are not used.
list.map2([1, 2, 3], [4, 5], (x, y) { x + y }) // [5, 7] map2 = <A, B, C, N>( map_fold
Maps the elements with an accumulator that goes from each element to the next. Gives the last accumulator and the new list.
list.map_fold([1, 2, 3], 100, (acc, x) { (acc + x, x * 2) })
// (106, [2, 4, 6]) map_fold = <A, Acc, B, N>( index_map
Like map, and the function also gets the index of the element,
counting from 0.
index_map = <A, B, N>(list : List(A), with : (A, Int) <- N -> B) -> List(B) { try_map
Calls a function that gives a result on every element. Gives Ok with
all the values, or the first Error; after an Error, the function is
not called again.
list.try_map(["1", "2"], int.parse) // Ok([1, 2]) try_map = <A, B, F, N>( drop
The list without its first up_to elements. When the list is shorter,
the empty list.
list.drop([1, 2, 3, 4], 2) // [3, 4] drop = <A>(from : List(A), up_to : Int) -> List(A) { take
The first up_to elements. When the list is shorter, the whole list.
list.take([1, 2, 3, 4], 2) // [1, 2] take = <A>(from : List(A), up_to : Int) -> List(A) { new
The empty list.
new = <A>() -> List(A) { [] } wrap
A list of one element.
wrap = <A>(item : A) -> List(A) { [item] } append
The elements of first, then the elements of second.
list.append([1, 2], [3]) // [1, 2, 3] append = <A>(first : List(A), second : List(A)) -> List(A) { prepend
Puts an element in front of a list.
prepend = <A>(to : List(A), this : A) -> List(A) { [this, ..to] } concat
The elements of all the lists, one list after the other.
list.concat([[1], [2, 3], []]) // [1, 2, 3] concat = <A>(lists : List(List(A))) -> List(A) { flat_map
Maps every element to a list, and puts these lists together.
list.flat_map([1, 2], (x) { [x, x] }) // [1, 1, 2, 2] flat_map = <A, B, N>(over : List(A), with : (A) <- N -> List(B)) -> List(B) { fold
Combines the elements with an accumulator, from the first to the last.
list.fold([1, 2, 3], 0, (acc, x) { acc + x }) // 6 fold = <A, Acc, N>( fold_right
Combines the elements with an accumulator, from the last to the first.
list.fold_right([1, 2, 3], [], (acc, x) { [x, ..acc] }) // [1, 2, 3] fold_right = <A, Acc, N>( index_fold
Like fold, and the function also gets the index of the element.
index_fold = <A, Acc, N>( try_fold
Like fold, but the function gives a result. The fold stops at the
first Error.
list.try_fold([1, 2, 3], 0, (acc, x) { Ok(acc + x) }) // Ok(6) try_fold = <A, Acc, F, N>( fold_until
Like fold, but the function says whether to go on (Continue) or to
stop (Stop).
list.fold_until([1, 2, 3, 4], 0, (acc, x) {
{ x < 3 } |> (True) { list.Continue(acc + x) } | (False) { list.Stop(acc) }
}) // 3 fold_until = <A, Acc, N>( find
The first element for which the function gives True, or None.
list.find([1, 2, 3], (x) { x > 1 }) // Some(2) find = <A, N>(in : List(A), one_that : (A) <- N -> Bool) -> Option(A) { find_map
The first Some value that the function gives, or None.
find_map = <A, B, N>(in : List(A), with : (A) <- N -> Option(B)) -> Option(B) { all
True when the function gives True for every element. It stops at the
first False. True for the empty list.
all = <A, N>(in : List(A), satisfying : (A) <- N -> Bool) -> Bool { any
True when the function gives True for some element. It stops at the
first True. False for the empty list.
any = <A, N>(in : List(A), satisfying : (A) <- N -> Bool) -> Bool { zip
Pairs of the elements of two lists at the same places. When one list is longer, its other elements are not used.
list.zip([1, 2, 3], ["a", "b"]) // [(1, "a"), (2, "b")] zip = <A, B>(list : List(A), with : List(B)) -> List((A, B)) { strict_zip
Like zip, but Error(Nil) when the lists have different lengths.
strict_zip = <A, B>(list : List(A), with : List(B)) -> Result( unzip
Takes a list of pairs apart into two lists.
list.unzip([(1, "a"), (2, "b")]) // ([1, 2], ["a", "b"]) unzip = <A, B>(input : List((A, B))) -> (List(A), List(B)) { intersperse
Puts with between every two elements.
list.intersperse([1, 2, 3], 0) // [1, 0, 2, 0, 3] intersperse = <A>(list : List(A), with : A) -> List(A) { unique
The list without the elements that are == to an earlier element. The
first of each is kept, in order. It takes O(n log n) steps, with a dict.
list.unique([1, 2, 1, 3, 2]) // [1, 2, 3] unique = <A>(list : List(A)) -> List(A) { sort
Sorts the elements with a compare function. The sort is stable: equal elements keep their order. It is a merge sort, which takes O(n log n) steps, and which starts from the runs that are already in order.
list.sort([3, 1, 2], int.compare) // [1, 2, 3] sort = <A, N>(list : List(A), by : (A, A) <- N -> Order) -> List(A) { range
The numbers from from to to, with both ends. It counts down when
to is less than from.
list.range(1, 4) // [1, 2, 3, 4]
list.range(2, 0) // [2, 1, 0] range = (from : Int, to : Int) -> List(Int) { repeat
A list of times copies of item.
list.repeat("a", 3) // ["a", "a", "a"] repeat = <A>(item : A, times : Int) -> List(A) { split
The first at elements, and the rest.
list.split([1, 2, 3, 4], 1) // ([1], [2, 3, 4]) split = <A>(list : List(A), at : Int) -> (List(A), List(A)) { split_while
The first elements for which the function gives True, and the rest.
split_while = <A, N>(list : List(A), satisfying : (A) <- N -> Bool) -> ( key_find
The value of the first pair whose key is == to find, in a list of
pairs, or None.
list.key_find([("a", 1), ("b", 2)], "b") // Some(2) key_find = <K, V>(in : List((K, V)), find : K) -> Option(V) { key_filter
The values of all the pairs whose key is == to find, in order.
key_filter = <K, V>(in : List((K, V)), find : K) -> List(V) { key_pop
The value of the first pair whose key is == to key, and the list
without that pair, or None.
list.key_pop([("a", 1), ("b", 2)], "a") // Some((1, [("b", 2)])) key_pop = <K, V>(list : List((K, V)), key : K) -> Option((V, List((K, V)))) { key_set
Sets the value of the first pair whose key is == to key, or adds the
pair at the end when there is none.
key_set = <K, V>(list : List((K, V)), key : K, value : V) -> List((K, V)) { each
Calls a function on every element, in order, for its effects.
each = <A, B, N>(list : List(A), with : (A) <- N -> B) -> Nil { try_each
Calls a function that gives a result on every element, in order, and
stops at the first Error.
try_each = <A, B, F, N>( partition
The elements for which the function gives True, and the others, each
in order.
list.partition([1, 2, 3, 4], int.is_odd) // ([1, 3], [2, 4]) partition = <A, N>(list : List(A), with : (A) <- N -> Bool) -> ( permutations
Every order of the elements. Elements are told apart by their place, so equal elements give equal permutations more than once. The number of permutations is n!, so this is only for short lists.
list.permutations([1, 2, 3])
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] permutations = <A>(list : List(A)) -> List(List(A)) { window
Every run of by elements that come one after the other, in order.
list.window([1, 2, 3, 4], 2) // [[1, 2], [2, 3], [3, 4]] window = <A>(list : List(A), by : Int) -> List(List(A)) { window_by_2
Every pair of elements that come one after the other.
list.window_by_2([1, 2, 3]) // [(1, 2), (2, 3)] window_by_2 = <A>(list : List(A)) -> List((A, A)) { drop_while
The list without its first elements for which the function gives
True.
drop_while = <A, N>(in : List(A), satisfying : (A) <- N -> Bool) -> List(A) { take_while
The first elements for which the function gives True.
take_while = <A, N>(in : List(A), satisfying : (A) <- N -> Bool) -> List(A) { chunk
Cuts the list into runs of elements, one after the other, for which the function gives the same key.
list.chunk([1, 2, 2, 3, 4, 4, 6], (x) { x % 2 })
// [[1], [2, 2], [3], [4, 4, 6]] chunk = <A, K, N>(in : List(A), by : (A) <- N -> K) -> List(List(A)) { sized_chunk
Cuts the list into lists of into elements. The last list may be
shorter. When into is 0 or less, the empty list.
list.sized_chunk([1, 2, 3, 4, 5], 2) // [[1, 2], [3, 4], [5]] sized_chunk = <A>(in : List(A), into : Int) -> List(List(A)) { reduce
Combines the elements with a function, from the first to the last, with
the first element as the start. None for the empty list.
list.reduce([1, 2, 3], (a, b) { a + b }) // Some(6) reduce = <A, N>(over : List(A), with : (A, A) <- N -> A) -> Option(A) { scan
Like fold, but gives every accumulator after each element.
list.scan([1, 2, 3], 0, (acc, x) { acc + x }) // [1, 3, 6] scan = <A, Acc, N>( combinations
Every way to choose by elements, keeping their order.
list.combinations([1, 2, 3], 2) // [[1, 2], [1, 3], [2, 3]] combinations = <A>(items : List(A), by : Int) -> List(List(A)) { combination_pairs
Every pair of two elements, keeping their order.
list.combination_pairs([1, 2, 3]) // [(1, 2), (1, 3), (2, 3)] combination_pairs = <A>(items : List(A)) -> List((A, A)) { interleave
The first elements of all the lists, then the second elements, and so on.
list.interleave([[1, 2], [101, 102], [201]]) // [1, 101, 201, 2, 102] interleave = <A>(list : List(List(A))) -> List(A) { concat(transpose(list)) } transpose
Turns rows into columns. Shorter lists leave gaps, which are taken out.
list.transpose([[1, 2, 3], [101, 102, 103]]) // [[1, 101], [2, 102], [3, 103]] transpose = <A>(list_of_lists : List(List(A))) -> List(List(A)) { max
The greatest element by a compare function, or None for the empty
list. Of equal greatest elements, the first is given.
max = <A, N>(over : List(A), with : (A, A) <- N -> Order) -> Option(A) { min
The smallest element by a compare function, or None for the empty
list. Of equal smallest elements, the first is given.
min = <A, N>(over : List(A), with : (A, A) <- N -> Order) -> Option(A) {