List structure

Up to index

The List structure provides the list type and a comprehensive set of operations for constructing, examining, and transforming singly-linked lists. Many operations are provided in both left-to-right and right-to-left variants.

Specified by the Standard ML Basis Library.

Synopsis

datatype 'a list = nil | :: of 'a * 'a list

exception Empty

val null : 'a list -> bool
val length : 'a list -> int
val @ : 'a list * 'a list -> 'a list
val hd : 'a list -> 'a
val tl : 'a list -> 'a list
val last : 'a list -> 'a
val getItem : 'a list -> ('a * 'a list) option
val nth : 'a list * int -> 'a
val only : 'a list -> 'a
val take : 'a list * int -> 'a list
val drop : 'a list * int -> 'a list
val rev : 'a list -> 'a list
val concat : 'a list list -> 'a list
val revAppend : 'a list * 'a list -> 'a list
val app : ('a -> unit) -> 'a list -> unit
val map : ('a -> 'b) -> 'a list -> 'b list
val mapPartial : ('a -> 'b option) -> 'a list -> 'b list
val find : ('a -> bool) -> 'a list -> 'a option
val filter : ('a -> bool) -> 'a list -> 'a list
val partition : ('a -> bool) -> 'a list -> 'a list * 'a list
val foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
val foldr : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
val exists : ('a -> bool) -> 'a list -> bool
val all : ('a -> bool) -> 'a list -> bool
val tabulate : int * (int -> 'a) -> 'a list
val collate : ('a * 'a -> order) -> 'a list * 'a list -> order
val mapi : (int * 'a -> 'b) -> 'a list -> 'b list
(* Morel extensions *)
val except : 'a list list -> 'a list
val intersect : 'a list list -> 'a list

datatype 'a list

is the type of polymorphic singly-linked lists.

exception Empty

is raised by operations that require a non-empty list when given an empty list.

null

null l (or l.null ()) returns true if the list l is empty.

length

length l (or l.length ()) returns the number of elements in the list l.

@

l1 @ l2 returns the list that is the concatenation of l1 and l2.

hd

hd l (or l.hd ()) returns the first element of l. Raises Empty if l is nil.

tl

tl l (or l.tl ()) returns all but the first element of l. Raises Empty if l is nil.

last

last l (or l.last ()) returns the last element of l. Raises Empty if l is nil.

getItem

getItem l (or l.getItem ()) returns NONE if the list is empty, and SOME (hd l, tl l) otherwise. This function is particularly useful for creating value readers from lists of characters. For example, Int.scan StringCvt.DEC getItem has the type (int, char list) StringCvt.reader and can be used to scan decimal integers from lists of characters.

nth

nth (l, i) (or l.nth i) returns the i(th) element of the list l, counting from 0. Raises Subscript if i < 0 or i ≥ length l. We have nth(l, 0) = hd l, ignoring exceptions.

only

only l (or l.only ()) returns the only element of list l. Raises Empty if l is empty, Size if l has more than one element.

take

take (l, i) (or l.take i) returns the first i elements of the list l. Raises Subscript if i < 0 or i > length l. We have take(l, length l) = l.

drop

drop (l, i) (or l.drop i) returns what is left after dropping the first i elements of the list l. Raises Subscript if i < 0 or i > length l.

It holds that take(l, i) @ drop(l, i) = l when 0 ≤ i ≤ length l. We also have drop(l, length l) = [].

rev

rev l (or l.rev ()) returns a list consisting of l's elements in reverse order.

concat

concat l returns the list that is the concatenation of all the lists in l in order. concat [l1, l2, ... ln] = l1 @ l2 @ ... @ ln

revAppend

revAppend (l1, l2) (or l1.revAppend l2) returns (rev l1) @ l2.

app

app f l applies f to the elements of l, from left to right.

map

map f l applies f to each element of l from left to right, returning the list of results.

mapPartial

mapPartial f l applies f to each element of l from left to right, returning a list of results, with SOME stripped, where f was defined. f is not defined for an element of l if f applied to the element returns NONE. The above expression is equivalent to:

((map valOf) o (filter isSome) o (map f)) b

find

find f l applies f to each element x of the list l, from left to right, until f x evaluates to true. It returns SOME (x) if such an x exists; otherwise it returns NONE.

filter

filter f l applies f to each element x of l, from left to right, and returns the list of those x for which f x evaluated to true, in the same order as they occurred in the argument list.

partition

partition f l applies f to each element x of l, from left to right, and returns a pair (pos, neg) where pos is the list of those x for which f x evaluated to true, and neg is the list of those for which f x evaluated to false. The elements of pos and neg retain the same relative order they possessed in l.

foldl

foldl f init [x1, x2, ..., xn] returns f(xn, ... , f(x2, f(x1, init))...) or init if the list is empty.

foldr

foldr f init [x1, x2, ..., xn] returns f(x1, f(x2, ..., f(xn, init)...)) or init if the list is empty.

exists

exists f l applies f to each element x of the list l, from left to right, until f(x) evaluates to true; it returns true if such an x exists and false otherwise.

all

all f l applies f to each element x of the list l, from left to right, until f(x) evaluates to false; it returns false if such an x exists and true otherwise. It is equivalent to not(exists (not o f) l)).

tabulate

tabulate (n, f) returns a list of length n equal to [f(0), f(1), ..., f(n-1)], created from left to right. Raises Size if n < 0.

collate

collate f (l1, l2) performs lexicographic comparison of the two lists using the given ordering f on the list elements.

mapi

mapi f l applies the function f to the elements of the argument list l, supplying the list index and element as arguments to each call.

except

except l returns the list that is the concatenation of all the lists in l in order. concat [l1, l2, ... ln] = l1 @ l2 @ ... @ ln

intersect

intersect l returns the list that is the concatenation of all the lists in l in order. concat [l1, l2, ... ln] = l1 @ l2 @ ... @ ln