如何在函数式编程中为AST节点生成稳定ID？ [英] How to generate stable id for AST nodes in functional programming?

问题描述

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

I want to substitute a specific AST node into another, and this substituted node is specified by interactive user input.

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

In non-functional programming, you can use mutable data structure, and each AST node have a object reference, so when I need to reference to a specific node, I can use this reference.

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

But in functional programming, use IORef is not recommended, so I need to generate id for each AST node, and I want this id to be stable, which means:

1. 当节点未更改时，生成的ID也不会更改。


2. 当子节点时

而且，为了清楚起见，它是一个ID而不是哈希值：

And, to make it clear that it is an id instead of a hash value:

1. 用于两个不同的子节点，它们比较起来是相等的，但对应于表达式的不同部分，它们应该具有不同的ID。

那么，我应该怎么做呢？

So, what should I do to approach this?

推荐答案

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

Perhaps you could use the path from the root to the node as the id of that node. For example, for the datatype

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

您可能会遇到类似

data ASTPathPiece = AddGoLeft
                  | AddGoRight
                  | NegGoDown

type ASTPath = [ASTPathPiece]

这满足条件2和3但是，a，它通常不满足1。例如，如果将节点插入到先前位置，则列表中的索引将发生更改。

This satisfies conditions 2 and 3 but, alas, it doesn't satisfy 1 in general. The index into a list will change if you insert a node in a previous position, for example.

如果将AST渲染为另一种格式，也许可以添加隐藏的结果节点中的属性，这些结果标识了导致 ASTPathPiece 的原因。将结果节点向上遍历到根将使您可以重建 ASTPath 。

If you are rendering the AST into another format, perhaps you could add hidden attributes in the result nodes that identified which ASTPathPiece led to them. Traversing the result nodes upwards to the root would let you reconstruct the ASTPath.

这篇关于如何在函数式编程中为AST节点生成稳定ID？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！