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 []).

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

Returns true if any element satisfies pred.

fnappendappend(xs : List(a), ys : List(a)) : List(a)#

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 at most size elements.

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

Concatenates a list of lists into a single list.

fndedupdedup(xs : List(a)) : List(a)#

Removes consecutive duplicate elements (keeps first of each run). Uses structural equality.

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

Drops the first n elements. Returns [] if n >= length.

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

Returns all elements except the last. Returns Nil for empty or singleton lists.

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

Drops elements while pred holds, returning the rest.

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

Applies f to each element for side effects. Returns ().

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)].

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

Returns only elements satisfying pred.

Examples

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

    march> List.filter(["foo", "", "bar", ""], fn s -> !String.is_empty(s))
    march> 
    ["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.

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

Returns the first element satisfying pred, or None.

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

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

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

Applies f to each element and concatenates the results. O(n) in the total output size.

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.

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

Returns the first element. Panics on empty list.

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

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

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

Inserts sep between every consecutive pair of elements.

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

Returns true if the list has no elements.

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

Returns the last element. Panics on empty list.

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.

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

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

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

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

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

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

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

Returns Some(nth element), or None if out of bounds.

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

Splits into (elements satisfying pred, elements not satisfying pred).

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.

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`.

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.

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) : List(Int)#

Returns [start, start+step, ...] up to but not including stop.

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)#

Returns the list in reverse order.

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

Like fold_left but returns a list of all intermediate accumulator values.

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. Uses merge sort (stable, O(n log n)).

Examples

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

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

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

Splits the list at position n, returning (take n xs, drop n xs).

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

Sums a list of integers.

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

Returns the tail (all but first element). Panics on empty list.

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

Returns Some(tail), or None if empty.

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

Returns the first n elements. Returns the whole list if n >= length.

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

Returns the longest prefix of elements satisfying pred.

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

Splits a list of pairs into two lists.

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"])
    march> 
    [(1, "a"), (2, "b"), (3, "c")]

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

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

Like zip but applies f to each pair instead of building tuples.