Как создать стабильный идентификатор для узлов AST в функциональном программировании?

Question

Я хочу заменить определенный узел AST другим, и этот замещенный узел определяется интерактивным пользовательским вводом.

В нефункциональном программировании вы можете использовать изменяемую структуру данных, и каждый узел AST имеет ссылку на объект, поэтому, когда мне нужно обратиться к конкретному узлу, я могу использовать эту ссылку.

Но в функциональном программировании используйте IORef не рекомендуется, поэтому мне нужно создать идентификатор для каждого узла AST, и я хочу, чтобы этот идентификатор был стабильным, что означает:

1. когда узел не изменяется, сгенерированный идентификатор также не изменится.
2. когда дочерний узел изменяется, его родительский идентификатор не изменится.

И, чтобы было ясно, что это идентификатор вместо хеш-значения:

3. для двух разных подузлов, которые сравниваются одинаково, но соответствуют разным частям выражения, они должны иметь разные идентификаторы.

Итак, что я должен сделать, чтобы приблизиться к этому?

Answer 1

Возможно, вы могли бы использовать путь от корня до узла в качестве идентификатора этого узла. Например, для типа данных

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

Вы могли бы иметь что-то вроде

data ASTPathPiece = AddGoLeft
                  | AddGoRight
                  | NegGoDown

type ASTPath = [ASTPathPiece]

Это удовлетворяет условиям 2 и 3, но, увы, вообще не удовлетворяет 1. Индекс в списке изменится, например, если вы вставите узел в предыдущую позицию.

Если вы отображаете AST в другом формате, возможно, вы могли бы добавить скрытые атрибуты в результирующие узлы, которые идентифицировали ASTPathPiece привел к ним. Обход результирующих узлов вверх до корня позволит вам восстановить ASTPath,