> 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".
This would be perfectly reasonable.
> 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.
Wao! You've got a really impressive compiler.
> 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.
Oups. I frankly doubt that we can define in Caml something like your fibs:
fibs =
arrray (1,n) ([(1,1),(2,1)] ++ [(i, fibs!(i-1) + fibs!(i-2)) | i <- [3..n]])
Don't forget our evaluation regime that will try to completely
evaluate the list
([(1,1),(2,1)] ++ [(i, fibs!(i-1) + fibs!(i-2)) | i <- [3..n]])
before calling the array creation function. What's the meaning of
fibs! then, since fibs has no existance yet ?
I think that in these examples, lazy evaluation is important: the list
is lazyly evaluated, and the fibs array elements are assigned one at a
time, as soon as the corresponding pair of the list has been computed.
As far as I can imagine the way vectors are handled in a lazy
language, the compiler must ``initialize'' vectors elements with a
dummy ``undefined value'', and updates this dummy value as usual as
soon as a value is provided for the dummy.
This way you always have the ``not yet initialized'' test for free,
since attempts to access such an element will raise some ``bottom'' or
``undefined'' exception. However, for the ``completely initialized
test'' you also need to access all the elements of the new vector
(once more accessing an undefined element will automatically raise an
exception). And I suspect also that the ``initialized only once'' check
will be tricky... (or similar to an ML solution).
So, I don't know how to implement your elegant solution in a strict
language (unless by adding some lazy evaluation regime for some
functions, such as ... array!)
> 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.
Yes this is really a interesting notation. However, I studied it once,
and as far as I remember I had the feeling that lazy evaluation was
also mandatory to handle ``real'' cases other than the trivial ones (such
as. [(i, f i) | i <- [1..n]] that can be easily done in Caml): complex
mutually recursive lists, where f and the bounds where functions of
other lists given in comprehension.
Also, I remember my strange feeling at reading pieces of code like:
[i | i <- [1..2**32]]
which is not completely reasonable in a strict language.
Anyway, you're right that we could may give it a try ...
Thank you for your interesting remarks.
Pierre Weis
INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/
This archive was generated by hypermail 2b29 : Mon May 22 2000 - 18:18:46 MET DST