# List module

A singly-linked list consists of zero or more cons cells, wherein each cell contains a single list element (the cell’s head), and a pointer to the remainder of the list (the cell’s tail).

``public type List<T> = ?(T, List<T>);``

## `nil`

empty list

``public func nil<T>() : List<T>``

## `isNil`

test for empty list

``public func isNil<T>(l : List<T>) : Bool``

## `push`

aka “list cons”

``public func push<T>(x : T, l : List<T>) : List<T>``

## `last`

last element, optionally; tail recursive

``public func last<T>(l : List<T>) : ?T``

## `pop`

treat the list as a stack; combines the usual operations `head` and non-failing) `tail` into one operation

``public func pop<T>(l : List<T>) : (?T, List<T>)``

## `len`

length; tail recursive

``public func len<T>(l : List<T>) : Nat``

## `lenIsLessThan`

test length against a maximum value; tail recursive

``public func lenIsEqLessThan<T>(l : List<T>, i : Nat) : Bool``

## `lenClamp`

get the length, unless greater than a maximum value, in which return null; tail recursive

``public func lenClamp<T>(l : List<T>, i0 : Nat) : ?Nat``

## `nth`

array-like list access, but in linear time; tail recursive

``public func nth<T>(l : List<T>, n : Nat) : ?T``

## `rev`

reverse the list; tail recursive

``public func rev<T>(l : List<T>) : List<T>``

## `iter`

Called `app` in SML Basis, and `iter` in OCaml; tail recursive

``public func iter<T>(l : List<T>, f:T -> ()) : ()``

## `map`

map the list elements; non-tail recursive.

``public func map<T,S>(l : List<T>, f:T -> S) : List<S>``

## `filter`

filter the list elements; non-tail recursive

``public func filter<T>(l : List<T>, f:T -> Bool) : List<T>``

## `split`

split the list elements; non-tail recursive

``public func split<T>(l : List<T>, f:T -> Bool) : (List<T>, List<T>)``

## `mapFilter`

map and filter the list elements; non-tail recursive

``public func mapFilter<T,S>(l : List<T>, f:T -> ?S) : List<S>``

## `append`

append two lists; non-tail recursive

``public func append<T>(l : List<T>, m : List<T>) : List<T>``

## `concat`

concat (aka “list join”); tail recursive, but requires “two passes”

``public func concat<T>(l : List<List<T>>) : List<T>``

## `revAppend`

See SML Basis library; tail recursive

``public func revAppend<T>(l1 : List<T>, l2 : List<T>) : List<T>``

## `take`

“take” `n` elements from the prefix of the given list.

If the given list has fewer than `n` elements, we return the full input list.

``public func take<T>(l : List<T>, n:Nat) : List<T>``

## `drop`

``public func drop<T>(l : List<T>, n:Nat) : List<T>``

## `foldLeft`

fold list left-to-right using function `f`; tail recursive

``public func foldLeft<T,S>(l : List<T>, a:S, f:(T,S) -> S) : S``

## `foldRight`

fold the list right-to-left using function `f`; non-tail recursive

``public func foldRight<T,S>(l : List<T>, a:S, f:(T,S) -> S) : S``

## `find`

test if there exists list element for which given predicate is true

``public func find<T>(l: List<T>, f:T -> Bool) : ?T``

## `exists`

test if there exists list element for which given predicate is true

``public func exists<T>(l: List<T>, f:T -> Bool) : Bool``

## `all`

test if given predicate is true for all list elements

``public func all<T>(l: List<T>, f:T -> Bool) : Bool``

## `merge`

Given two ordered lists, merge them into a single ordered list

``public func merge<T>(l1: List<T>, l2: List<T>, lte:(T,T) -> Bool) : List<T>``

## `lessThanEq`

Compare two lists lexicographic` ordering. tail recursive.

To do: Eventually, follow `collate` design from SML Basis, with real sum types, use 3-valued `order` type here.

``public func lessThanEq<T>(l1: List<T>, l2: List<T>, lte:(T,T) -> Bool) : Bool``

## `isEq`

Compare two lists for equality. tail recursive.

`isEq(l1, l2)` is equivalent to `lessThanEq(l1,l2) && lessThanEq(l2,l1)`, but the former is more efficient.

``public func isEq<T>(l1: List<T>, l2: List<T>, eq:(T,T) -> Bool) : Bool``

## `partition`

using a predicate, create two lists from one: the “true” list, and the “false” list.

(See SML basis library); non-tail recursive.

``public func partition<T>(l: List<T>, f:T -> Bool) : (List<T>, List<T>)``

## `tabulate`

generate a list based on a length, and a function from list index to list element.

(See SML basis library); non-tail recursive.

``public func tabulate<T>(n:Nat, f:Nat -> T) : List<T>``