函数式编程中的可变性

Question

首先，我是Haskell的新手。我读了这篇文章：高度可变领域中的不可变函数对象。我的问题几乎与此相同——如何有效地编写需要更改状态的算法。以Dijkstra算法为例，新路径将被发现，并且距离应该被更新。在传统语言中，这很简单，而在Haskell中，我只能想到创建完全新的距离，这将太慢且占用内存。是否有像设计模式这样的东西，可以在可变数据结构下实现算法，并且速度和内存使用是主要问题？

- Mariy

Answer 1

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

1. 不同的数据结构 - 许多数据结构可以以纯函数式的方式实现，具有与命令式版本相同的算法复杂度。这个领域中最著名的工作可能是Chris Okasaki的Purely Functional Data Structures，但还有许多其他资源可用。对于Dijkstra算法，Martin Erwig在functional graphs上的工作很合适。也可以参考此问题。

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

3. 可变状态 - 每个函数式语言都可以使用State monad来模拟函数式状态。大多数还提供其他形式的可变性，例如Haskell的ST monad和IORef's。

- John L

---

遗憾的是，针对惰性函数式不可变语言最适合的数据结构和算法的研究落后于严格命令式可变语言的研究。 :-( - ephemient

Answer 2

ST Monad 可以让你在内部使用可变状态，但外部接口仍然是纯的。

- Anon.

Answer 3

创建新的不可变对象并不像你想象的那么昂贵，因为编译器知道它们不能改变，所以可以安全地共享大量的结构。尽管如此，在Haskell中使用高度命令式的算法和大量可变状态是一种代码异味。

- Tyler Eaves

Answer 4

在ML派生语言（如OCaml、SML、F#）中，有“引用”可以用作可变变量。 在Haskell中，这并不是很干净的处理方式。状态根本没有被通常的“纯函数式”风格所涵盖。纯FP语言处理“永恒的真理”，因此不太适合处理“短暂的真理”（尽管肯定可以做到）。 然而，有时我们确实需要可变状态。像ATS这样的语言结合了线性类型来处理破坏性更新和安全资源操作。

- Artyom Shalkhakov