Seven trees - λx. x K S K ＠はてな

NICTA に来てから tree transducer 漬けの毎日．こちらに来るまで，Macro tree transducer (MTT) とか Attributed tree transducer (ATT) とかそれより上のクラスばっかり相手にしていて， Top-down tree transducer (TDTT) は自明な世界だと思ってましたが， Partial や Nondeterministic を許すとなかなか奥が深いです．

と，余談はさておき，表題の件です．元ネタを知っていたので狡いですが，ヒントは，二分木 (Tree) が $X =1 + X \times X$ の不動点で表現できることと， $x = 1 + x^2$ の複素数解 $x = e^{i\pi/3}$ が $x^7 = x$ を満たすということですね．あまり，ヒントになってないか…． OCaml で実装してみましたが，双方向とも 5 種類のパターンによる分岐で定義できます．