haskell - 如何在函数式编程中为AST节点生成稳定的id？

Question

我想将一个特定的 AST 节点替换为另一个节点，并且这个替换的节点是由交互式用户输入指定的。

在非函数式编程中，可以使用可变数据结构，并且每个AST节点都有一个对象引用，因此当我需要引用特定节点时，可以使用这个引用。

但是在函数式编程中，不建议使用IORef，所以我需要为每个AST节点生成id，并且我希望这个id稳定，这意味着:

1. 当节点不改变时，生成的id也不会改变。
2. 当子节点更改时，其父节点的 id 不会更改。

并且，为了明确它是一个 id 而不是哈希值:

对于两个不同的子节点，它们比较相等，但对应表达式的不同部分，它们应该具有不同的 id。

那么，我应该怎么做才能解决这个问题？

Answer 1

也许您可以使用从根到节点的路径作为该节点的 id。例如，对于数据类型

data AST = Lit Int
         | Add AST AST
         | Neg AST

你可以有类似的东西

data ASTPathPiece = AddGoLeft
                  | AddGoRight
                  | NegGoDown

type ASTPath = [ASTPathPiece]

这满足条件 2 和 3，但遗憾的是，它通常不满足条件 1。例如，如果您在先前位置插入节点，列表中的索引将会更改。

如果您要将 AST 渲染为另一种格式，也许您可​​以在结果节点中添加隐藏属性，以识别哪个 ASTPathPiece 通向它们。向上遍历结果节点到根可以让您重建 ASTPath。