algorithm - 函数式编程中的可变性

Question

首先我是一个 Haskell 新手。我读过这个: Immutable functional objects in highly mutable domain我的问题几乎是一样的——如何有效地编写状态应该改变的算法。让我们以 Dijkstra 算法为例。将会找到新的路径并且应该更新距离。在传统语言中，这很简单，而在 Haskell 中，例如，我只能考虑创建全新的距离，这将太慢且耗费内存。在这种情况下，是否有设计模式之类的东西，其中人们应该使用可变数据结构来实现算法，速度和内存使用是主要关注点？

Answer 1

当然，函数式语言有很多方法可以解决这个问题。

1. 不同的数据结构 - 许多数据结构可以纯函数方式实现，具有与命令式版本相同的算法复杂性。这方面最著名的作品可能是 Chris Okasaki 的 Purely Functional Data Structures ，但还有许多其他资源。对于 Dijkstra 算法，Martin Erwig关于 functional graphs 的工作是合适的。参见 this question

2. 不同的算法 - 一些算法内置了可变性假设，快速排序就是一个例子。在这种情况下，可以使用更适合不变性的替代算法。

3. 可变状态 - 每种函数式语言都可以使用 State monad 对函数式状态进行建模。大多数还提供其他形式的可变性，例如 Haskell 的 ST monad 和 IORef。