HELP VECTOR Robert Duncan, November 1990 Sequences with constant time access. CONTENTS - (Use g to access required sections) -- The Vector Module -- The Vector Type -- Vector Functions -- The Vector Module -------------------------------------------------- signature Vector signature VECTOR structure Vector : Vector The structure -Vector- provides an implementation of simple, one-dimensional, read-only vectors. The structure is described by the following signature: signature Vector = sig eqtype 'a vector exception Size exception Subscript val vector : 'a list -> 'a vector val tabulate : int * (int -> 'a) -> 'a vector val length : 'a vector -> int val sub : 'a vector * int -> 'a end signature VECTOR = Vector The -Vector- module is not part of the Definition, but can be considered standard insofar as it is supported by all current Standard ML compilers. For additional (non-standard) functions on vectors see HELP * EXTENDED_VECTOR. For traditional updatable arrays see HELP * ARRAY. -- The Vector Type ---------------------------------------------------- eqtype 'a vector The type of vectors. A vector is a sequence of elements all the same type which supports indexed access in constant time. For a vector of length -n-, index values are integers in the range 0 <= i < n Vectors are not updatable: changing a single element requires copying the whole vector. See HELP * ARRAY for updatable vector-like objects. The vector type is abstract in the sense that it has no data constructors -- vectors can be created and manipulated only by the functions described in this file -- but it does admit equality, two vectors being equal whenever they contain the same elements in the same order. The semantics of vectors can be described with the following model implementation: structure Vector : Vector = struct datatype 'a vector = VECTOR of 'a list (* ... function definitions given below *) end; (* structure Vector *) This correctly illustrates the static and dynamic properties of vectors, but does not capture their space and time efficiency: it is impossible to represent constant-time access in Standard ML, so this feature is provided directly by the compiler. -- Vector Functions --------------------------------------------------- The descriptions of functions given below are illustrated with model definitions based on the datatype defined above; as explained already, these are considerably less efficient than the real implementations which cannot be written in Standard ML. val vector (l : 'a list) : 'a vector Constructs a new vector of size -length(l)-, where the i'th element of the vector is initialised with the corresponding item from the list. val vector = VECTOR; exception Size val tabulate (n : int, init : int -> 'a) : 'a vector Constructs a new vector of size -n-, where the i'th element of the vector is initialised with the value -init(i)-. Raises the exception -Size- if -n- is negative. exception Size fun tabulate(n, init) = let fun tab i = if i = n then [] else init(i) :: tab(i+1) in if n < 0 then raise Size else VECTOR(tab 0) end; val length (v : 'a vector) : int Returns the number of elements in the vector -v-. This is a constant-time operation. fun length(VECTOR l) = let fun len [] = 0 | len (_::l) = len l + 1 in len l end; exception Subscript val sub (v : 'a vector, i : int) : 'a Returns the i'th element of the vector -v-. Raises the exception -Subscript- if -i- is outside the range 0 <= i < length(v) This is a constant-time operation. exception Subscript fun sub(VECTOR l, i) = let fun nth 0 (x::_) = x | nth i (_::l) = nth (i-1) l | nth _ [] = raise Subscript in nth i l end; NB: -sub- is intended to be an infix operator of precedence 9. It is recommended that whenever the -Vector- structure is opened, an appropriate fixity directive should be appended, e.g: open Vector infix 9 sub --- C.all/pml/help/vector --- Copyright University of Sussex 1994. All rights reserved. ----------