Re: vector dot multiply

nikhil@crl.dec.com
Fri, 9 Jun 1995 09:20:58 -0400

From: nikhil@crl.dec.com
Date: Fri, 9 Jun 1995 09:20:58 -0400
Message-Id: <9506091320.AA27705@mattapoisett.crl.dec.com>
To: chet@watson.ibm.com
In-Reply-To: <9506091150.AA30307@lusitania.watson.ibm.com> (message from Chet Murthy on Fri, 09 Jun 1995 07:50:06 -0400)
Subject: Re: vector dot multiply

Chet Murthy writes:
> > >Also, is there a similar construct to Haskell array/list comprehensions?
> >
> > Bird and Wadler's book gives a simple translation scheme
> > for list comprehensions to map+filter functions (pp63-64).
> > This may meet your requirements.
>
> That translation is wildly inefficient, too. There's a reason
> that lazy languages, and pure languages, haven't caught on --
> it's called efficiency. It's far more efficient to construct
> a decent set of imperative classes (e.g. Rogue Wave Vector Classes)
> than to try to import into CAML (which was, after all, designed
> to (IMHO) not penalize the imperative code writer) the constructs of
> intrinsically broken languages like Haskell.

I don't understand why the question about list/array comprehensions
provokes this sharp comment about lazy languages and Haskell in
particular.

1) List comprehensions and array comprehensions are simply a
convenient way to express nested loops, collecting a subset of the
results. The notation is completely neutral to whether you embed
it in a strict, lazy, pure or impure language. It has nothing
to do do with Haskell per se.

In fact, modern list comprehension notation was originally
introduced by Darlington and Burstall in the _strict_ language Hope
at Edinburgh.

A similar construct existed even earlier in the _strict_, _impure_
language SETL from New York University.

List and array comprehensions also appear in Id, which is an _impure_
language.

2) The translation in Bird and Wadler (page 63-64) is given purely for
illustrative purposes, and was never claimed to be the way to
implement them efficiently. It's simply meant to build an
intuitive connection between list comprehensions and maps and filters.

A better, more efficiecy-motivated, translation is given (by
Wadler) in Peyton Jones' book (Ch 7). It is optimal in the sense
that it does not cons unnecessarily. Even better translations
exist in existing compilers using just loops.

So, to summarize: there's nothing inefficient per se about list and
array comprehensions, and the notation has no specific connection to
lazy languages or to Haskell.

Nikhil