bonotakeの日記

元・ソフトウェア工学系研究者、今・AI系エンジニア

Seven trees+拡張問題

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)、左右両方に枝があるか、なんですね。

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



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

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

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

注:bonotakeは、amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイト宣伝プログラムである、 Amazonアソシエイト・プログラムの参加者です。