Paulson pp 128->

Conventional Array
------------------
(1) Block of storage, rectangular, cuboide, etc. "Linear" in some
    sense.
(2) In POP-II as a function of n arguments, where that function
    delivers a value or an array reference.
(3) A mapping of a finite range of integers to values,
    ie functional arrays.


Functional Array as Binary Tree
-------------------------------
Given index k and array (as tree) X.

 (0) if k=1 deliver X
 (1) if k is even go left with k/2
 (3) if k is odd go right with k/2

Access time is of the order O(log k) (base 2). 
However, additional space is required for left/right pointers.


Required Functions
------------------
(a) make_vector n v
    Make a vector of n elements, initialised to v
(b) get x n
    Get the nth element of x
(c) put x n v
    Put into nth element of x the value v.

Observations on put
-------------------
val x = make_vector 5 0;
val y = put x 3 99;

An entirely new array/tree is not created. Only the node
corresponding to 3d element of x is create anew. y shares the
rest of the tree with x. Therefore we can "go back" to previous
version of tree. This might be usefull within an editor (undo
command).

Observations on make_vector
---------------------------
Polymorpic. 

val x1 = make_vector 10 [];
val x2 = make_vector 5 x1;

x1 is an array of lists, and x2 is a 2-dimensional array of
lists. How much space is consumed by x2? That is, how much
sharing takes place? Lots!!


Observation on get
------------------
Only works on 1 dimensional array. How do we get from 2-d?

get (get x2 1) 5

More generally, to get from array with n subscripts

get (get (get (... (get xn i) j) k) ... ) n

fun get2 x i j = get (get x i) j;

Why can't I produce a function as follows?

fun gets x [] = x
   |gets x (i::js) = get (gets x js) i;


More Observations on put
------------------------
Only works on 1-d array. How do I deal with n-d array.

val y = get x2 1;
val x = put x2 1 (put y 3 data);

fun put2 x i j data = let val y = get x i
                      in put x i (put y j data) end;

fun put3 x i j k data = let val z = get2 x i j
                        in put2 x i j (put z k data) end;