Seven trees＋拡張問題

seven trees の問題、私も解いてみました。以下参考：

• Seven Trees：これは難しいパズルだ、取り急ぎ紹介 - 檜山正幸のキマイラ飼育記
• Seven Trees - まめめも
• Seven trees - λx.x K S K ＠ はてな
• Seven Trees：ちゃんと問題を述べると - 檜山正幸のキマイラ飼育記

実装言語はHaskell、ってかid:ku-ma-meさんがささっと解いて貼り付けたコードの大枠をテンプレートにさせて頂きました(^^;
とはいえku-ma-meさんとまるきり同じコードになってもつまらないので*1、檜山さんのいうところの「木を操作する関数」を使うとか、id:KeisukeNakanoさんのいうところの「5種類のパターンによる分岐」でやってみるとか色々考えたんですが…考えてるうちに面倒くさくなったので、元の方針からできる範囲で最適化して、とりあえず自分なりに書いちゃいました。

で結局、f, gの実装は、パターンマッチを最大限活用して、

f (t1,t2,t3,t4,t5,t6,t7) = t

とか

g t = (t1,t2,t3,t4,t5,t6,t7)

とかいうのを羅列してるだけです。 (t, t1~t7はTreeのパターン） 関数というより殆どただのテーブルですね。
ちなみにこれで、fもgも9行です（型宣言部を除けば）。つまり、ともに9種類のパターンでの分岐です。

いやー、しかしうまくできてるもんだなぁ。

それから、拡張問題…というほど大げさなものではないですが。
オリジナルの問題では、空の木（ノードが一つもない木）が許されていません。また、片方の枝しかないノードというのも許されていないのです。ノードは枝がないか（Leaf）、左右両方に枝があるか、なんですね。

でも、仮に空の木や片枝を許したとしても、やはり元の問題 はちゃんと成り立ちます。で、空の木・片枝が入ったバージョンの解答も作ってみました。上のも併せていずれ公開します。
元の問題が解けた人は、これも考えてみてくださいませ。ある事に気づけば、空の木・片枝がないバージョンに少し手を入れるだけでいけるはず*2。

[追記] 拡張問題についてはコメントで解答がでてしまったので、本文でも簡単に解答しちゃう事にします。別エントリーで解答を書きます。元々ここに書いてたんですが、長いので分けました。→http://d.hatena.ne.jp/bonotake/20081025/1224924682 まぁ、ここのコメント見たらすぐわかるんですけど。

*1:昨晩ku-ma-meさんと話して、大まかな解き方の方針までは大体共有していたのでした。

*2:いや、よく考えると、これは若干嘘かもしれないｗ …と書いたのは、ちょっとしたヒッカケです。詳しくはコメント、追記参照。