避免在不变的有向图中重新访问节点
Avoid revisiting node in an invariant directed graph
这可能与函数式数据结构有关，但我没有找到关于该主题的标签。
假设我有一个语法树类型 Tree，它通过简单地共享公共子表达式组织为 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。
问题来了。整个数据结构是不变的，共享对程序员是透明的，所以似乎无法确定两个节点是否实际上是相同个节点。
同样的问题发生在处理所谓的“打结”结构时。通过打结，我们为原本无限的数据结构生成了有限的数据表示，例如let xs = 1 : xs in xs。这里 xs 本身是有限的，但对其调用 map succ 并不一定会产生有限表示。
这些问题可以归纳为：当数据组织成一个不变的有向图时，我们如何避免重访同一个节点，做重复的工作，甚至在图刚好发生时导致不终止循环？
我想到的一些想法：
- 将
Tree 类型扩展为 Tree a，使每个节点都持有一个额外的 a。生成图形时，将每个节点与唯一的 a 值相关联。内存地址应该在这里起作用，尽管垃圾收集器可能随时移动任何堆对象。
- 对于语法树的例子，我们可能会在简化版的每个节点中存储一个
STRef (Maybe Tree)，但这可能是不可扩展的，并且将特定操作的一些实现细节注入到整个数据结构本身.
这是一个背后有大量研究的问题。通常，由于引用透明性，您无法观察到像 Haskell 这样的纯语言中的共享。但实际上，只要您将自己限制在 IO monad 中进行观察，就可以安全地观察共享。大约 10 年前，Andy Gill（来自旧格拉斯哥学校 FP 的传奇人物之一！）写了一篇精彩的论文：
http://ku-fpg.github.io/files/Gill-09-TypeSafeReification.pdf
非常值得一读，参考书目将为您提供该领域的现有技术和许多建议的解决方案，从 "poor-man's morally-safe" 方法到完全单子打结技术。在我看来，Andy的解决方案和Hackage中对应的reify包：
是这个问题最实用的解决方案。而且我可以从经验中看出它们在实践中非常有效。
这可能与函数式数据结构有关，但我没有找到关于该主题的标签。
假设我有一个语法树类型 Tree，它通过简单地共享公共子表达式组织为 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。
问题来了。整个数据结构是不变的，共享对程序员是透明的，所以似乎无法确定两个节点是否实际上是相同个节点。
同样的问题发生在处理所谓的“打结”结构时。通过打结，我们为原本无限的数据结构生成了有限的数据表示，例如let xs = 1 : xs in xs。这里 xs 本身是有限的，但对其调用 map succ 并不一定会产生有限表示。
这些问题可以归纳为：当数据组织成一个不变的有向图时，我们如何避免重访同一个节点，做重复的工作，甚至在图刚好发生时导致不终止循环？
我想到的一些想法：
- 将
Tree类型扩展为Tree a，使每个节点都持有一个额外的a。生成图形时，将每个节点与唯一的a值相关联。内存地址应该在这里起作用，尽管垃圾收集器可能随时移动任何堆对象。 - 对于语法树的例子，我们可能会在简化版的每个节点中存储一个
STRef (Maybe Tree)，但这可能是不可扩展的，并且将特定操作的一些实现细节注入到整个数据结构本身.
这是一个背后有大量研究的问题。通常，由于引用透明性，您无法观察到像 Haskell 这样的纯语言中的共享。但实际上，只要您将自己限制在 IO monad 中进行观察，就可以安全地观察共享。大约 10 年前，Andy Gill（来自旧格拉斯哥学校 FP 的传奇人物之一！）写了一篇精彩的论文：
http://ku-fpg.github.io/files/Gill-09-TypeSafeReification.pdf
非常值得一读，参考书目将为您提供该领域的现有技术和许多建议的解决方案，从 "poor-man's morally-safe" 方法到完全单子打结技术。在我看来，Andy的解决方案和Hackage中对应的reify包：
是这个问题最实用的解决方案。而且我可以从经验中看出它们在实践中非常有效。