Chapter 4: Vectors and Arrays

This chapter describes Poly/ML's implementation of vectors and arrays (vectors are non-updatable arrays). The structures Vector and Array are not part of the Standard ML Initial Basis and may not be supported by all implementations of Standard ML, but we don't know of any serious implementation that doesn't support them.

4.1 Vectors

The structure Vector contains the following items:

eqtype 'a vector
val vector : 'a list -> 'a vector

val length : 'a vector int

exception Subscript
val sub : 'a vector * int -> 'a

exception Size
val tabulate : int * (int -> 'a) -> 'a vector

The purpose of these is as follows:

Vector.vector l produces a vector whose elements are the members of the list l.

Vector.length v returns the number of elements in the vector v.

Vector.sub (v,n) returns the n'th element of the vector v. It raises the exception Vector.Subscript if n is outside the range 0 < n < Vector.length v.

Vector.tabulate (n,f) is an alternative way to create a vector. It raises the exception Vector.Size if n is negative; otherwise it creates a vector of length n whose i'th element is (f i).

Note: vector is an equality type. Two vectors are equal if they consist of the same elements in the same order.

4.2 Arrays

The structure Array contains the following items:

eqtype 'a array
val arrayoflist : '_a list -> '_a array

val length : 'a array -> int

exception Subscript
val sub : 'a array * int -> 'a
val update : 'a array * int 'a -> unit

exception Size
val tabulate : int * (int -> '_a) -> '_a array
val array : int * '_a -> '_a array

The purpose of these is as follows:

Array.arrayoflist l produces an array whose initial values are the members of the list 1.

Array.length a returns the number of elements in the array a.

Array.sub (a,n) returns the n'th element of the array a. It raises the exception Array.Subscript if n is outside the range 0 < n < Array.length a.

Array.update (a,n,x) updates the n'th element of the array a to be x. It raises the exception Array.Subscript if n is outside the range 0 < n < Array.length a.

Array.tabulate (n,f) is an alternative way to create an array. It raises the exception Array.Size if n is negative; otherwise it creates an array of length n whose i'th element is (f i).

Array.array (n,x) creates an array of length n where every element of the array has the initial value x. It raises the exception Array.Size if n is negative.

Note 1: array is an equality type that behaves rather like ref; two arrays are distinct if it is possible to update one without updating the other. This means that they are equal if they were created by the same function call or if they are both of length zero.

Note 2: arrays are like refs in that they can be updated; this is why imperative type variables ('_a) must appear in the types of the array-creation functions.

Note 3: The two Subscript exceptions (Vector.Subscript and Array.Subscript) are identical, as are the two Size exceptions (Vector.Size and Array.Size). This means that a handler for Vector.Subscript will also catch Array.Subscript and vice versa.