Возможность использования в функциональном программировании

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

Ответы

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

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