Mutability в функциональном программировании

Question

Сначала я новичок Haskell. Я читал: Immutable functional objects in highly mutable domain И мой вопрос почти такой же - как эффективно писать алгоритмы, в которых должно измениться состояние. Возьмем, к примеру, алгоритм Дейкстры. Будут обнаружены новые пути, и расстояния должны быть обновлены. И в традиционных языках это просто, в то время как в Haskell, например, я могу думать только о создании совершенно новых расстояний, которые будут слишком медленными и потребляющими память. Есть ли что-то вроде шаблонов проектирования для таких случаев, когда нужно реализовать алгоритм с изменяемой структурой данных, а скорость и использование памяти - основные проблемы?

Answer 1

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

1. Различные структуры данных - структуры многих данных могут быть реализованы в чисто функциональной образом, с той же алгоритмической сложностью как императивная версия. Вероятно, самой известной работой в этой области является Purely Functional Data Structures Криса Окасаки, но есть много других ресурсов. Для алгоритма Дейкстры целесообразно работать Martin Erwig по адресу functional graphs. См. Также this question.

2. Различные алгоритмы - некоторые алгоритмы имеют предположения о встроенной модификации, Quicksort - пример этого. В этом случае можно использовать альтернативный алгоритм, который более поддается неизменности.

3. Mutable state - каждый функциональный язык может моделировать функциональное состояние с государственной монадой. Большинство из них также обеспечивают другие формы изменчивости, такие как монашеская монашка Haskell и IORef.

Answer 2

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

Answer 3

Создание новых неизменяемых объектов не так дорого, как вы могли бы подумать, поскольку может произойти большое количество структурного обмена, поскольку компилятор ЗНАЕТ, что они не могут измениться и, следовательно, могут быть безопасно распределены. Тем не менее, использование крайне императивных алгоритмов с большим количеством изменчивого состояния в Haskell - это немного запаха кода.

Answer 4

В производных ML (таких как OCaml, SML, F #) есть «ссылки», которые могут использоваться как изменяемые переменные.

В Haskell это не чисто обрабатывается. Государство просто не покрывается обычным «чисто функциональным» стилем. Чистые языки FP связаны с «вечными истинами» и поэтому не очень подходят для работы с «эфемерными истинами» (хотя это можно сделать, определенно).

Однако да, иногда мы необходимо изменчивое состояние. Язык, такой как ATS, включает линейные типы для обработки разрушительных обновлений и безопасного управления ресурсами.