bonotakeの日記

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

Seven trees 拡張問題 解答編

長くなったので、新たにエントリー起こしました。
空の木、片枝を許した場合で T \simeq T^7を示す問題の解答編です。とはいえ、オリジナルの解答をまだ公開してないので、中途半端な解説になってますが。
元のエントリーはこちら


id:ku-ma-meさんのHaskellでの問題定義(ここ)で、二分木を

data Tree = Leaf | Node Tree Tree deriving Eq
type Tree7 = (Tree, Tree, Tree, Tree, Tree, Tree, Tree)

と定義してましたが、これを

data Tree = Empty | Node Tree Tree deriving Eq
type Tree7 = (Tree, Tree, Tree, Tree, Tree, Tree, Tree)

と書き換えれば、空の木を含めた二分木の定義をした事になります(^^; ここで、Emptyは空の木です。元々Leafと書いていたものは

Node Empty Empty

として表現されます。片枝の木は、例えば

Node (Node ...) Empty

みたいな感じで書ける訳ですね。

fとgの実装についても、Leafかそうでないかで場合分けしていたところを、Emptyかそうでないかで場合わけすればすむので、基本的にコード中の"Leaf"を"Empty"で全置換すれば、空の木・片枝を考慮した解答のできあがり、ですw

で、ここまで書くとほぼ明らかですが、元々の問題と空の木・片枝を考えた場合の問題とで、本質的に何も変わりません。Leafを「単ノードの木」と解釈してるのは人間の勝手であって、なので字面に惑わされずLeafを「空の木」と脳内変換すれば、コードを書き換える必要すらありません。

拡張問題というより、何か子供だましみたいな感じですね。失礼しました。

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