Plus ca change...
I advocated overloaded array operations in similar manner some years
back among pH enthusiasts---this being years before functional
dependencies, though, the multiparameter type classes worked only in
the pH compiler. :-) (I recall audible complaints from Simon P-J among
others...) Producing a full implementation has been on my to-do list
(down near the bottom, alas) since 1994 or so. This may save me the
effort, and GHC is really a better platform for getting this into the
hands of the community. Plus, I'd love for GHC to have a system of
arrays I can actually wrap my mind around.
* A plea: please don't overload our names
An impassioned plea, though: Please don't call them IArray and MArray!
I have a vague suspicion that they're called that by analogy to the Id
and pH data structures of the same name (the MVars seen in
Concurrent). We already have types called IArray and MArray. Their
semantics aren't at all the same as the ones given.
I'd actually name IArray as FArray (for "functional array" or even
"frozen array") as no in-place update is really possible. The "I" in
IArray actually stood for "Imperative" back in the mists of time, I
think, and this class is anything but.
As for naming MArray, this namespace is already rather cluttered with
the several skillion array types and names (which of course was the
point of the proposal). I haven't committed enough of them to memory
to be certain which terminology is available... So I'll leave my plea
out here and hope someone can come up with a reasonable alternative
name.
* Indexing?
One of the more controversial bits of my multiparameter array
experiment was the desire to also overload indexing, so that we could
capture array-like operations which had a fixed index type. The most
notable examples of this are the vector types we use to implement
arrays, which have a fixed index type of Int and don't support
creation with arbitrary bounds (they're zero-indexed). Arguably we
could also extend indexing to map types as well under this scheme.
The other controversial bit was a similar attempt to capture datatype
dependencies. This is mostly useful for arrays of unboxed or
specialized type (bit vectors / sets); I suspect the restrictions on
polymorphism over unboxed types means these'd mostly be useful for
operations which re-boxed the fetched type. In any case, I don't
recall ever making this work even in the much-hacked pH type checker.
I mention this because it sounds like generalized indexing might be
the sort of thing Chris Okasaki et al are looking for. The danger, of
course, is that everyone starts using GHC-specific vector types for
all their 1-D array needs, thus badly fragmenting the language. Some
might argue this has already happened with GHC's thousand arrays and
an Array.
-Jan-Willem Maessen
[EMAIL PROTECTED]
To give a flavor, my proposal went something like this:
>class Indexed a i e where
> (!) :: a -> i -> e
The fact that a isn't parameterized wrt i or e here was cause for
some controversy---having everything depend on a is probably the
correct answer, but I haven't played with functional dependencies
enough yet to guess if that will get existing programs through
the type checker
>class ArrayLike a i e where
> array :: (i,i) -> [(i,e)] -> a
> (//) :: a -> [(i,e)] -> a
Our notion is that (//) gets deforested and thus single update is
very very cheap. array would reject illegal bounds tuples.
>class WriteArray a i e m where
> (//=) :: a -> [(i,e)] -> m a
Again, we include bulk "parallel" update (it made sense for us,
anyone else might want single update). Single update? It'll
deforest. And of course we didn't care about ordered reads at the
time (though I do now).
With hindsight, this proposal was too radical. But I think some of
the ideas I was trying to capture might be worth a visit---
particularly capturing the behavior of underlying vector types and
specialized-element array types in a neat way. Something to think
about for the future.
