alice
library
manual.

Alice Project

The List structure


________ Synopsis ____________________________________________________

    signature LIST
    structure List : LIST
  

An extended version of the Standard ML Basis' List structure.

See also: ListPair, Vector


________ Import ______________________________________________________

Imported implicitly.


________ Interface ___________________________________________________

    signature LIST =
    sig
	datatype 'a list = nil | op:: of 'a * 'a list
	type     'a t    = 'a list						(**)

	exception Empty

	val null :        'a list -> bool
	val length :      'a list -> int

	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 sub :         'a list * int -> 'a
	val take :        'a list * int -> 'a list
	val drop :        'a list * int -> 'a list
	val split :       'a list * int -> 'a list * 'a list

	val rev :         'a list -> 'a list
	val op @ :        'a list * 'a list -> 'a list
	val revAppend :   'a list * 'a list -> 'a list
	val concat :      'a list list -> 'a list
	val tabulate :    int * (int -> 'a) -> 'a list
	val index :       'a list -> (int * 'a) list

	val app :         ('a -> unit) -> 'a list -> unit
	val appr :        ('a -> unit) -> 'a list -> unit
	val map :         ('a -> 'b) -> 'a list -> 'b list
	val mapPartial :  ('a -> 'b option) -> 'a list -> 'b list
	val foldl :       ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
	val foldr :       ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
	val all :         ('a -> bool) -> 'a list -> bool
	val exists :      ('a -> bool) -> 'a list -> bool
	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 appi :        (int * 'a -> unit) -> 'a list -> unit
	val appri :       (int * 'a -> unit) -> 'a list -> unit
	val mapi :        (int * 'a -> 'b) -> 'a list -> 'b list
	val mapiPartial : (int * 'a -> 'b option) -> 'a list -> 'b list
	val foldli :      (int * 'a * 'b -> 'b) -> 'b -> 'a list -> 'b
	val foldri :      (int * 'a * 'b -> 'b) -> 'b -> 'a list -> 'b
	val alli :        (int * 'a -> bool) -> 'a list -> bool
	val existsi :     (int * 'a -> bool) -> 'a list -> bool
	val findi :       (int * 'a -> bool) -> 'a list -> (int * 'a) option
	val filteri :     (int * 'a -> bool) -> 'a list -> (int * 'a) list
	val partitioni :  (int * 'a -> bool) -> 'a list -> (int * 'a) list * (int * 'a) list

	val contains :    ''a list -> ''a -> bool
	val notContains : ''a list -> ''a -> bool

	val equal :       ('a * 'a -> bool) -> 'a list * 'a list -> bool
	val collate :     ('a * 'a -> order) -> 'a list * 'a list -> order

	val isSorted :    ('a * 'a -> order) -> 'a list -> bool
	val sort :        ('a * 'a -> order) -> 'a list -> 'a list
    end
  

________ Description _________________________________________________

Items not described here are as in the Standard ML Basis' List structure.

type t = list

A local synonym for type list.

sub (l, i)

Returns the ith element of the list l, counting from 0. Raises Subscript if i < 0 or i >= length l. This function is a synonym for nth, for consistency with other collection types like vectors and arrays.

split (l, i)

Returns a pair (l1,l2) of lists, where l1 contains the first i elements of l and l2 the remaining ones. Raises Subscript if i < 0 or i >= length l. Equivalent to (take (l,i), drop (l,i)).

index l

Pairs each element of the list l with its index in l, counting from 0, and returns the list of pairs.

appr f l

Like app, but applies f in right to left order.

appi f l
appri f l
mapi f l
mapiPartial f l
foldli f b l
foldri f b l
alli f l
existsi f l
findi f l
filteri f l
partitioni f l

Indexed versions of the functions app, appr, map, mapPartial, foldl, foldr, all, exists, find, filter and partition. The index of each element (starting from 0) is passed to f as an additional argument. For appri and foldri, processing starts at the highest index. The functions findi, filteri and partitioni return indices along with the corresponding elements. The following equivalences hold:

	appi f l        = app f (index l)
	appri f l       = appr f (index l)
	mapi f l        = map f (index l)
	mapiPartial f l = mapPartial f (index l)
	foldli f b l    = foldl (fn ((i,a),b) => f(i,a,b)) b (index l)
	foldri f b l    = foldr (fn ((i,a),b) => f(i,a,b)) b (index l)
	alli f l        = all f (index l)
	existsi f l     = exists f (index l)
	findi f l       = find f (index l)
	filteri f l     = filter f (index l)
	partitioni f l  = partition f (index l)

        app f l         = appi (f o #2) l
        appr f l        = appri (f o #2) l
        map f l         = mapi (f o #2) l
        mapPartial f l  = mapiPartial (f o #2) l
        foldl f b l     = foldli (fn (i,a,b) => f(a,b)) b l
        foldr f b l     = foldri (fn (i,a,b) => f(a,b)) b l
        all f l         = alli (f o #2) l
        exists f l      = existsi (f o #2) l
        find f l        = Option.map #2 (findi (f o #2) l)
        filter f l      = map #2 (filteri (f o #2) l)
        partition f l   = Pair.map (map #2, map #2) (partitioni (f o #2) l)
contains l a

Returns true if the element a occurs in the list l; otherwise false.

notContains l a

Returns true if the element a does not occur in the list l; otherwise false. Equivalent to not(contains l a).

equal eq (l1, l2)

Creates a customized equality function on lists given an equality on the element type.

isSorted f l

Returns true iff l is sorted with respect to the ordering function f.

sort f l

Returns a new list that contains the same elements as l, but sorted with respect to the ordering function f. Sorting may be unstable with respect to equal elements.



last modified 2007/Mar/30 17:10