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

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.

5
задан Alex R 8 September 2010 в 14:22
поделиться