Если вы ищете списки пропусков, реализованные в Haskell, вы не найдете их много. Это вероятностная структура данных, требующая генератора случайных чисел, что означает, что любая из этих структур должна была бы работать в монаде IO.
Люди Хаскелла держатся подальше от этих структур данных, потому что их невозможно реализовать чисто? Как Хаскелл справляется с ними?
Генератор псевдослучайных чисел может, конечно, использоваться вне IO, просто сохраняя текущее значение генератора вместе с вероятностной чистой структурой данных и обновляя его при построении модифицированных версий. Недостатком этого является то, что PRNG будет более явно детерминированным, чем в нечистой программе, поскольку ничего за пределами единой структуры данных не будет обновлять его. Если только статистические свойства имеют значение, это не представляет проблемы, но может быть причиной для беспокойства.
С другой стороны, скрытие нечистого PRNG, возможно, является оправданным использованием unsafePerformIO, как в ответе Ganesh Sittampalam. Это нагло нарушает ссылочную прозрачность, но только в той степени, в которой PRNG вернет непредсказуемые, непоследовательные ценности - вот и все! Однако необходимо соблюдать осторожность, поскольку компилятор может сделать неправильные предположения о коде, потому что он выглядит чистым.
Но на самом деле ни один подход не является ужасно привлекательным. Использование unsafePerformIO является неудовлетворительным и потенциально опасным. Threading состояние PRNG прост, но налагает (потенциально ложные) строгие последовательности на любые вычисления, которые его используют. Ни безопасность, ни лень не легко освобождаются программистами Haskell (и это правильно!), И, конечно, структуры данных, ограниченные IO, имеют ограниченную полезность. Итак, чтобы ответить на часть вашего вопроса, почему программисты Haskell могут избежать таких структур.
Что касается "того, как Haskell может иметь дело с" такими вещами, я бы предположил, что это неправильный вопрос, чтобы спросить.
На самом деле, это то, что многие структуры данных и алгоритмы неявно предполагают (и оптимизируют) императивный, нечистый, строгий язык, и хотя это, безусловно, возможно реализовать в Haskell, это редко бывает желательным, потому что (даже игнорируя внутренняя реализация), используя их, накладывает на ваш код структуру и подход, который очень не идиоматичен. Кроме того, поскольку Haskell нарушает эти неявные предположения, производительность часто ухудшается (иногда это плохо).
Дело в том, что алгоритмы и структуры данных - это средство, а не конец. Редко бывает, что требуется отдельная конкретная реализация - требуется, как правило, определенные характеристики производительности. Поиск структур данных/алгоритмов, которые предлагают желаемые характеристики, а также идиоматический Haskell, почти всегда является лучшим планом и, скорее всего, будет лучше, чем пытаться втиснуть строгую настоятельную привязку в ленивую функциональную дыру.
Эта ошибка, пожалуй, наиболее часто встречается в подмножестве программистов, которые никогда не сталкивались с проблемой, которую они не могли решить с помощью хеш-таблицы, но привычку легко поддаваться многим из нас. Правильный подход заключается в прекращении мышления "как реализовать это решение в Haskell", но вместо этого "что является лучшим способом решить мою проблему в Haskell" . Вы можете быть удивлены, как часто ответы различаются; Я знаю, что часто бываю!
Списки пропусков могут быть реализованы чисто - просто инкапсулируйте текущее семя в состояние самого списка пропусков.
data SkipList a = SkipList StdGen (Node a)
data Node a = ...
Это может привести к атакам с некоторой степенью сложности, которые не являются практическими против "реальных" списков пропусков, поскольку вы можете исследовать вырожденные заказы на вставку и повторять атаки против одного и того же семени, но это позволяет вам извлекать выгоду из структуры, когда состязательное использование не является проблемой.
Вы также можете откинуться на unsafePerformIO и тщательно продуманный побочный эффект - не замечающий, казалось бы, чистый интерфейс. Хотя, по общему признанию, он не является чисто внутренним, интерфейс дает ощущение чистоты.
Тем не менее, многие из классических преимуществ производительности от skiplists исходят из того, когда они могут быть реализованы ненадолго, и это исключает функциональный интерфейс.
Поскольку у skiplists есть чистый интерфейс, было бы целесообразно сделать реализацию с использованием IO внутри и обернуть это с помощью unsafePerformIO для интерфейса. Это просто переносит бремя "правильного выбора" с языка на программиста (где бремя всегда лежит на нечистых языках).
Я однажды попробовал реализовать список пропуска в Haskell. Конечно, это была неизменная структура данных (в конце концов, это Haskell). Но это означало, что необходимость случайности исчезла; "fromList" только что подсчитал элементы и построил пропущенные массивы правильной длины для каждого элемента (2 указателя каждый 4-й элемент, 3 каждые 16, 4 каждые 64 и т.д.).
В этот момент я понял, что просто строю более сложную версию дерева с гораздо меньшей способностью мутировать ее. Поэтому я сдался.
Случайные генераторы не требуют операций IO. Они следуют своим собственным монадическим законам (вид, полученный из монады State) и поэтому представляются через монаду Random.
В случае списка пропусков вы можете определить свою собственную монаду, способную переносить вероятностные вычисления или просто использовать стандартный Random.
demo :: Random Int
demo = do
let l = SkipList.empty
l2 <- l `add` ("Hello", 42)
return $ l2 `get` "Hello"
Существует новая реализация списка пропуска, основанная на STM для haskell, см. tskiplist в хакете.
Ну, во-первых, генератор случайных чисел в монаде IO для удобства. Вы можете использовать генераторы случайных чисел вне монады IO; см. System.Random. Но да, вам нужно поддерживать состояние; здесь нужна полезная монада ST. И, да, я бы сказал, программист Haskell предпочитает чистые структуры данных.