Hal Daume III 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