Изменчивость в функциональном программировании

Question

Сначала я новичок на Хаскеле.Я прочитал это: Неизменяемые функциональные объекты в сильно изменяемой области И мой вопрос почти такой же - как эффективно писать алгоритмы, в которых предполагается изменение состояния.Давайте возьмем для примера алгоритм Дейкстры.Будут найдены новые пути и расстояния должны быть обновлены.А в традиционных языках это просто, в то время как в Хаскеле, например, я могу думать только о создании совершенно новых расстояний, которые будут слишком медленными и потребляющими память.Существуют ли что-то вроде шаблонов проектирования для таких случаев, когда нужно реализовать алгоритм с изменяемой структурой данных, а скорость и использование памяти являются главными проблемами?

Answer 1

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

1. Различные структуры данных - многие структуры данных могут быть реализованы чисто функциональным способом с той же алгоритмической сложностью, что и императивные версии. Вероятно, наиболее известной работой в этой области является «1007 * чисто функциональные структуры данных» Криса Окасаки , но есть и много других ресурсов. Для алгоритма Дейкстры подходит работа Martin Erwig над функциональными графами . См. этот вопрос .

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

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