STUArrays for Pairs

[Manuel M T Chakravarty]

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
at

  http://www.cse.unsw.edu.au/~chak/nepal/#software

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 

  http://www.cs.uu.nl/~johanj/publications/tidata.pdf
  [Ralf Hinze, Johan Jeuring, and Andres Loeh. "Type-indexed datatypes"]

describes how to define type-indexed data types using type
classes and 

  http://www.cse.unsw.edu.au/~chak/papers/CK00.html
  [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

  http://citeseer.nj.nec.com/harper95compiling.html
  [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.

Cheers,
Manuel