В Permutive мы привержены функциональному программированию. Обычно это также означает фиксацию неизменяемых структур данных (что очень хорошо!), Но бывают случаи, когда алгоритм работал бы намного быстрее или занимал бы меньше места, если бы он мог обновлять состояние на месте.

Рассмотрим очень полезный, но сильно оклеветанный nub, который удаляет дубликаты из списка:

Это имеет O(n^2) временную сложность из-за внутреннего обхода списка. Но если мы хотим ввести Ord a ограничение, мы можем уменьшить его до O(nlog(n)), построив двоичное дерево, дав нам функцию nubOrd в Data.List.Extra. Кроме того, мы могли бы заменить ограничение Ord a на Hashable a и реализовать nub за O(n) среднее время, если бы мы могли построить изменяемую хэш-карту.

Один из способов достичь этого изменяемого состояния - сохранить наши состояния внутри IORef, поскольку это обеспечивает изменяемую память, защищенную упорядоченными IO действиями. Он будет работать в постоянном пространстве, но не полностью удовлетворителен, поскольку наши типы загрязняются IO. Ясно, что в этом нет необходимости: наша nub функция не хочет изменять какое-либо нелокальное состояние.

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

Итак, можем ли мы создать тип, который разрешает мутацию на месте, но не может использоваться совместно между потоками?

Да! :)

(Большое спасибо Джону Лаанчбери и Саймону Пейтону Джонсу - Ленивые потоки функционального состояния)

Монада ST

Haskell определяет типы ST s a и STRef s a, которые поддерживают, среди прочего, следующие операции:

Это означает, что мы можем писать (псевдо-императивный) код, например:

Пока что это похоже на IORef. Однако разница в том, что мы можем безопасно извлечь значение из ST s a, используя:

Например:

Это очень похоже на unsafePerformIO - на самом деле они тесно связаны внутренне, но вам нужна очень веская причина для использования unsafePerformIO. STRef поддерживается частью изменяемой памяти. Как runST не нарушает ссылочную прозрачность, как unsafePerformIO?

Давайте попробуем "просочить" ссылку из значения ST, чтобы увидеть, что произойдет.

Компилятор выйдет из строя со следующим сообщением об ошибке:

Couldn't match type ‘a’ with ‘STRef s Integer’ because type variable ‘s’ would escape its scope

Почему это? Рассмотрим виды:

Предположим, мы можем применить runST к newSTRef 0. Мы можем попробовать:

Но это противоречит типу runST, поскольку тип возврата зависит от s, тогда как тип возврата runST не зависит от s

Точно так же мы можем показать, что компилятор не позволит нам передать STRef для оценки runST:

Если бы это было законно, v имел бы тип ST s (STRef s Bool) и, следовательно, readVar v :: ST s Bool. Опять же, это не соответствует типу (forall s. ST s a), требуемому runST: s свободен в последнем, но не в первом.

TL; DR фантомный тип s означает, что компилятор запрещает нам передавать STRef в качестве параметра runST или возвращать STRef через runST. Следовательно, мы можем гарантировать, что изменяемое состояние никогда не передается и поэтому runST безопасно, в отличие от unsafePerformIO! (Более строгое доказательство см. В исходной статье)

Вернуться к нубу

Что нам купила монада ST? Теперь у нас есть способ выполнять мутации на месте, сохраняя при этом ссылочную прозрачность! Вот nub, работающий в среднем O(n), с использованием упрощенной изменяемой хэш-карты, как и было обещано - в частности, с использованием STArray, который построен на основе ST и работает примерно так же.

Обратите внимание, что нам не пришлось жертвовать ссылочной прозрачностью, чтобы получить это - сигнатура функции не изменилась. Это также почти прямой перевод эквивалентной реализации на C, но он гарантирует, что наше изменяемое состояние не может выйти за пределы области видимости функции nub - то, что не может сделать ни один императивный язык.

TL;DR

Мы можем использовать монаду ST для реализации функций, которые используют изменяемое состояние для эффективности, сохраняя при этом ссылочную прозрачность, и иметь гарантию компилятора, что мы случайно не передадим это изменяемое состояние. :)

Хотите работать с нами? Мы нанимаем инженеров по Scala, Haskell, облачной инфраструктуре, JavaScript / TypeScript и iOS!