HELP ARRAY Robert Duncan, January 1990
Revised November 1994
Sequences with constant time access and update.
CONTENTS - (Use g to access required sections)
-- The Array Module
-- The Array Type
-- Array Functions
-- The Array Module ---------------------------------------------------
signature Array
signature ARRAY
structure Array : Array
The structure -Array- provides an implementation of simple
one-dimensional arrays. The structure is described by the following
signature:
signature Array = sig
eqtype 'a array
exception Size
exception Subscript
val array : int * '_a -> '_a array
val tabulate : int * (int -> '_a) -> '_a array
val arrayoflist : '_a list -> '_a array
val length : 'a array -> int
val sub : 'a array * int -> 'a
val update : 'a array * int * 'a -> unit
end
signature ARRAY = Array
The -Array- module is not part of the Definition, but can be
considered standard insofar as it is supported by all current
Standard ML compilers. See HELP * EXTENDED_ARRAY for additional
(non-standard) functions on arrays and HELP * VECTOR for non-
updatable array-like objects.
-- The Array Type -----------------------------------------------------
eqtype 'a array
The type of arrays. An array is a sequence of elements all the same
type which supports indexed access and update in constant time. For
an array of length -n-, index values are integers in the range
0 <= i < n
The array type is abstract in the sense that it has no data
constructors -- arrays can be created and manipulated only by the
functions described in this file -- but it does admit equality.
Array values are one-dimensional only; higher-order arrays must be
simulated with arrays of arrays.
Arrays share with references the property of being updatable. The
semantics of arrays can be properly described with the following
model implementation based on vectors (see HELP * VECTOR):
structure Array : Array = struct
datatype 'a array = ARRAY of 'a ref Vector.vector
(* ... function definitions given below *)
end; (* structure Array *)
Updating a particular element of an array means changing the value
at the corresponding address (equivalent to updating a reference in
the model) and such a change is visible everywhere. This property
means that the types of the array creation functions must be
imperative in order to be type-safe, just as the type of the -ref-
constructor is imperative. This in turn means that type constraints
may sometimes be needed at the points at which these functions are
applied.
Equality on arrays is implemented analogously to equality on
references: two arrays are equal if and only if they occupy the same
range of addresses in memory, such that the updating of either one
causes an equivalent change in the other. This definition follows
directly from the model implementation. In addition, the array type
constructor shares with -ref- the special property that the type
'ty array
is always an equality type regardless of whether 'ty is itself an
equality type.
The zero-length array is a unique object, so that the equation
array(0, x) = array(0, x)
is true for any -x-.
-- Array Functions ----------------------------------------------------
The descriptions of functions given below are illustrated with model
definitions based on the abstract type defined above and using functions
from the -Vector- module (see HELP * VECTOR). The real definitions are
more space-efficient than those given here, but cannot be represented
directly in Standard ML.
exception Size
val array (n : int, x : '_a) : '_a array
Constructs a new array of size -n-, where every element of the array
is initialised with the value -x-. Raises the exception -Size- if
-n- is negative (note that this exception is identical to that in
the Vector module). Because this function returns a new array, its
result type is necessarily imperative as discussed above.
exception Size = Vector.Size
fun array(n, x) = ARRAY(Vector.tabulate(n, fn _ => ref x))
val tabulate (n : int, init : int -> '_a) : '_a array
Constructs a new array of size -n-, where the i'th element of the
array is initialised with the value -init(i)-. Raises the exception
-Size- (described above) if -n- is negative. Because this function
returns a new array, its result type is necessarily imperative as
discussed above.
fun tabulate(n, init) =
ARRAY(Vector.tabulate(n, fn i => ref(init(i))))
val arrayoflist (l : '_a list) : '_a array
Constructs a new array of size -length(l)-, where the i'th element
of the array is initialised with the corresponding item from the
list. Because this function returns a new array, its result type is
necessarily imperative as discussed above.
fun arrayoflist(l) = ARRAY(Vector.vector(map ref l))
val length (a : 'a array) : int
Returns the number of elements in the array -a-. This is a
constant-time operation.
fun length(ARRAY(v)) = Vector.length(v)
exception Subscript
val sub (a : 'a array, i : int) : 'a
val update (a : 'a array, i : int, x : 'a) : unit
The function -sub- returns the i'th element of the array -a-; the
function -update- updates that element in place to have the value
-x-. Both are constant-time operations. In either case, the
exception -Subscript- is raised for values of -i- outside the range
0 <= i < length(a)
The exception -Subscript- is identical to that in the -Vector-
module.
exception Subscript = Vector.Subscript
fun sub(ARRAY(v), i) = !(Vector.sub(v, i))
and update(ARRAY(v), i, x) = Vector.sub(v, i) := x
NB: -sub- is intended to be an infix operator of precedence 9. It is
recommended that whenever the -Array- structure is opened, an
appropriate fixity directive should be appended, e.g:
open Array
infix 9 sub
--- C.all/pml/help/array
--- Copyright University of Sussex 1994. All rights reserved. ----------