List module

Purely-functional, singly-linked lists.

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>