Grałem z kataami this w Haskell i natknąłem się na pytanie w temacie.Zdobądź środek zakresu Ix w czasie O (1) w Haskell
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.
Jeśli rzeczywiście istnieje bijekcją, to dlaczego nie mapować do liczb, obliczania punktu środkowego, a następnie podjąć odwrotność mapować go z powrotem do indeksu ? Nie mam pojęcia, jaki mechanizm pozwoliłby na to w Haskell, ale wydaje się to możliwe? – Gian
Funkcja 'index' w klasie' Ix' jest jedną z części bijectionu, mapującą indeksy na liczby całkowite, ale druga z nich jest niedostępna, o ile wiem. – yatima2975