### Re: re. Arrays and Assoc

```

Thomas Johnsson says:

If I recall correctly, the := to be used in array comprehensions was a
consession to the FORTRAN/Id/Sisal community, so that array comprehensions
would look more like they were used to.

Both Arvind and I think this is notation is awful, and I don't recall
either of us ASKING for it, so this was probably someone else's idea
of a ``concession'' to the Id community!

Nikhil

Oh. My apologies to the Id community.
-- Thomas

```

### Re: Arrays and Assoc

```

Let me just remind people what the LML arrays does:

example:
lmlarray 1 3 f list =
array [ 1:= f [ x | (1,x) - list],
2:= f [ x | (2,x) - list],
3:= f [ x | (3,x) - list]
]
where array is like the ordinary Haskell array constructor function.
...
It seems to me that it is a bit more general to apply f to the entire
list accumulated at each index, rather than as an operator for foldr.

If you want the list you can supply (:) and []. If not, you supply the
operations, .[ ]

This is of course a matter of taste, but I think that in some cases it is a
bit clumsier:

lmlarray l u (take 2) list

does seem simpler than, say

amap (take 2) (lmlarray' l u (:) list).

(I don't know how to express  take 2  as an operator for foldr).
Also, in LML there is only one array constructor function, lmlarray
(simply called array in LML), so an 'ordinary' array is obtained by

lmlarray l u (\[ x ].x) list

(LML has . instead of - ).  Note that the pattern [ x ] in the function
forces the evaluation of the entire list and its indices, because,
intuitively, it has to be checked that there is no more than one element for
each index.

and the intermediate list never gets built.

Yes, there is that.
-- Thomas

```

### Re: Arrays and Assoc

```

I agree, but I also agree with Lennart that both sorts of arrays are needed.

Yes, I agree on that; language design is, as always, a compromise
between the desirable semantics (in this case, as lazy as possible),
and desirable efficency, and we don't know yet how to make lazy arrays
a la LML arrays as (potentially) efficient as current Haskell accumArray.

So here is a concrete suggestion:

1) Keep accumarray as it is (but like foldr-like behaviour instead of
foldl).

2) Add one more function to the prelude (or a standard module,
to be imported explicitly):

filterArray f z b list =
array b [ i := foldr f z [ x | j - indices b, i==j ]
| i - indices b
]

The only difference between assocArray and filterArray would be
that filterArray is lazy and ignores indices out of bound.

Another possibility would be to have only one, the lazy one,
and to use strictness annotations when the extra efficiency is desired;
but there seems to be a consensus against strictness annotations
But maybe the distaste is only for annotated *constructors* ?

-- Thomas

```

### re. Arrays and Assoc

```

Thomas Johnsson says:

If I recall correctly, the := to be used in array comprehensions was a
consession to the FORTRAN/Id/Sisal community, so that array comprehensions
would look more like they were used to.

Both Arvind and I think this is notation is awful, and I don't recall
either of us ASKING for it, so this was probably someone else's idea
of a ``concession'' to the Id community!

Nikhil

```

### Re: Arrays and Assoc

```

1. We should get rid of Assoc.
I agree wholeheartedly!  Do we have tp consider backwards
compat?

2. Arrays should be lazier.
I agree again.  But I think both kinds should be provided.

3. AccumArray should mimic foldr, not foldl.
Right!

-- Lennart

```

### Re: re. Arrays and Assoc

```

Nikhil says,

| Thomas Johnsson says:
|
| If I recall correctly, the := to be used in array comprehensions was a
| consession to the FORTRAN/Id/Sisal community, so that array comprehensions
| would look more like they were used to.
|
| Both Arvind and I think this is notation is awful, and I don't recall
| either of us ASKING for it, so this was probably someone else's idea
| of a ``concession'' to the Id community!
|
| Nikhil

All right!  I'm sorry!  ;-)

As I recall, Nikhil is right that neither he nor Arvind asked for this.
Some scientific programmers of my acquaintance did, though.  Id uses
= for this purpose, together with square brackets around the index.
This, of course, was not possible for Haskell.  The motivation was not
so much a "concession" to the Id community, as a concern for the

[((i,j), (f i j, g i j)) |

versus

[(i,j) := (f i j, g i j) |

or Id's

{matrix (1,N),(1,N) | [i,j] = (f i j, g i j) ||

(if I have that somewhere close to right).  The use of := for pairing
(or if you like, binding, or single-assignment) rather that assignment
did have a precedent in Val and Sisal.

All this syntax may seem of little consequence now, but at the time,
there was a genuine concern about the unpalatability of some choices
of syntax to a large community of programmers.

--Joe

```

### Re: Arrays and Assoc

```

John Launchbury says:
1. We should get rid of Assoc.

When explaining my programs to other people I find this is a point of
confusion. Imagine exaplaining array construction, "When I define an array,
the comprehension produces a list of index/value pairs, only they are not
written as pairs--these's this special type called Assoc. Oh, and don't be
confused by :=. That's not assignment. It is an infix pairing operator."
All of this is entirely unnecessary. Pairs have been used in maths for
decades to represent exactly this sort of thing. I simply do not believe
that [Assoc a b] provides me with any better information than [(a,b)].
Worse, I often find myself having to redefine standard pair functions on
elements of Assoc.

I agree.
If I recall correctly, the := to be used in array comprehensions was a
consession to the FORTRAN/Id/Sisal community, so that array comprehensions
would look more like they were used to.
But := is a bit unintuitive if you're thinking e.g. FORTRAN:
a = array[1 := 2, 2 := 4]
does *not* mean 1 is assigned to 2, etc!

But I think we can have the cake and eat it too, if we get rid of the
restriction (which I never liked) that operators beginning with : must be a
constructor: just define
a := b = (a,b)

[ While I'm at it: we should also get rid of the lower/uppercase
restrictions on constructor/nonconstructor names.
]

2. Arrays should be lazier.

I'm expecting Lennart to agree with me here as LML has the Right Thing. I
am convinced that there is no semantic problem with this, and I think that
even Simon isn't horrified at the implementation implications. The ability
to define arrays by self reference is just as important as it is for lists.

I'm not exactly sure what you mean here. It is allready possible to define

I am assuming that the fact that lazy indexes provide a better match with
laziness elsewhere is clear, but I am willing to expand on this point if
someone wants.

3. AccumArray should mimic foldr, not foldl.

This is tied up with the last point. The only advantage I can see with the
present scheme would be if the array element could be used as the
accumulator while the array was under construction. However, as arrays are
non-strict in their *elements* this seems to be of no benefit. It seems to
me highly sensible that the structure of the computation at each point
should reflect the structure of the input sequence (i.e. the elements are
in the same order). Furthermore, if a lazy operation is used (such as (:))
then the result becomes available early (assuming point 2. above).

Again I wholeheartedly agree.
Let me just remind people what the LML arrays does:

example:
lmlarray 1 3 f list =
array [ 1:= f [ x | (1,x) - list],
2:= f [ x | (2,x) - list],
3:= f [ x | (3,x) - list]
]
where array is like the ordinary Haskell array constructor function.
In the implementation, the filtering needs to be done only once
and not n times, where n is the size of the array.
[ If anyone wants to know how this is done, I could expand on this. ]

It seems to me that it is a bit more general to apply f to the entire
list accumulated at each index, rather than as an operator for foldr.

-- Thomas

```

### Re: Arrays and Assoc

```

John Launchbury says,
| Here are three comments directed particularly at Haskell 1.3 people, but
| obviously open to general feedback.
|
| 1. We should get rid of Assoc.
|
| When explaining my programs to other people I find this is a point of
| confusion. Imagine exaplaining array construction, "When I define an array,
| the comprehension produces a list of index/value pairs, only they are not
| written as pairs--these's this special type called Assoc. Oh, and don't be
| confused by :=. That's not assignment. It is an infix pairing operator."
| All of this is entirely unnecessary. Pairs have been used in maths for
| decades to represent exactly this sort of thing. I simply do not believe
| that [Assoc a b] provides me with any better information than [(a,b)].
| Worse, I often find myself having to redefine standard pair functions on
| elements of Assoc.

Mea maxima culpa.  I must admit that the reason for introducing Assoc
was syntactic.  Making a semantic distinction between pairs and assocs
for a syntactic purpose should have set off alarms; somehow, I managed
to ignore them.

At the time this decision was made, arrays and array syntax were something
of a contentious issue.  Even the use of infix ! for indexing was a
source of anguish for potential users of arrays, and the fear was that
pair syntax in "array comprehensions" would be unwieldy, particularly
for multidimensional arrays.  Consider a matrix of pairs (a typical
construction in scientific mesh algorithms).

problem.  Thomas suggests that we could drop the syntactic restrictions
on constructor and nonconstructor symbols and define (:=) as a pairing
function.  That almost does the job, but there are some programs that
pattern-match Assocs.  Also, I think there will be objection in some
quarters to dropping the separation of name spaces.  Here are two more
possibilities:

2.  Provide a way to declare synonyms for constructors, and
use it to equate := with (,).

3.  Don't provide such a general facility, but hack in :=
as a special case (rather like prefix minus).

| 2. Arrays should be lazier.
|
| I'm expecting Lennart to agree with me here as LML has the Right Thing. I
| am convinced that there is no semantic problem with this, and I think that
| even Simon isn't horrified at the implementation implications. The ability
| to define arrays by self reference is just as important as it is for lists.
| I am assuming that the fact that lazy indexes provide a better match with
| laziness elsewhere is clear, but I am willing to expand on this point if
| someone wants.

I agree, but I also agree with Lennart that both sorts of arrays are needed.
too many scientific programs couldn't live without them (or else effects).
Pragmatically, the accumulations in these programs were almost always
sums.  (histogramming, Monte Carlo tallying)  People needed to be convinced
that this could be done efficiently.

| 3. AccumArray should mimic foldr, not foldl.
|
| This is tied up with the last point. The only advantage I can see with the
| present scheme would be if the array element could be used as the
| accumulator while the array was under construction. However, as arrays are
| non-strict in their *elements* this seems to be of no benefit. It seems to
| me highly sensible that the structure of the computation at each point
| should reflect the structure of the input sequence (i.e. the elements are
| in the same order). Furthermore, if a lazy operation is used (such as (:))
| then the result becomes available early (assuming point 2. above).
|
| John.
|

Agreed again.  The historical reason for the choice of foldl should be
evident from the remarks above.

Since all of these decisions had to do with Id arrays, I'm pleased
to hear from Nikhil that pH people are thinking along the same lines
as John and Lennart.  Consensus!

--Joe

```

### Re: Arrays and Assoc

```

But I think we can have the cake and eat it too, if we get rid of the
restriction (which I never liked) that operators beginning with : must be a
constructor: just define
a := b = (a,b)

Unfortunately that won't work if := had been used in patterns. I think
backward compatibility is an issue. The standard technique of supporting
Assoc but with compiler warnings will probably have to be used.

---

I'm not exactly sure what you mean here. It is allready possible to define

Haskell arrays are strict in the indices. That is, the whole of the
defining list is consumed and the indices examined before the array becomes
available. Thus, a recursive array definition in which the *index
calculation* depends on the earlier part of the array gives bottom. The
current definition allows for a recursive definition so long as it is only
the values of the array elements which depend on the array. This is not
always sufficient.

---

Let me just remind people what the LML arrays does:

example:
lmlarray 1 3 f list =
array [ 1:= f [ x | (1,x) - list],
2:= f [ x | (2,x) - list],
3:= f [ x | (3,x) - list]
]
where array is like the ordinary Haskell array constructor function.
...
It seems to me that it is a bit more general to apply f to the entire
list accumulated at each index, rather than as an operator for foldr.

If you want the list you can supply (:) and []. If not, you supply the
operations, and the intermediate list never gets built.

John.

```

### Arrays and Assoc

```

John Launchbury makes the suggestion, inter alia, that Haskell 1.3
`should get rid of Assoc.'

Reading some of the followup messages, I see that there is some
division on this point.  Those closer to the scientific applications
community, such as Nikhil and Joe Fasel's acquaintances, seem to be
warmed by the familiar sight of `:=', whereas the more
pure-mathematically motivated commentators seem to find the (assuredly
equivalent) pair constructor more congenial.

John's suggestion will definitely stop old code dead in its tracks
(namely, in the type-checker).

Clearly, what's needed to satisfy all parties and make Haskell 1.3 the
rousing success that it deserves to be is to introduce a class
`Associator' with methods `key', `image', `associate', `toPair',
`toAssoc'.  Then the array prelude functions could be redefined in
terms of the class by (1) pattern-matching on `toAssoc assoc' instead
of `assoc' for each variable assoc :: Assoc, and (2) replacing
explicit applications of the constructor `:=' by `associate'.  I don't
think user code would have to change, but users might wonder about the
new inferred type constraints on their array code.

Of course, to recover efficiency, all Haskell implementors will have
to treat the class `Associator' specially so that no dictionary usage
is actually produced (as long as the users haven't perversely
introduced their own instances, which suggests some wondrous new
interpretations of the concept `array').

I intended this message to be humorous when I started, but I'm
beginning to think this is a reasonable approach to such matters.  So
let's generalize with wild abandon: what would be the consequences of
automatically deriving an class abstraction for _every_ Haskell data
type?  Even function types are eligible via the abstract operation
`apply'.  What new vistas now unfold?

-
Dan Rabin   I must Create a System
Department of Computer Scienceor be enslav'd by another Man's.
P.O. Box 208285 I will not Reason  Compare:
New Haven, CT 06520-8285  my business is to Create.

[EMAIL PROTECTED] -- William Blake, `Jerusalem'
-

```