Get the middle of an Ix range in O(1) time in Haskell

Question

I was playing around with this code kata in Haskell, and I came across the question in the topic.

It's trivial to find the midpoint of an array whose indexes are a single numerical value, but Haskell's array indexes can be any instance of the Ix typeclass, including, for example, the tuple (Int, Word, Card) where card is an instance of Ix but not of Num.

One way to get the midpoint of the array is to query its length, query the list of indexes, and drop half that list, but this requires O(n) time.

Does anyone know of a way to index to do it in constant time? I feel like there should be one, since an Ix range is supposed to biject with an integer range.

Answer 1

Ix typeclass requires only injection from values of type i to that of Int. index together with range can give us inverse mapping:

index' :: (Ix i) => (i, i) -> Int -> i
index' b x = range b ! x

As you can see index' evaluates at least in linear time. Also we can't have an idea of how long range b works. It is evaluated in the way that user has defined in instance definition. So the optimization needed in your case (get midpoint of an array) can take place if and only if we have some kind of index' that works in constant time. As Ix typeclass doesn't give us constant time mapping from Int to i, we should ask user for that. Consider next code:

midpoint :: (Ix j) => (Int -> j) -> Array j e -> e
midpoint f a = a ! f middle
               where middle = rangeSize (bounds a) `div` 2

Now complexity of taking midpoint of array depends on complexity of user-defined f. So if values of our index type i can be in constant time evaluated from Int values and vice versa -- we get midpoint in constant time.

Also consider ixmap function from Data.Ix:

ixmap :: (Ix i, Ix j) => (i, i) -> (i -> j) -> Array j e -> Array i e