List

List module: immutable singly-linked list operations.

List(a) = Cons(a, List(a)) Nil (built-in constructors)

Design:

Partial functions (head, tail, nth, last) panic on empty/out-of-bounds
Safe variants use the _opt suffix and return Option
fold_left is the primitive; fold_right recurses on the structure
sort uses merge sort

Functions

fnallall(xs : List(a), pred : a -> Bool) : Bool#

Returns true if all elements satisfy pred (vacuously true for []). Stops at the first element that fails.

Examples

march> List.all([2, 4], fn x -> x % 2 == 0)
true
march> List.all([2, 3], fn x -> x % 2 == 0)
false
march> List.all([], fn x -> x > 100)
true

fnanyany(xs : List(a), pred : a -> Bool) : Bool#

Returns true if any element satisfies pred (false for []). Stops at the first match.

Examples

march> List.any([1, 2, 3], fn x -> x > 2)
true
march> List.any([], fn x -> x > 2)
false

fnappendappend(xs : List(a), ys : List(a)) : {List(a) | elts(_) == union(elts(xs), elts(ys))}#

Concatenates two lists.

Examples

march> List.append([1, 2], [3, 4, 5])
[1, 2, 3, 4, 5]
march> List.append([], [1, 2])
[1, 2]

fnchunkschunks(xs : List(a), size : {Int | _ > 0}) : List(List(a))#

Splits the list into consecutive chunks of size elements; the last chunk holds the remainder and may be shorter. Returns [] for an empty list. size must be positive ({Int | _ > 0}); panics otherwise.

Examples

march> List.chunks([1, 2, 3, 4, 5], 2)
[[1, 2], [3, 4], [5]]
march> List.chunks([1, 2], 5)
[[1, 2]]

fnconcatconcat(xss : List(List(a))) : List(a)#

Concatenates a list of lists into a single list, in order. O(total length).

Examples

march> List.concat([[1, 2], [], [3]])
[1, 2, 3]
march> List.concat([])
[]

fndedupdedup(xs : List(a)) : {List(a) | elts(_) == elts(xs)}#

Removes consecutive duplicate elements (keeps the first of each run). Uses structural equality. Only adjacent repeats are removed, so a value can appear again later; sort first to remove all duplicates.

Examples

march> List.dedup([1, 1, 2, 1, 1, 3])
[1, 2, 1, 3]
march> List.dedup([])
[]

fndropdrop(xs : List(a), n : Int) : List(a)#

Drops the first n elements. Returns [] if n >= length, and the whole list if n <= 0.

Examples

march> List.drop([1, 2, 3], 2)
[3]
march> List.drop([1, 2, 3], 10)
[]
march> List.drop([1, 2, 3], 0)
[1, 2, 3]

fndrop_lastdrop_last(xs : List(a)) : List(a)#

Returns all elements except the last. Returns [] for empty or singleton lists (no panic).

Examples

march> List.drop_last([1, 2, 3])
[1, 2]
march> List.drop_last([1])
[]
march> List.drop_last([])
[]

fndrop_whiledrop_while(xs : List(a), pred : a -> Bool) : List(a)#

Drops the longest prefix of elements satisfying pred, returning the rest (starting at the first element that fails). The complement of take_while.

Examples

march> List.drop_while([1, 2, 5, 1], fn x -> x < 3)
[5, 1]
march> List.drop_while([1, 2], fn x -> x < 3)
[]

fneacheach(xs : List(a), f : a -> b) : ()#

Applies f to each element, in order, for its side effects; f's results are discarded. Returns ().

Examples

march> List.each([1, 2, 3], fn x -> x * 2)
()

fnemptyempty() : List(a)#

Returns an empty list.

Examples

march> List.empty()
[]

fnenumerateenumerate(xs : List(a)) : List((Int, a))#

Pairs each element with its 0-based index: [a, b] -> [(0, a), (1, b)].

Examples

march> List.enumerate(["a", "b"])
[(0, "a"), (1, "b")]

fnfilterfilter(xs : List(a), pred : a -> Bool[p]) : {List(a[p]) | subset(elts(_), elts(xs))}#

Returns only elements satisfying pred.

The result's elements are known to satisfy the predicate: with sum_pos(xs : List({Int | _ > 0})), sum_pos(List.filter(ys, fn y -> y > 0)) is proved. p is an abstract refinement, instantiated from the lambda at each call.

Examples

march> List.filter([1, 2, 3, 4, 5], fn x -> x > 2)
[3, 4, 5]

march> List.filter(["foo", "", "bar", ""], fn s -> !String.is_empty(s))
["foo", "bar"]

fnfilter_mapfilter_map(xs : List(a), f : a -> Option(b)) : List(b)#

Applies f to each element; collects Some values, discards None. Equivalent to map followed by filter for non-None values, in one pass.

Examples

march> List.filter_map([1, 2, 3, 4], fn x -> if x % 2 == 0 do Some(x * 10) else None end)
[20, 40]
march> List.filter_map(["1", "x", "3"], fn s -> Result.to_option(String.to_int(s)))
[1, 3]

fnfindfind(xs : List(a), pred : a -> Bool[p]) : Option(a[p])#

Returns the first element satisfying pred, or None. Stops at the first match. The element, when present, is known to satisfy pred (an abstract refinement p, as for filter).

Examples

march> List.find([1, 5, 8, 9], fn x -> x > 4)
Some(5)
march> List.find([1, 2], fn x -> x > 4)
None

fnfind_indexfind_index(xs : List(a), pred : a -> Bool) : Option(Int)#

Returns the 0-based index of the first element satisfying pred, or None.

Examples

march> List.find_index(["a", "b", "c"], fn s -> s == "c")
Some(2)
march> List.find_index([], fn s -> s == "c")
None

fnflat_mapflat_map(xs : List(a), f : a -> List(b)) : List(b)#

Applies f to each element and concatenates the resulting lists, in order. O(n) in the total output size.

Examples

march> List.flat_map([1, 2, 3], fn x -> List.repeat(x, x))
[1, 2, 2, 3, 3, 3]
march> List.flat_map([1, 2], fn _ -> [])
[]

fnfold_leftfold_left(xs : List(a), acc : b, f : b -> a -> b) : b#

Left fold: reduces the list from left to right with an accumulator. Argument order follows the stdlib uncurried-collection convention: collection first, acc second, callback last.

Examples

march> List.fold_left([1, 2, 3, 4], 0, fn (acc, x) -> acc + x)
10

march> List.fold_left([1, 2, 3], [], fn (acc, x) -> Cons(x * 2, acc))
[6, 4, 2]

fnfold_rightfold_right(xs : List(a), acc : b, f : a -> b -> b) : b#

Right fold: reduces the list from right to left, so the last element is combined with acc first. The callback takes the element first and the accumulator second, f(x, acc) (the reverse of fold_left). Uses constant stack (it folds left over the reversed list).

Examples

march> List.fold_right([1, 2, 3], [], fn (x, acc) -> Cons(x * 2, acc))
[2, 4, 6]
march> List.fold_right(["a", "b", "c"], "", fn (x, acc) -> acc ++ x)
"cba"

fnheadhead(xs : {List(a) | len(_) > 0}) : a#

Returns the first element. Panics on an empty list; use head_opt when the list may be empty.

Examples

march> List.head([7, 8, 9])
7

fnhead_opthead_opt(xs : List(a)) : Option(a)#

Returns Some(first element), or None if the list is empty.

Examples

march> List.head_opt([7, 8])
Some(7)
march> List.head_opt([])
None

fnintersperseintersperse(xs : List(a), sep : a) : List(a)#

Inserts sep between every consecutive pair of elements. Lists with fewer than two elements are returned unchanged.

Examples

march> List.intersperse([1, 2, 3], 0)
[1, 0, 2, 0, 3]
march> List.intersperse([1], 0)
[1]

fnis_emptyis_empty(xs : List(a)) : Bool#

Returns true if the list has no elements. O(1), unlike length(xs) == 0.

Examples

march> List.is_empty([])
true
march> List.is_empty([0])
false

fnlastlast(xs : {List(a) | len(_) > 0}) : a#

Returns the last element, walking the whole list (O(n)). Panics on an empty list.

Examples

march> List.last([1, 2, 3])
3

fnlengthlength(xs : List(a)) : Int#

Returns the number of elements in the list.

Examples

march> List.length([1, 2, 3])
3
march> List.length([])
0

fnmapmap(xs : List(a), f : a -> b) : List(b)#

Applies f to each element, returning a new list.

Examples

march> List.map([1, 2, 3], fn x -> x * 2)
[2, 4, 6]

march> List.map(["a", "b"], String.to_uppercase)
["A", "B"]

fnmaximum_intmaximum_int(xs : {List(Int) | len(_) > 0}) : Int#

Returns the maximum integer in the list. Panics if empty.

Examples

march> List.maximum_int([3, -1, 2])
3

fnmembermember(xs : List(a), x : a) : Bool#

Returns true if xs contains x (using structural equality). O(n).

Examples

march> List.member([1, 2, 3], 2)
true
march> List.member([], 2)
false

fnminimum_intminimum_int(xs : {List(Int) | len(_) > 0}) : Int#

Returns the minimum integer in the list. Panics if empty.

Examples

march> List.minimum_int([3, -1, 2])
-1

fnnthnth(xs : List(a), n : {Int | _ >= 0 && _ < len(xs)}) : a#

Returns the nth element (0-indexed). Panics if out of bounds.

n carries the bounds contract {Int | _ >= 0 && _ < len(xs)}, so an index the compiler can prove out of range is a compile error rather than a runtime panic. An index it cannot bound is accepted in silence — March reports only definite failures — and the panic below remains the runtime backstop. Use nth_opt when the index is genuinely unknown. O(n).

Examples

march> List.nth([10, 20, 30], 0)
10
march> List.nth([10, 20, 30], 2)
30

fnnth_optnth_opt(xs : List(a), n : Int) : Option(a)#

Returns Some(nth element) (0-indexed), or None if n is out of bounds, including any negative n. O(n).

Examples

march> List.nth_opt([10, 20, 30], 1)
Some(20)
march> List.nth_opt([10, 20, 30], 3)
None
march> List.nth_opt([10, 20, 30], -1)
None

fnpartitionpartition(xs : List(a), pred : a -> Bool[p]) : (List(a[p]), List({a | !p(_)}))#

Splits into (elements satisfying pred, elements not satisfying pred), each keeping the original order. Every element of the first list satisfies pred and none of the second does: an abstract refinement p, as for filter, so let (pos, neg) = List.partition(ys, fn y -> y > 0) gives pos the element refinement y > 0 and neg the refinement !(y > 0).

Examples

march> List.partition([1, 2, 3, 4, 5], fn x -> x % 2 == 1)
([1, 3, 5], [2, 4])
march> List.partition([], fn x -> x > 0)
([], [])

fnpfilterpfilter(xs : List(a), pred : a -> Bool) : List(a)#

Parallel filter: keeps elements satisfying pred, in the same order as sequential filter. pred MUST be safe to run concurrently. Below pmap_threshold() elements it delegates to sequential filter; above it each threshold-sized chunk is filtered on its own task and the kept elements concatenated in order.

Examples

march> List.pfilter([1, 2, 3, 4], fn x -> x % 2 == 0)
[2, 4]

fnpmappmap(xs : List(a), f : a -> b) : List(b)#

Parallel map: applies f to every element, returning a new list in the same order as map. f MUST be safe to run concurrently (pure / no cross-element ordering dependency).

Below pmap_threshold() elements this delegates to sequential map (zero spawn overhead). Above it, the list is split into threshold-sized chunks, each mapped on its own task, and the results concatenated in order. In the interpreter tasks run eagerly (correct, sequential); in compiled code they run on the multi-core scheduler.

Examples

march> List.pmap([1, 2, 3], fn x -> x * 2)
[2, 4, 6]

fnpmap_npmap_n(xs : List(a), f : a -> b, max_concurrency : Int) : List(b)#

Like pmap, but caps the number of concurrent tasks at max_concurrency by splitting the input into at most that many contiguous chunks. Use this when each element is expensive (few elements, heavy work) so the threshold heuristic doesn't apply. No threshold check is performed.

max_concurrency is treated as at least 1. Result order matches map.

Examples

march> List.pmap_n([1, 2, 3, 4, 5], fn x -> x * x, 2)
[1, 4, 9, 16, 25]
march> List.pmap_n([], fn x -> x * x, 4)
[]

fnpreducepreduce(xs : List(a), identity : a, combine : a -> a -> a) : a#

Parallel reduction over an associative combine with identity as its unit.

Contract: combine MUST be associative — combine(combine(x, y), z) must equal combine(x, combine(y, z)) — and identity must be its unit. Sum, product, max, min, string concat, and set union qualify; subtraction and average DO NOT. The compiler cannot check this; correctness is the caller's responsibility.

Below pmap_threshold() elements this is sequential fold_left. Above it, each threshold-sized chunk is reduced on its own task and the partial results are combined in order — identical to the sequential result iff the contract holds.

Examples

march> List.preduce([1, 2, 3, 4], 0, fn (a, b) -> a + b)
10

fnproduct_intproduct_int(xs : List(Int)) : Int#

Multiplies all integers in a list. Returns 1 for [].

Examples

march> List.product_int([2, 3, 4])
24
march> List.product_int([])
1

fnrangerange(start : Int, stop : Int) : List(Int)#

Returns [start, start+1, ..., stop-1]. Returns [] if start >= stop.

Examples

march> List.range(0, 5)
[0, 1, 2, 3, 4]
march> List.range(3, 7)
[3, 4, 5, 6]
march> List.range(5, 5)
[]

fnrange_steprange_step(start : Int, stop : Int, step : {Int | _ != 0}) : List(Int)#

Returns [start, start+step, start+2*step, ...], stopping before stop. A positive step counts up while the value is < stop; a negative step counts down while it is > stop. Returns [] when start is already past stop in the direction of step. Panics if step is zero (also a refinement precondition), as Range.new_step does.

Examples

march> List.range_step(0, 10, 3)
[0, 3, 6, 9]
march> List.range_step(5, 0, -2)
[5, 3, 1]
march> List.range_step(0, 5, -1)
[]

fnrepeatrepeat(x : a, n : Int) : List(a)#

Returns a list with x repeated n times.

Examples

march> List.repeat(0, 3)
[0, 0, 0]
march> List.repeat("x", 4)
["x", "x", "x", "x"]

fnreversereverse(xs : List(a)) : {List(a) | elts(_) == elts(xs)}#

Returns the list in reverse order.

Examples

march> List.reverse([1, 2, 3])
[3, 2, 1]
march> List.reverse([])
[]

fnscan_leftscan_left(xs : List(a), acc : b, f : b -> a -> b) : List(b)#

Like fold_left but returns every accumulator value, starting with the initial acc, so the result has one more element than xs; its last element is what fold_left would return.

Examples

march> List.scan_left([1, 2, 3], 0, fn (acc, x) -> acc + x)
[0, 1, 3, 6]
march> List.scan_left([], 5, fn (acc, x) -> acc + x)
[5]

fnsingletonsingleton(x : a) : List(a)#

Returns a list containing a single element.

Examples

march> List.singleton(42)
[42]
march> List.singleton("hi")
["hi"]

fnsort_bysort_by(xs : List(a), cmp : a -> a -> Bool) : List(a)#

Sorts by a comparator function: cmp(a, b) returns true when a may come before b. Uses bottom-up merge sort, O(n log n).

Stable only with a non-strict comparator (<=): on a tie the merge takes the left element only when cmp(left, right) is true, so with a strict < equal elements can come out reordered.

Examples

march> List.sort_by([3, 1, 4, 1, 5], fn (a, b) -> a < b)
[1, 1, 3, 4, 5]

march> List.sort_by(["banana", "apple", "cherry"], fn (a, b) -> a < b)
["apple", "banana", "cherry"]

march> List.sort_by([3, 1, 2], fn (a, b) -> a >= b)
[3, 2, 1]

march> List.sort_by([(1, "a"), (0, "z"), (1, "b")], fn (p, q) -> Tuple.first(p) <= Tuple.first(q))
[(0, "z"), (1, "a"), (1, "b")]

fnsplit_atsplit_at(xs : List(a), n : Int) : (List(a), List(a))#

Splits the list at position n, returning (take(xs, n), drop(xs, n)) in a single pass. An n past the end gives (xs, []); n <= 0 gives ([], xs).

Examples

march> List.split_at([1, 2, 3, 4], 1)
([1], [2, 3, 4])
march> List.split_at([1, 2], 5)
([1, 2], [])

fnsum_intsum_int(xs : List(Int)) : Int#

Sums a list of integers. Returns 0 for [].

Examples

march> List.sum_int([1, 2, 3])
6
march> List.sum_int([])
0

fntailtail(xs : {List(a) | len(_) > 0}) : List(a)#

Returns the tail (all but the first element). Panics on an empty list; use tail_opt when the list may be empty.

Examples

march> List.tail([7, 8, 9])
[8, 9]
march> List.tail([7])
[]

fntail_opttail_opt(xs : List(a)) : Option(List(a))#

Returns Some(tail), or None if the list is empty.

Examples

march> List.tail_opt([1, 2])
Some([2])
march> List.tail_opt([1])
Some([])
march> List.tail_opt([])
None

fntaketake(xs : List(a), n : Int) : List(a)#

Returns the first n elements. Returns the whole list if n >= length, and [] if n <= 0.

Examples

march> List.take([1, 2, 3], 2)
[1, 2]
march> List.take([1, 2, 3], 5)
[1, 2, 3]
march> List.take([1, 2, 3], -1)
[]

fntake_whiletake_while(xs : List(a), pred : a -> Bool[p]) : List(a[p])#

Returns the longest prefix of elements satisfying pred, stopping at the first element that fails. Every element of the result is known to satisfy pred (an abstract refinement p, as for filter).

Examples

march> List.take_while([1, 2, 5, 1], fn x -> x < 3)
[1, 2]
march> List.take_while([5, 1], fn x -> x < 3)
[]

fnunzipunzip(pairs : List((a, b))) : (List(a), List(b))#

Splits a list of pairs into a pair of lists (first components, second components). The inverse of zip.

Examples

march> List.unzip([(1, "a"), (2, "b")])
([1, 2], ["a", "b"])
march> List.unzip([])
([], [])

fnzipzip(xs : List(a), ys : List(b)) : List((a, b))#

Pairs up elements from two lists. Stops at the shorter list.

Examples

march> List.zip([1, 2, 3], ["a", "b", "c"])
[(1, "a"), (2, "b"), (3, "c")]

march> List.zip([1, 2], ["a", "b", "c", "d"])
[(1, "a"), (2, "b")]

fnzip_withzip_with(xs : List(a), ys : List(b), f : a -> b -> c) : List(c)#

Like zip but applies f(x, y) to each pair of elements instead of building tuples. Stops at the shorter list.

Examples

march> List.zip_with([1, 2, 3], [10, 20], fn (a, b) -> a + b)
[11, 22]