Zdobądź środek zakresu Ix w czasie O (1) w Haskell

Question

Grałem z kataami this w Haskell i natknąłem się na pytanie w temacie.

To jest banalne, aby znaleźć punkt środkowy tablicy, której indeksy są pojedynczą wartością liczbową, ale indeksy tablic Haskell mogą być dowolnymi instancjami kodu typu Ix, w tym na przykład krotką (Int, Word, Card), gdzie karta jest instancją Ix, ale nie Num.

Jednym ze sposobów uzyskania punktu środkowego tablicy jest zapytanie o jej długość, zapytanie o listę indeksów i upuszczenie połowy tej listy, ale wymaga to czasu O (n).

Czy ktoś wie o sposobie indeksowania, aby zrobić to w stałym czasie? Czuję, że powinien być jeden, ponieważ zakres Ix ma być ustawiony na zakres całkowity.

Answer 1

Ix typeclass wymaga tylko iniekcji od wartości typu i do tej z Int. index wraz z range może dać nam odwrotnego mapowania:

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

Jak widać index' ocenia przynajmniej w czasie liniowym. Również nie możemy mieć pojęcia, jak długo działa range b. Jest oceniany w sposób zdefiniowany przez użytkownika w definicji instancji. Optymalizacja potrzebna w twoim przypadku (uzyskać punkt środkowy tablicy) może mieć miejsce wtedy i tylko wtedy, gdy mamy jakiś rodzaj index', który działa w stałym czasie. Ponieważ typeclass Ix nie daje nam stałego mapowania czasu od Int do i, powinniśmy poprosić o to użytkownika. Rozważmy kolejny kod:

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

Teraz złożoność biorąc punkt środkowy tablicy zależy od złożoności zdefiniowany przez użytkownika f. Jeśli więc wartości naszego indeksu typu i mogą być w stałym czasie obliczane z wartości Int i vice versa - otrzymamy punkt środkowy w stałym czasie.

również pod ixmap funkcja z Data.Ix:

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