List
structureThe 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.
signature LIST
structure List
: LIST
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
datatype list
exception Empty
null l
true
if the list l is nil
.
length l
l1 @ l2
hd l
nil
.
tl l
nil
.
last l
nil
.
getItem l
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)
length
l.
take (l, i)
length
l.
drop (l, i)
length
l. It holds that take(l, i) @ drop(l, i) = l
when 0 <= i <= length
l.
rev l
concat l
revAppend (l1, l2)
(rev l1) @ l2
.
app f l
map f l
mapPartial f l
find f l
f x
evaluates to true
; returns SOME x
if such an x exists, otherwise NONE.
filter f l
f x
evaluated to true
, in the same order as the occurred in the argument list.
partition f l
(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 f b [x1, x2, ..., xn]
f(xn,...,f(x2, f(x1, b))...)or b if the list is empty.
foldr f b [x1, x2, ..., xn]
f(x1, f(x2, ..., f(xn, b)...))or b if the list is empty.
exists f l
f x
evaluates to true
; returns true
if such an x exists and false
otherwise.
all f l
f x
evaluates to false
; returns false
if such an x exists and true
otherwise. Equivalent to not(exists (not o f) l))
.
tabulate (n, f)
[f(0), f(1), ..., f(n-1)]
, created from left to right. Raises Size if n < 0.
General, ListPair
Last Modified October 4, 1997
Comments to John Reppy.
Copyright © 1997 Bell Labs, Lucent Technologies