列表如何共用尾部
一个不可变列表可以由首元素和尾列表组成。若已有尾部为 (b c),在前面构造 a 只需新增一个首节点,两个逻辑列表可以继续指向同一段尾部。
Racket 的 cons 构造这样的成对节点;其 append 则会复制前面的列表连接节点,并把最后一个参数直接作为尾部。因此,同样产生连接结果的操作,复制范围可以不同。
参考:[1]
树更新只复制必要路径
在采用路径复制的树中,更新一个叶节点时,旧根到该位置的路径需要新的节点来指向新结果。没有改变的旁支可以继续共用,所以旧根仍描述旧版本,新根描述新版本。
共享是否划算取决于结构形状和操作。路径很深、更新范围很大或长期保留大量版本时,新增节点仍可能很多,不能把结构共享笼统写成所有操作都是常数成本。
参考:[2]
共享不等于深度不可变
共享结构与不可变性有联系,但不是同一个概念。若节点中存放的对象本身还允许修改,不同逻辑集合仍可能通过那个对象观察到同一变化;外层结构不变并未冻结所有内容。
Clojure 的 transient 示例进一步说明,共享可以配合受控的临时编辑,但要求不通过编辑过程破坏原持久值,且不能把临时中间状态任意保留或同时交给多个线程修改。