纯函数式数据结构与写时复制？
我想利用函数式数据结构的优势（可以有多个版本的数据共享结构），但又希望能以命令式的方式进行修改。
我在想的一个例子（可能的应用场景）：一个角色扮演游戏（RPG），在这个游戏中，整个游戏历史都被保存下来（比如说，可以让玩家回到过去）。使用“写时复制”的方式，我可以简单地克隆一个保存游戏状态的结构，然后通过引入一个新的回合来修改它——这样我就可以访问之前的回合（不一定是所有的，可能只是选定的游戏状态快照），而不需要每次都复制所有内容。
假设 foo 是一个地图。
bar = foo.clone()
在这之前，foo 的结构（比如说树形结构）还没有被复制。不过，从现在开始，bar 被视为一个副本，任何对它的修改都不会影响到 foo。
baz = bar[someKey]
baz.modifyInSomeWay()
现在
- 创建了一个新的对象，它是
baz的一个修改版。 bar被替换成一个新的地图，里面保存了新的baz（可能保留了一些foo的结构）。foo不受影响。
但是如果我们接着做...
baz.modifyAgain()
...baz 可以直接被修改，因为我们有它的最新版本。bar 不需要被改变。
这一切都需要保存一些关于 foo 和 bar 的版本信息，在调用 foo.clone() 时增加这个信息，并以某种方式传递给 baz（可能通过将其变成一个代理对象？）。
此外，任何被克隆的结构部分都变成了“历史的一部分”，不能再被修改，这一点可以在运行时强制执行。
这有点像 JavaScript 的原型，但我觉得它更进一步，因为它允许修改向上传播。我认为这就像一个版本控制系统。
- 这种方法有没有被实现过？实现到什么程度？
- 这是个好主意吗？如果不是，有没有办法保存它？
- 怎么实现它？我在考虑在一些高级的垃圾回收语言上构建，比如 Python。
3 个回答
这听起来比直接使用一个完全不可变的数据结构要复杂得多，而且容易出错。我们可以用一个包装器来保存对这个数据结构的引用，并提供一个命令式的接口，通过更新包装的版本来工作。
比如在Scala语言中：
class ImmutableData{
def doStuff(blah : Blah) : ImmutableData = implementation
}
class MutableData(var wrapped : ImmutableData){
def doStuff(blah : Blah) : Unit = { wrapped = wrapped.doStuff(blah); }
}
当然，这样做意味着你需要创建两个版本的接口，但这样做的逻辑会清晰很多。
1. 这个事情有没有做过，做到什么程度了？
有的，举个例子，可以看看qt5中的隐式共享。
2. 这样做是个好主意吗？如果不是，有什么办法可以保存它吗？
是的，这确实是个好主意。一个建议的替代方案是使用完全不可变的数据结构（用一个命令式的接口来包装），但问题是即使一个对象是唯一指向某个数据的，进行修改操作时也会创建数据的副本（不能就地更新），这样效率不高。使用“写时复制”的方法，只有在第一次修改时才会创建副本，后续的修改会直接改变复制的数据（当然前提是没有创建指向同一数据的其他引用）。
3. 这该怎么实现呢？我在想可以在一些高级的垃圾回收语言上实现，比如Python。
一种方法是使用引用计数，就像qt中那样（可以在这里找到描述）。要实现这个功能，需要重载赋值操作符或者显式调用一个方法（比如bar = foo.clone()，但这可能会有点脆弱，如果有人忘记调用clone而直接写bar = foo会怎样呢？），这样才能保持计数。
另一种可能性是创建一个代理对象，就像你说的那样。可以看看pycow（这是一个Python实现）。
函数式（“持久性”）数据结构通常是通过不可变的节点递归构建的，比如单向链表，其中共享了相同的后缀，或者搜索树和堆，只需要复制从根节点到更新项的路径上的部分树结构。
如果每次修改都需要复制整个数据集，那就是不好的做法。在这种情况下，你可能会使用小的“差异”来覆盖，这样会检查这些差异（这会花费额外的时间），并递归到之前的版本。偶尔，当这些差异变得太大时，你可以进行深度复制或重建（这样平均成本就不会那么高）。
持久性数据结构可能会有显著的开销，但如果你能高效地分配小对象（像JVM的垃圾回收就符合这个条件），它们可以非常实用。在最佳情况下，它们的速度可以和可变数据结构一样快，只是在内存使用上有持久性——这可能远远少于每次更新时的完整复制。
根据你使用的编程语言，你可能会发现想要的语法在没有重载赋值操作符的情况下很难实现。在C++中，左值（可变引用）确实需要非持久性的语义。