NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX

The vector datatype

The Standard ML library provides vectors. A value of type 'a vector is a fixed-length collection of values of type 'a. Vectors differ from lists in their access properties. A vector is a random access data structure, whereas lists are strictly sequential access. With a list of a thousand elements it takes longer to access the last element than the first but with a vector the times are the same. The penalty to be paid for this convenience is that we are not able to subdivide a vector as efficiently as a list into its `head' and its `tail' and thus when programming with vectors we do not write pattern matching function definitions. Indeed, we cannot write pattern matching function definitions because we do not have access to the constructors of the vector datatype, they are not exported from the Vector structure in the Standard ML library. If we ever have occasion to wish to split a vector into smaller parts then we work with vector slices which are triples of a vector, a start index and a length.

Vector constants resemble list constants, only differing in the presence of a hash before the opening bracket. Thus this is a vector constant of length five and type int vector.

#[2, 4, 8, 16, 32];

We can obtain a sub-vector #[8, 16] by extracting a slice from this one.

Vector.extract (#[2,4,8,16,32], 2, SOME 2);

We can convert a list into a vector.

Vector.fromList [2, 4, 8, 16, 32];

A suitable use of a vector is in implementing a lookup table. We could revisit our day function [*] and re-implement it using a vector in place of pattern matching.

fun day' d = Vector.sub (#["Monday", "Tuesday", "Wednesday",
  "Thursday", "Friday", "Saturday"], d) handle Subscript => "Sunday";

The effect is entirely the same. The handled exception provides a catch-all case just as the wild card in the last pattern caught all other arguments, including negative numbers. As we have noted, the subscripting function Vector.sub provides constant-time access into the vector unlike the indexing function List.nth for lists and thus it is appropriate that it has a different name to remind us of this different execution behaviour.

NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX