Obtenir le milieu d'une gamme Ix en O (1) temps dans Haskell

Question

Je jouais avec this code kata dans Haskell, et je suis tombé sur la question dans le sujet.

Il est trivial de trouver le point médian d'un tableau dont les index sont une seule valeur numérique, mais les index de tableau de Haskell peuvent être n'importe quelle instance de la classe Ix, y compris, par exemple, le tuple (Int, Word, Card) est une instance de Ix mais pas de Num. Une façon d'obtenir le point médian du tableau consiste à interroger sa longueur, interroger la liste des index et supprimer la moitié de cette liste, mais cela nécessite un temps O (n).

Est-ce que quelqu'un connaît un moyen d'indexer pour le faire en temps constant? Je pense qu'il devrait y en avoir un, car une plage Ix est supposée bijecter avec une plage entière. Le type de classe

Answer 1

Ix nécessite uniquement l'injection des valeurs de type i à celle de Int. index avec range peut nous donner la cartographie inverse:

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

Comme vous pouvez le voir au moins index' évalue en temps linéaire. Aussi, nous ne pouvons pas avoir une idée de combien de temps range b fonctionne. Il est évalué de la manière définie par l'utilisateur dans la définition d'instance. Donc, l'optimisation nécessaire dans votre cas (obtenir le point milieu d'un tableau) peut avoir lieu si et seulement si nous avons une sorte de index' qui fonctionne à temps constant. Comme Ix typeclass ne nous donne pas le mappage de temps constant de Int à i, nous devrions demander à l'utilisateur pour cela. Considérez le code suivant:

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

Maintenant, la complexité de la prise milieu du tableau dépend de la complexité de défini par l'utilisateur f. Donc, si les valeurs de notre type d'index i peuvent être en temps constant évalué à partir de Int valeurs et vice versa - nous obtenons le point milieu à temps constant.

Voir également la fonction ixmap de Data.Ix:

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