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

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

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

但在函数式编程中，使用IORef不推荐，所以我需要为每个AST节点生成id，并且我希望这个id是stable， 意思是：

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

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

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

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

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

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

你可以有类似的东西

data ASTPathPiece = AddGoLeft
                  | AddGoRight
                  | NegGoDown

type ASTPath = [ASTPathPiece]

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

如果您将 AST 渲染为另一种格式，也许您可​​以在结果节点中添加隐藏属性来标识哪些格式ASTPathPiece导致了他们。向上遍历结果节点到根可以让您重建ASTPath.