Получите середину диапазона Ix за O (1) раз в Haskell - PullRequest
Новая
       22

Получите середину диапазона Ix за O (1) раз в Haskell

5 голосов
/ 08 сентября 2010

Я играл с этим кодом ката в Haskell, и я натолкнулся на вопрос в теме.

Тривиально найти середину массива, индексы которого являются единичнымичисловое значение, но индексы массива Haskell могут быть любым экземпляром класса типов Ix, включая, например, кортеж (Int, Word, Card), где card является экземпляром Ix, но не Num.

В одну сторонуполучить среднюю точку массива - запросить его длину, запросить список индексов и отбросить половину этого списка, но для этого требуется время O (n).

Кто-нибудь знает, как выполнить индексирование?это в постоянное время?Я чувствую, что он должен быть, так как диапазон Ix должен делиться на целочисленный диапазон.

1 Ответ

4 голосов
/ 08 сентября 2010

Ix Класс типов требует внедрения только значений типа i и Int. index вместе с range может дать нам обратное отображение: 

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

Как видите, index' оценивает по крайней мере в линейном времени. Также мы не можем иметь представление о том, как долго работает range b. Он оценивается способом, который пользователь определил в определении экземпляра. Таким образом, оптимизация, необходимая в вашем случае (получение средней точки массива), может иметь место, если и только если у нас есть какой-то index', который работает в постоянном времени. Так как класс типов Ix не дает нам постоянное отображение времени от Int до i, мы должны попросить об этом пользователя. Рассмотрим следующий код: 

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

Теперь сложность получения средней точки массива зависит от сложности пользовательской f. Таким образом, если значения нашего типа индекса i могут быть в постоянном времени оценены из Int значений и наоборот - мы получаем среднюю точку в постоянном времени.

Также рассмотрим функцию ixmap от Data.Ix: 

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