Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!cica!iuvax!silver!jashley
From: jashley@silver.ucs.indiana.edu (J. Michael Ashley)
Newsgroups: comp.lang.functional
Subject: Id array comprehensions revisited
Keywords: Id, Haskell, poor array comprehensions
Message-ID: <51123@iuvax.cs.indiana.edu>
Date: 17 Jul 90 00:49:54 GMT
Sender: news@iuvax.cs.indiana.edu
Reply-To: jashley@silver.ucs.indiana.edu (J. Michael Ashley)
Organization: Graceland
Lines: 48

A little while ago I asked why array comprehensions are not parallel.  In
particular, why does an array comprehension like this:

	{ array (1, n) | [i] = f i || i <- 1 to n }

not evaluate the (f i)'s concurrently?  Well, it turns out that the i's get
generated sequentially as a list (a list in the data structure sense, mind
you).

But there's no reason why we have to confine ourselves to using this "1 to n"
construct to generate the indices.  In fact, we can use any function we like
to generate the indices.  For example, we can rewrite the above expression as

	{ array (1, n) | [i] = f i || i <- gen 1 n }

where gen is some generator of our own creation.  But what are we going to
create?  We'd like to write something better than the O(n) generator that the
"1 to n" represents.  Unfortunately, I haven't been able to uncover a
O(1) or even O(log n) algorithm.  The difficulty is that the append
function is O(m), where m is the length of the first argument, so the best
I've been able to do is O(m).  This is no good.

Thorsten von Eiken suggested the following trick.  Instead of using one
generator to create the indices, use two!  I'm ignoring the bounds problem,
but this is the idea:

	{ array (1, n) | [i] = f i || j <- 1 to n by 8 &
                                      i <- j to j+7      }

The best you can hope for with this method is O(sqrt n) where n is the
length of the array.  You can use more generators to get O(cubert n), etc...
This is a nice solution, and I don't think you can do much better without
resorting to non-functional constructs (the "make_1d_i_array" function in Id).

Though this is a nice solution, it is still a trick, and I'm not very fond
of tricks.  It seems that the root of the problem is that the generator
produces a *list* of indices.  I say this is the problem because building
a list is an O(n) job and referencing the list is an O(n) job.  A list
is the wrong data structure.

Can anybody else suggest a better definition for array comprehensions?  What
about a "set" as a new data structure?

By the way, array comprehensions are a feature of Haskell, which is
suppossed to be the new standard.  So this question is very relevent!

mike ashley 
jashley@lanl.gov