避免在不变有向图中重新访问节点

Kra*_*ntz 6 haskell directed-graph purely-functional

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

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

data Tree = Val Int | Plus Tree Tree

example :: Tree
example = let x = Val 42 in Plus x x
Run Code Online (Sandbox Code Playgroud)

然后,在这个语法树类型上,我有一个纯函数simplify :: Tree -> Tree,当给定 a 的根节点时,它Tree通过首先简化该根节点的子节点来简化整个树,然后处理根节点本身的操作。

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

问题来了。整个数据结构是不变的,共享对程序员是透明的,因此似乎无法确定两个节点是否实际上是同一个节点。

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

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

我想到的一些想法:

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

ali*_*ias 5

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

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

非常值得一读,参考书目将为您提供该领域现有技术的指示以及许多建议的解决方案,从“穷人的道德安全”方法到完全一元打结技术。在我看来,安迪的解决方案和reifyHackage中的相应包:

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

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