Obtener el centro de un rango Ix en O (1) tiempo en Haskell

Question

Estaba jugando con this código kata en Haskell, y me encontré con la pregunta en el tema.

Es trivial encontrar el punto medio de una matriz cuyos índices son un único valor numérico, pero los índices de matriz de Haskell pueden ser cualquier instancia de la clase de tipo Ix, incluida, por ejemplo, la tupla (Int, Word, Card) donde la tarjeta es una instancia de Ix pero no de Num.

Una forma de obtener el punto medio de la matriz es consultar su longitud, consultar la lista de índices y soltar la mitad de esa lista, pero esto requiere O (n) tiempo.

¿Alguien sabe de una manera de indexar para hacerlo en tiempo constante? Siento que debería haber uno, ya que se supone que un rango Ix debe biject con un rango entero.

Answer 1

Ix typeclass requiere solo la inyección desde los valores del tipo i al de Int. index junto con range nos puede dar aplicación inversa:

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

Como se puede ver index' evalúa al menos en el tiempo lineal. Tampoco podemos tener una idea de cuánto tiempo funciona range b. Se evalúa de la manera que el usuario definió en la definición de la instancia. Por lo tanto, la optimización necesaria en su caso (obtener el punto medio de una matriz) puede tener lugar si y solo si tenemos algún tipo de index' que funcione en tiempo constante. Como Ix typeclass no nos da el mapeo de tiempo constante de Int a i, debemos preguntar al usuario por eso. Considere código siguiente:

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

Ahora complejidad de tomar el punto medio de la matriz depende de la complejidad de f definida por el usuario. Entonces, si los valores de nuestro índice tipo i se pueden evaluar en tiempo constante a partir de los valores Int y viceversa, obtenemos un punto medio en tiempo constante.

Considera también ixmap función de Data.Ix:

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