The List
structure
The List structure provides a collection of utility functions for manipulating polymorphic lists, traditionally an important datatype in functional programming.
Lists are usually supported with a large collection of library functions. Here, we provide a somewhat smaller collection of operations that reflect common usage. We feel the collection is moderately complete, in that most programs will not need to define additional list operations. We have tried to adopt names that reflect a consensus from various existing libraries and texts. We have avoided functions relying on equality types.
Different SML implementations may still desire to provide list utility library modules, though if the design of List is right, they should be small.
Synopsis
signature LIST
structure List
: LIST
Interface
datatype list = datatype 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 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
Description
-
datatype list
-
-
exception Empty
-
indicates an operation requiring a non-empty list was given an empty list as an argument.
-
null l
-
returns
true
if the list l isnil
.
-
length l
-
returns the number of elements in the list l.
-
l1 @ l2
-
returns the list that is the concatenation of l1 and l2.
-
hd l
-
returns the first element of l. Raises Empty if l is
nil
.
-
tl l
-
returns all but the first element of l. Raises Empty if l is
nil
.
-
last l
-
returns the last element of l. Raises Empty if l is
nil
.
-
getItem l
-
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 type(int,char list) StringCvt.reader
and scan be used to scan decimal integers from lists of characters.
-
nth (l, i)
-
returns the ith element of the list l, counting from 0. Raises Subscript if i < 0 or i >=
length
l.
-
take (l, i)
-
returns the first i elements of the list l. Raises Subscript if i < 0 or i >=
length
l.
-
drop (l, 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 thattake(l, i) @ drop(l, i) = l
when 0 <= i <=length
l.
-
rev l
-
returns a list consisting of l's elements in reverse.
-
concat l
-
returns the list that is the concatenation of all the lists in l.
-
revAppend (l1, l2)
-
returns
(rev l1) @ l2
.
-
app f l
-
applies f to the elements of l, from left to right.
-
map f l
-
applies f to each element of l from left to right, returning the list of results.
-
mapPartial f l
-
applies f to each element of l from left to right, returning a list of results where f was defined. f is not defined for an element of l if f applied to the element returns NONE.
-
find f l
-
applies f to each element x of the list l, from left to right, until
f x
evaluates totrue
; returnsSOME x
if such an x exists, otherwise NONE.
-
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 totrue
, in the same order as the occurred in the argument list.
-
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 whichf x
evaluated totrue
, and neg is the list of those for whichf x
evaluated tofalse
. The elements of pos and neg retain the same relative order they possessed in l.
-
foldl f b [x1, x2, ..., xn]
-
returns
f(xn,...,f(x2, f(x1, b))...)
or b if the list is empty.
-
foldr f b [x1, x2, ..., xn]
-
returns
f(x1, f(x2, ..., f(xn, b)...))
or b if the list is empty.
-
exists f l
-
applies f to each element x of the list l, from left to right, until
f x
evaluates totrue
; returnstrue
if such an x exists andfalse
otherwise.
-
all f l
-
applies f to each element x of the list l, from left to right, until
f x
evaluates tofalse
; returnsfalse
if such an x exists andtrue
otherwise. Equivalent tonot(exists (not o f) l))
.
-
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.
See Also
General, ListPair