ツリーの書き換え

Question

私はタイプシグネチャを表すデータ構造を持っています。このデータ構造は、最初のピクチャで赤のイメージとして例示されているツリーです。私は黒を手に入れたいと思っていますが、これまではオレンジ色（2番目の写真）しか持っていませんでした。これはタイプツリーですが、左に関連付けられています。

ここで私はこれまで持っているオレンジの木（オレンジ色の矢印に従ってください）

は、私はかなり木を印刷することで、この問題を解決し、その後でそれを解析していたですパーサーコンビネータであるが、この非効率性は望ましくない。私は、オレンジ色のツリーから黒色のツリーに変換する別のアルゴリズムを持つことができると思いますが、2つのアルゴリズムを作成する代わりに、1つしか書くことができない方が良いでしょう。

私は、私が解決策を書いているので、これをHaskellとタグ付けします。私は赤い木のようなデータ構造を得るためのコードを提供することができましたが、解決策の試みが複雑になると思います。

このアルゴリズムの名前があるかどうか、赤い木の中のオペレータの位置は、です。それはプレフィックスですか？

ありがとうございました。

Answer 1

再帰スキームを見てください。リンクの負荷を含み、ここで、関連する質問があります：

Recursion schemes for dummies?

その質問へのすべてのリンクは優れているが、私は特に（その質問への私の答えにリンク）ティム・ウィリアムズのスライドを見てみたいです様々な異なる再帰パターンの具体的な実装（そのほとんどは木構造上でデモされています）。