Haskell уклоняется от вероятностных структур данных?

Question

Если вы будете искать списки пропусков, реализованные в Haskell, вы не найдете много. Это вероятностная структура данных, требующая генератора случайных чисел, а это означает, что любая из этих структур должна была бы работать в монаде ввода-вывода.

Люди Haskell держатся подальше от этих структур данных, потому что невозможно реализовать их чисто? Как Haskell может справиться с ними?

Answer 1

Генератор псевдослучайных чисел, конечно, может использоваться за пределами IO, просто сохраняя текущее значение генератора вместе с вероятностной структурой чистых данных и обновляя ее при построении модифицированных версий. Недостатком этого является то, что PRNG будет более явно детерминированным, чем в нечистой программе, так как ничто за пределами единой структуры данных не сможет его обновить. Если только статистические свойства имеют значение, это не представляет проблемы, но может быть причиной для беспокойства в противном случае.

С другой стороны, сокрытие нечистого PRNG, возможно, является оправданным использованием unsafePerformIO, как в Ganesh Sittampalam . Это явно нарушает ссылочную прозрачность, но только в той степени, в которой PRNG будет возвращать непредсказуемые, противоречивые значения - вот и весь смысл! Однако необходимо соблюдать осторожность, поскольку компилятор может сделать неверные предположения о коде, потому что он выглядит чисто.

Но на самом деле ни один из этих подходов не является чрезвычайно привлекательным. Использование unsafePerformIO неудовлетворительно и потенциально опасно. Потоки в состоянии PRNG просты, но накладывают (потенциально ложную) строгую последовательность на любые вычисления, которые его используют. Программисты Haskell не отказываются ни от безопасности, ни от лени (и это правильно!), И, конечно, структуры данных, ограниченные IO, имеют ограниченную полезность. Поэтому, чтобы ответить на часть вашего вопроса, программисты на Haskell, скорее всего, избегают таких структур.

---

Что касается того, «как Хаскелл может справиться» с такими вещами, я бы предположил, что это неправильный вопрос, чтобы задать .

Что действительно сводится к тому, что многие структуры данных и алгоритмы неявно предполагают (и оптимизируют для) императивный, нечистый, строгий язык , и хотя он, безусловно, возможно реализовать их в Haskell, редко желательно , потому что (даже игнорируя внутреннюю реализацию) их использование налагает на ваш код структуру и подход, который очень не идиоматичен. Кроме того, поскольку Haskell нарушает эти неявные допущения, производительность часто снижается (иногда очень сильно).

Необходимо понять, что алгоритмы и структуры данных являются средством, а не целью . Редко бывает так, что требуется одна конкретная реализация - то, что требуется , , обычно соответствует характеристикам производительности . Поиск структур данных / алгоритмов, которые предлагают желаемые характеристики и в то же время идиоматичны, Haskell почти всегда является лучшим планом и, скорее всего, будет лучше, чем попытка втиснуть строгий императивный колышек в ленивое функциональное отверстие.

Эта ошибка, пожалуй, чаще всего встречается в подмножестве программистов, которые никогда не сталкивались с проблемой, которую не могли решить с помощью хеш-таблицы, но для многих из нас привычка проста. Правильный подход состоит в том, чтобы перестать думать «как реализовать это решение в Haskell», а вместо этого «каков наилучший способ решения моей проблемы в Haskell» . Вы можете быть удивлены, как часто ответы отличаются; Я знаю, что я часто!

Answer 2

Списки пропусков могут быть реализованы просто - просто инкапсулируйте текущее начальное число в состояние самого списка пропусков.

data SkipList a = SkipList StdGen (Node a)
data Node a = ...

Это может подвергнуть вас некоторым атакам сложности, которые не практичны против «настоящих» списков пропусков, поскольку вы можете проверять вырожденные порядки вставки и повторять атаки против одного и того же начального числа, но это позволяет вам извлечь преимущества структуры, когда состязательное использование не является проблемой.

Вы также можете воспользоваться unsafePerformIO и тщательно продуманным интерфейсом, не обращающим внимания на побочные эффекты. Хотя по общему признанию это не чисто внутренне, интерфейс производит впечатление чистоты.

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

Answer 3

Поскольку скиплисты имеют чистый интерфейс, было бы правильно сделать реализацию, использующую IO внутри, и обернуть ее с unsafePerformIO для интерфейса. Это просто переносит бремя «сделать все правильно» с языка на программиста (именно здесь бремя всегда лежит на нечистых языках).

Answer 4

Однажды я попробовал реализовать список пропусков в Haskell. Конечно, это была неизменная структура данных (в конце концов, это Haskell). Но это означало, что потребность в случайности исчезла; «fromList» только что посчитал элементы и построил пропускаемые массивы правильной длины для каждого элемента (2 указателя на каждый 4-й элемент, 3 на каждый 16-й, 4 на 64-й и т. д.)

В тот момент я понял, что просто строю более сложную версию дерева с гораздо меньшей способностью изменять его. И я сдался.

Answer 5

Существует новая реализация списка пропусков, основанная на STM для haskell, см. tskiplist о взломе.

Answer 6

Случайные генераторы не требуют IO операций. Они следуют своим собственным монадическим законам (своего рода полученным из монады State) и поэтому могут быть представлены через монаду Random.

В случае списка пропусков, вы можете определить свою собственную монаду, которая может выполнять вероятностные вычисления, или просто использовать стандарт Random.

demo :: Random Int
demo = do
 let l = SkipList.empty

 l2 <- l `add` ("Hello", 42)

 return $ l2 `get` "Hello"

Answer 7

Ну, во-первых, генератор случайных чисел в монаде IO есть для удобства. Вы можете использовать генераторы случайных чисел вне монады IO; см. System.Random. Но да, вам нужно поддерживать состояние; ST монада полезна здесь. И да, я бы сказал, что программист на Haskell предпочитает чистые структуры данных.