haskell - Haskell の親を持つ構文ツリー

Question

Haskell で AST を実装したい。親参照が必要なため、機能的なデータ構造を使用することは不可能に思えます。次のような記事を見ました。ノードを次のように定義します。

type Tree = Node -> Node

ノードを使用すると、タイプ Key a のキーで属性を取得できます。そのようなパターンについて読むべきものはありますか? さらにいくつかのリンクを教えていただけますか？

Answer 1

循環的な自己参照を持つ純粋なデータ構造が必要な場合は、デルナンがコメントで言っているように、それを表す通常の用語は「結び目を結ぶ」です。その用語を検索すると、より多くの情報が得られるはずです。

結び目を結ぶことによって構築されたデータ構造は、通常の方法で「更新」するのが困難 (または不可能) であることに注意してください。サイクルのどの部分でも、サイクル全体を再構築する必要があります。もちろん、何をしているかによって、これが問題になる場合とそうでない場合があります。