Ken Sailor writes
| Reginald Meeson writes
|
| > Interesting discussion, but it seems to me that Haskell already
| > provides the best of both worlds, namely
|
| > a. Efficient implementation of arrays as data objects, with indexing
| > as a projection function; and
|
| (Actually, efficient seems a little hopeful here).
Agreed, although any reasonable implementation should at least be able to
provide o(1) indexing.
| Rats, my Haskell manual is home, so correct me if the following
| is wrong... Actually, let me pose this as a question (then I
| don't have to get so embarrassed later!)
|
| Let's say I have an array arr and at some index i I want to update
| it to be x. That is, I want to define
|
| upd arr i x
|
| to return a new array equal to arr everywhere except i where the
| value of the result is x. It seems to me that there is no
| way to write this function without decomposing arr into a list
| and rebuilding an array. Am I right? (I will be pleased to be wrong!)
Wrong! :-) (or maybe half-right)
Incremental update is provided, your example being written arr//[i:=x] .
The Standard Prelude does define (//) in more or less the terms you
describe above, but note the comment at the beginning of PreludeArray,
which can be paraphrased, "Dont't even _think_ about actually implementing
arrays this way." The expectation is that a compiler that is serious
about array performance will do something more clever, such as static
sharing analysis for update-in-place and/or dynamic techniques like
version arrays.
| >From the APL/Nial/Array Theory world, it is a travesty to be forced
| to perform such a decomposition. There are enough optimization problems
| without mixing lists into it.
I, for one, would be very interested in seeing APL/Nial/Array-Theory
ideas considered for incorporation in some future version of Haskell.
(We haven't been talking about Haskell 2 much lately.)
| This, of course, is not to say that it is not convenient or perhaps
| necessary to be able to convert lists into arrays. It is very convenient
| for monolithic array operations, such as building tables for lookup
| functions, etc, but it also seems like there ought to be some kind
| of support for incremental array operations, like update.
|
| Dave Barton writes:
|
| > I am interested in how the lack of a distinction gets in the way of
| > your reading and understanding programs, however.
|
| (where the distinction is between arrays as rules and arrays
| as general functions).
This may be painfully obvious, as well as syntactic and superficial,
but since nobdoy's mentioned it up to now: If you want to treat
an array a as a function, just use (a!) , e.g., f . (a!) . g
| My apologies for not being more sensitive to your application
| before my first response. I have an interest in the
| optimization of incremental array operations (see above) and
| don't tend to think of arrays as fixed tables.
|
| The first area that pops into mind where I am more comfortable
| with having the distinction is graph theory. Now perhaps
| it has something to do with the way it was taught to me, but
| I like thinking of the arrays as data objects rather than functions,
| and it helps me in thinking about what an algorithm is doing and
| how much the algorithm costs.
This, indeed, is the attitude toward arrays taken by the Haskell
committee. At the beginning of the Report section on arrays, we
say that although in the abstract arrays should be regarded as
functions, there are pragmatic reasons for treating them as data.
| On the other hand, I am not sure how important this is or how
| long it would take me to forget or drop my dependence on the
| distinction.
|
| Ken
The opinion prevailing at the time we decided to distinguish array
indexing syntactically from function application was that it would
be difficult in general for a compiler to generate efficient code
for an array access without the distinction.
--Joe
