When (ab)using them for this purpose, SmallArrayArray's would be very handy as well.
Consider right now if I have something like an order-maintenance structure I have:
data Upper s = Upper {-# UNPACK #-} !(MutableByteArray s) {-# UNPACK #-} !(MutVar s (Upper s)) {-# UNPACK #-} !(MutVar s (Upper s))
data Lower s = Lower {-# UNPACK #-} !(MutVar s (Upper s)) {-# UNPACK #-} !(MutableByteArray s) {-# UNPACK #-} !(MutVar s (Lower s)) {-# UNPACK #-} !(MutVar s (Lower s))
The former contains, logically, a mutable integer and two pointers, one for forward and one for backwards. The latter is basically the same thing with a mutable reference up pointing at the structure above.
On the heap this is an object that points to a structure for the bytearray, and points to another structure for each mutvar which each point to the other 'Upper' structure. So there is a level of indirection smeared over everything.
So this is a pair of doubly linked lists with an upward link from the structure below to the structure above.
Converted into ArrayArray#s I'd get
data Upper s = Upper (MutableArrayArray# s)
w/ the first slot being a pointer to a MutableByteArray#, and the next 2 slots pointing to the previous and next previous objects, represented just as their MutableArrayArray#s. I can use sameMutableArrayArray# on these for object identity, which lets me check for the ends of the lists by tying things back on themselves.
and below that
data Lower s = Lower (MutableArrayArray# s)
is similar, with an extra MutableArrayArray slot pointing up to an upper structure.
I can then write a handful of combinators for getting out the slots in question, while it has gained a level of indirection between the wrapper to put it in * and the MutableArrayArray# s in #, that one can be basically erased by ghc.
Unlike before I don't have several separate objects on the heap for each thing. I only have 2 now. The MutableArrayArray# for the object itself, and the MutableByteArray# that it references to carry around the mutable int.
The only pain points are
1.) the aforementioned limitation that currently prevents me from stuffing normal boxed data through a SmallArray or Array into an ArrayArray leaving me in a little ghetto disconnected from the rest of Haskell,
and
2.) the lack of SmallArrayArray's, which could let us avoid the card marking overhead. These objects are all small, 3-4 pointers wide. Card marking doesn't help.
Alternately I could just try to do really evil things and convert the whole mess to SmallArrays and then figure out how to unsafeCoerce my way to glory, stuffing the #'d references to the other arrays directly into the SmallArray as slots, removing the limitation we see here by aping the MutableArrayArray# s API, but that gets really really dangerous!
I'm pretty much willing to sacrifice almost anything on the altar of speed here, but I'd like to be able to let the GC move them and collect them which rules out simpler Ptr and Addr based solutions.
-Edward