Holen Sie sich die Mitte eines Ix-Bereich in O (1) Zeit in Haskell

Question

Ich spielte mit this Code Kata in Haskell, und ich stieß auf die Frage in dem Thema.

Es ist trivial, den Mittelpunkt eines Arrays zu finden, dessen Indizes ein einzelner numerischer Wert sind, aber Haskells Array-Indizes können jede Instanz der Ix-Typklasse sein, z. B. das Tupel (Int, Word, Card) ist eine Instanz von Ix, aber nicht von Num.

Eine Möglichkeit, den Mittelpunkt des Arrays zu erhalten, besteht darin, seine Länge abzufragen, die Liste der Indizes abzufragen und die Hälfte dieser Liste zu löschen, aber dies erfordert O (n) Zeit.

Kennt jemand eine Möglichkeit zu indizieren, um es in konstanter Zeit zu tun? Ich habe das Gefühl, dass es einen geben sollte, da ein Ix-Bereich mit einem ganzzahligen Bereich bijizieren soll.

Answer 1

Ix typeclass erfordert nur eine Injektion von Werten des Typs i zu der von Int. index zusammen mit range können uns inverse Abbildung geben:

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

Wie Sie index' wertet zumindest in linearer Zeit sehen können. Wir können uns auch nicht vorstellen, wie lange range b funktioniert. Es wird auf die Weise ausgewertet, die der Benutzer in der Instanzdefinition definiert hat. Die Optimierung, die in Ihrem Fall benötigt wird (Mittelpunkt des Arrays erhalten), kann genau dann stattfinden, wenn wir eine Art von index' haben, die in konstanter Zeit arbeitet. Da Ix typeclass uns keine konstante Zeitabbildung von Int bis i gibt, sollten wir den Benutzer danach fragen. Man betrachte als nächstes Code:

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

Jetzt Komplexität der Mittelpunkt des Arrays nimmt, hängt von der Komplexität von benutzerdefinierten f. Also wenn Werte unseres Indextyps i in konstanten Zeitwerten sein können, ausgewertet von Int Werten und umgekehrt - wir bekommen den Mittelpunkt in konstanter Zeit.

Sehen Sie sich auch ixmap Funktion von Data.Ix:

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