The Standard ML Basis Library

The Array structure

The Array structure provides polymorphic mutable sequences. Arrays also have a special equality property: two arrays are equal if they are the same array, i.e., created by the same call to a primitive array constructor such as array, fromList, etc.; otherwise they are not equal. This also holds for arrays of zero length. Thus, type t array admits equality even if ty does not.

Synopsis

signature ARRAY
structure Array : ARRAY


Interface

eqtype 'a array
eqtype 'a vector
val maxLen : int
val array : (int * 'a) -> 'a array
val fromList : 'a list -> 'a array
val tabulate : (int * (int -> 'a)) -> 'a array
val length : 'a array -> int
val sub : ('a array * int) -> 'a
val update : ('a array * int * 'a) -> unit
val extract : ('a array * int * int option) -> 'a vector
val copy : {src : 'a array, si : int, len : int option, dst : 'a array, di : int} -> unit
val copyVec : {src : 'a vector, si : int, len : int option, dst : 'a array, di : int} -> unit
val appi : ((int * 'a) -> unit) -> ('a array * int * int option) -> unit
val app : ('a -> unit) -> 'a array -> unit
val foldli : ((int * 'a * 'b) -> 'b) -> 'b -> ('a array * int * int option) -> 'b
val foldri : ((int * 'a * 'b) -> 'b) -> 'b -> ('a array * int * int option) -> 'b
val foldl : (('a * 'b) -> 'b) -> 'b -> 'a array -> 'b
val foldr : (('a * 'b) -> 'b) -> 'b -> 'a array -> 'b
val modifyi : ((int * 'a) -> 'a) -> ('a array * int * int option) -> unit
val modify : ('a -> 'a) -> 'a array -> unit


Description

eqtype 'a array

eqtype 'a vector

maxLen

is the maximum length of arrays supported by this implementation. Attempts to create larger arrays will result in the Size exception being raised.

array (n, init)

creates a new array of length n; each element is initialized to the value init. If n < 0 or maxLen < n, then the Size exception is raised.

fromList l

creates a new array from a list of elements. If the length of the list is greater than maxLen, then the Size exception is raised.

tabulate (n, f)

creates an array of n elements, where the elements are defined in order of increasing index by applying f to the element's index. This is equivalent to the expression:

	  fromList (List.tabulate (n, f))
	  

If n < 0 or maxLen < n, then the Size exception is raised.

length arr

returns |arr|, the length of the array arr.

sub (arr, i)

returns the ith element of the array arr. If i < 0 or |arr| < i, then the Subscript exception is raised.

update (arr, i, x)

sets the ith element of the array arr to x. If i < 0 or |arr| < i, then the Subscript exception is raised.

extract slice

extracts the array slice slice from the array arr, and returns it as a vector. If the slice is not valid, then the exception Subscript is raised.

copy {src, si, len, dst, di}

copyVec {src, si, len, dst, di}

copy the slice specified by (src, si, len) into the array dst, with element si being copied to position di in the destination array. The function copy takes an array slice as its source, while the function copyVec uses a vector slice. If the source slice is not valid, then the Subscript exception is raised. Likewise, if di < 0 or if |dst| < di+n, where n is the number of elements copied, then the Subscript exception is raised.

appi f slice

app f arr

apply the function f to the elements of an array in left to right order (i.e., increasing indices). The more general appi function applies f to the elements of the array slice slice and supplies both the element and the element's index to the function f. If slice is not valid, then the exception Subscript is raised.

The function app applies f to the whole array and does not supply the element index to f. Thus the expression app f arr is equivalent to:

	    appi (f o #2) (arr, 0, NONE)
	  

foldli f init slice

foldri f init slice

foldl f init arr

foldr f init arr

fold the function f over the elements of an array, using the value init as the initial value. The functions foldli and foldl apply the function f from left to right (increasing indices), while the functions foldri and foldr work from right to left (decreasing indices). The more general functions foldli and foldri work on array slices, and supply both the element and the element's index to the function f. The functions foldl and foldr work on the whole ar! ray arr and do not supply the element index to f.

More precisely, if extract slice = Vector.fromList [A0,A1,...,An], then the expression foldli f init slice is equivalent to:

	    List.foldl (fn ((i, a), x) => f(i, a, x))
	      init [(0,A0),(1,A1),...,(n,An)]
	  

The expression foldl f init arr is equivalent to:

	    foldli (fn (_, a, x) => f(a, x))
	      init (arr, 0, NONE)
	  

The analogous equivalences hold for foldri and List.foldr.

Example:

One can extract the list of elements in an array arr by the expression:

	      foldr (op ::) [] arr
	    

modifyi f slice

modify f arr

apply the function f to the elements of an array in left to right order (i.e., increasing indices), and replace the elements with the results of f. The more general modifyi function applies f to the elements of the array slice slice and supplies both the element and the element's index to the function f. If slice is not valid, then the exception Subscript is raised.

The function modify applies f to the whole array and does not supply the element index to f. Thus the expression modify f arr is equivalent to:

	    modifyi (f o #2) (arr, 0, NONE)
	  

See Also

MONO_ARRAY, Vector

Last Modified April 16, 1996
Copyright © 1996 AT&T