RE: reference initialization

[Simon Peyton-Jones <simonpj@microsoft.com>]

| val initialize :
|  int -> 'a -> ((int -> 'a) -> (int -> 'a -> unit) -> unit) -> 'a array
|  [initialize n x f] returns a fresh array of length [n],
|  with elements initialized by function [f].
|  All the elements of the new array must be assigned once and only
|  once by the function [f]. [f] received two functions as arguments,
|  one to access elements of the new array, and the other to set the
|  elements of the new array. [f] can access to element [i] of the new
|  array provided [f] has already properly initialized element [i].

This is all good stuff.  It might be worth mentioning Haskell's approach
in this context.  The main array former is

	array :: Ix ix => (ix,ix) -> [(ix,elt)] -> Array ix elt

'array' takes an upper and lower bound, both of type 'ix'.  ix is a type
variable that must be bound to a type in class Ix, which supports indexing
operations.  So that I can avoid discussion of type classes, let's
specialise
array much as 'initialize' is above, to vectors indexed by Ints:

	array :: (Int,Int) -> [(Int,elt)] -> Array Int elt

So array takes an uppper and lower bound, and a list of (index,value) pairs;
it returns an array with each element filled in.  The list should mention
each element just once, but that is not statically checked.

In conjunction with list comprehensions, this gives rise to quite nice code.
For example, to tabulate a function we might write

	array (1,n) [(i, f i) | i <- [1..n]]

Referring to existing elements is easy via recursion:

	fibs = arrray (1,n) ([(1,1),(2,1)] ++
			       [(i, fibs!(i-1) + fibs!(i-2)) | i <- [3..n]])

Notice how easily the boundary cases are specified.

Laziness means that the compiler does not need to figure out which
order to do the initialisation. In a strict language it would be a little
harder -- or perhaps one could say "it's done in the order the index,value
pairs are given".


You may wonder about the efficiency issue.  After all, it doesn't seem
great to build an intermediate list just before constructing an array.
But a bit of short-cut deforestation does the trick, and eliminates the
intermediate list.  I have to admit that a lot of things have to Work Right
in the compiler to really get the for-loop you intended, but that's what
compilers are for.


None of this is specific to Haskell or to a lazy language.  Caml could
well use it.  I mention it on this list becuase it's an aspect of the
Haskell design that I think has worked particularly well, and which 
might be of use to Camlers.

A lot of the benefit comes from the re-use (for arrays) of the 
list comprehension notation.  I forget whether Caml has such notation,
but again, it's nothing to do with laziness and it's a notation which
is really useful.

Simon