From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA01177 for caml-red; Mon, 22 May 2000 18:12:13 +0200 (MET DST) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id WAA15738 for ; Sat, 20 May 2000 22:14:01 +0200 (MET DST) Received: from mail4.microsoft.com (mail4.microsoft.com [131.107.3.122]) by nez-perce.inria.fr (8.10.0/8.10.0) with SMTP id e4KKE0918236 for ; Sat, 20 May 2000 22:14:00 +0200 (MET DST) Received: from 157.54.9.103 by mail4.microsoft.com (InterScan E-Mail VirusWall NT); Sat, 20 May 2000 13:13:52 -0700 (Pacific Daylight Time) Received: by INET-IMC-04 with Internet Mail Service (5.5.2651.58) id ; Sat, 20 May 2000 13:13:52 -0700 Message-ID: <9E6D5163D780C142B2B58107F4E605A9021C994B@red-msg-23.redmond.corp.microsoft.com> From: Simon Peyton-Jones To: Pierre Weis , hwxi@ECECS.UC.EDU Cc: caml-list@inria.fr Subject: RE: reference initialization Date: Sat, 20 May 2000 13:13:52 -0700 X-Mailer: Internet Mail Service (5.5.2651.58) Sender: weis | 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