haskell - 避免重新访问不变有向图中的节点

Question

这可能与函数数据结构有关，但我没有找到有关此主题的标签。

假设我有一个语法树类型Tree，它通过简单地共享公共(public)子表达式来组织为 DAG。例如，

data Tree = Val Int | Plus Tree Tree

example :: Tree
example = let x = Val 42 in Plus x x

然后，在这个语法树类型上，我有一个纯函数 simplify::Tree -> Tree，当给定 Tree 的根节点时，它会简化首先简化根节点的子节点，然后处理根节点本身的操作，从而得到整个树。

由于 simplify 是一个纯函数，并且某些节点是共享的，因此我们希望不要在这些共享节点上多次调用 simplify 。

问题来了。整个数据结构是不变的，并且共享对程序员来说是透明的，因此似乎不可能确定两个节点实际上是否是相同的节点。

处理所谓的“打结”结构时也会出现同样的问题。通过喜结连理，我们为原本无限的数据结构生成了有限的数据表示，例如让xs = 1:xs in xs。这里xs本身是有限的，但是对其调用map succ并不一定会产生有限的表示。

这些问题可以归结为:当数据被组织成一个不变的有向图时，如何避免重新访问同一个节点，做重复的工作，甚至当图恰好是循环时导致不终止？

我想到的一些想法:

1. 将Tree类型扩展为Tree a，使每个节点都持有一个额外的a。生成图表时，将每个节点与唯一的 a 值相关联。尽管垃圾收集器可能随时移动任何堆对象，但内存地址应该在这里起作用。
2. 对于语法树示例，我们可以在简化版本的每个节点中存储一个 STRef(Maybe Tree)，但这可能不可扩展，并将特定操作的一些实现细节注入(inject)到整个数据结构本身。

Answer 1

这是一个背后有大量研究的问题。一般来说，由于引用透明性，您无法观察到像 Haskell 这样的纯语言中的共享。但实际上，只要您限制自己在 IO monad 中进行观察，就可以安全地观察共享。 Andy Gill(老格拉斯哥 FP 学校的传奇人物之一!)大约 10 年前写了一篇关于此的精彩论文:

http://ku-fpg.github.io/files/Gill-09-TypeSafeReification.pdf

非常值得一读，引用书目将为您提供该领域现有技术的指导以及许多建议的解决方案，从“穷人的道德安全”方法到完全单一的打结技术。在我看来，Andy的解决方案以及Hackage中对应的reify包:

https://hackage.haskell.org/package/data-reify

是解决这个问题的最实用的解决方案。我从经验中可以看出，它们在实践中非常有效。