Если вы будете искать списки пропусков, реализованные в Haskell, вы не найдете много. Это вероятностная структура данных, требующая генератора случайных чисел, а это означает, что любая из этих структур должна работать в монаде IO.
Люди из Haskell держатся подальше от этих структур данных, потому что их невозможно реализовать чисто? Как Haskell может справиться с ними?
Генератор псевдослучайных чисел, конечно, можно использовать вне IO, просто сохраняя текущее значение генератора вместе с вероятностной чистой структурой данных и обновляя ее при построении модифицированных версий. Недостатком этого является то, что PRNG будет более явно детерминированным, чем в нечистой программе, поскольку ничто за пределами единой структуры данных не будет обновлять его. Если важны только статистические свойства, это не представляет проблемы, но в противном случае может вызвать беспокойство.
С другой стороны, сокрытие нечистого ГПСЧ, возможно, является оправданным использованием unsafePerformIO, как в ответе Ганеша Ситтампалама. Это вопиющее нарушение ссылочной прозрачности, но только в той степени, в которой PRNG будет возвращать непредсказуемые, непоследовательные значения — в этом весь смысл! Однако осторожность все же требуется, так как компилятор может сделать неверные предположения о коде, потому что он выглядит чистым.
Но на самом деле ни один из подходов не является ужасно привлекательным. Использование unsafePerformIO неудовлетворительно и потенциально опасно. Потоки состояния PRNG просты, но налагают (потенциально ложную) строгую последовательность на любые вычисления, которые его используют. Программисты на Haskell не отказываются легко ни от безопасности, ни от лени (и это правильно!), и, конечно, структуры данных, ограниченные IO, имеют ограниченную полезность. Итак, чтобы ответить на часть вашего вопроса, вот почему программисты на Haskell, скорее всего, избегают таких структур.
Что касается того, «как Haskell может справляться с такими вещами», я бы предположил, что это неправильный вопрос.
На самом деле все сводится к тому, что многие структуры данных и алгоритмы неявно предполагают (и оптимизируют) императивный, нечистый, строгий язык, и хотя это, безусловно, возможно реализовать их в Haskell редко желательно, потому что (даже игнорируя внутреннюю реализацию) их использование накладывает на ваш код структуру и подход, которые очень не идиоматичны. Кроме того, поскольку Haskell нарушает эти неявные предположения, производительность часто снижается (иногда сильно).
Следует понимать, что алгоритмы и структуры данных — это средство, а не цель. Редко когда требуется одна конкретная реализация — требуется, как правило, определенные характеристики производительности. Поиск структур данных/алгоритмов, которые предлагают желаемые характеристики, но в то же время являются идиоматичными Haskell, почти всегда является лучшим планом и, вероятно, будет работать лучше, чем попытка втиснуть строгую императивную привязку в ленивую функциональную дыру.
Эта ошибка, возможно, чаще всего встречается у тех программистов, которые никогда не сталкивались с проблемой, которую они не могли бы решить с помощью хэш-таблицы, но многие из нас легко поддаются этой привычке. Правильный подход состоит в том, чтобы перестать думать "как мне реализовать это решение на Haskell", а вместо этого "как лучше всего решить мою проблему на Haskell". Вы можете быть удивлены, как часто ответы различаются; Я знаю, что я часто!
unsafePerformIO в своем собственном коде, даже когда это кажется разумным...
- person C. A. McCann; 24.02.2010
Списки пропуска можно реализовать чисто — просто инкапсулируйте текущее начальное число в состояние самого списка пропуска.
data SkipList a = SkipList StdGen (Node a)
data Node a = ...
Это может подвергнуть вас некоторым атакам сложности, которые непрактичны против «настоящих» списков пропуска, поскольку вы можете исследовать вырожденные порядки вставки и повторять атаки против одного и того же начального числа, но это позволяет вам получить преимущества структуры, когда враждебное использование не проблема.
Вы также можете прибегнуть к unsafePerformIO и тщательно продуманному внешнему чистому интерфейсу, не обращающему внимания на побочные эффекты. Хотя, по общему признанию, это не чисто внутренне, интерфейс создает видимость чистоты.
Тем не менее, многие из классических преимуществ производительности от списков пропусков проистекают из того, что они могут быть реализованы непостоянно, что исключает функциональный интерфейс.
Поскольку у списков пропуска есть чистый интерфейс, было бы правильно сделать реализацию, используя 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 предпочитают чистые структуры данных.
