STUArrays for Pairs

Manuel M T Chakravarty
Wed, 31 Jul 2002 17:51:00 +1000 (EST)

Hal Daume III <hdaume@ISI.EDU> wrote,

> it seems to me that if you have
>   instance MArray (STUArray s) a (ST s)
> and
>   instance MArray (STUArray s) b (ST s)
> you should be able to have
>   instance MArray (STUArray s) (a,b) (ST s)
> by simply keeping two arrays with identical bounds, one holding as and one
> holding bs, and then when you lookup, you lookup in each individually and
> pair.
> i'd like to write such an instance, but have no idea where to start...any
> pointers?

It's a little bit more difficult, but possible.  Have a look

I have put a "sneak preview" of our new array library up
there.  It shows how to do something as what you attempt
above with STUArray (and more).

What you need is some sort of generic programming or
intensional type analysis (or however you want to call it).
The paper
  [Ralf Hinze, Johan Jeuring, and Andres Loeh. "Type-indexed datatypes"]

describes how to define type-indexed data types using type
classes and
  [Manuel M. T. Chakravarty and Gabriele Keller, "More Types
  for Nested Data Parallel Programming"]

among other things introduces the idea of regarding
polymorphic arrays as a type-indexed data type.

If you want to see how to express this all using intensional
type analysis, have a look at
  [Robert Harper and Greg Morrisett. "Compiling Polymorphism
  Using Intensional Type Analysis"]

They are also using the example of flattening an array of
pairs into a pair of arrays.