Slicing an IOArray (or MArray in general)

Question

Is there a way how efficiently to construct a slice (a sub-array view) out of an IOArray, or MArray in general? That is, taking the same array, just restricting the bounds. The signature could be

(MArray a e m, Ix i) => a i e -> i -> i -> m (a i e)

For example, taking an array with bounds (1,1000) and making a view that gives access only to elements with bounds (500,700) of the original array. I searched the documentation but I couldn't find any such function.

Answer 1

Given how the array types are implemented, this isn't something that would really be a feature of an array, which is probably why nothing along these lines exists already.

Recall that an array is a contiguous block of memory, so at some level every array with n elements has bounds (0, n-1). However, wanting indices other than integers starting from zero is common enough that Haskell provides a type class for defining arbitrary bounds and translating from an element inside those bounds to a 0-based integer index for the actual block of memory.

This causes some difficulty for what you want to do because it's assumed that the bounds for an array cover its entire range. So if you were to simply create a copy of an existing array that used the same memory chunk but different bounds, the indices would not line up--in your example, index 500 in the subarray would be the same as index 1 in the original array. Not helpful.

The simplest approach here would be to define your own array type that wraps an existing array and stores any extra information needed to translate indices, so that it reports its own bounds as the smaller range, but looks things up in the wrapped array based on the full range. You can then use the wrapped array type everywhere (and give it all the expected instances, &c.) with newly-created arrays simply using the same bounds as the "real" array. You can perform whatever translations you need on the indices here, so this approach should generalize to index types that don't have a linear order as well (e.g., "multi-dimensional" arrays indexed by tuples).

You could probably also do something involving a wrapper around your index type and giving the wrapper version a weird Ix instance that translated things automatically somehow, which would let you use the existing array types. That would probably be trickier to make work correctly, though.

I don't think there's any way to do it without changing either the array or index types.