長くなったので、新たにエントリー起こしました。
空の木、片枝を許した場合で を示す問題の解答編です。とはいえ、オリジナルの解答をまだ公開してないので、中途半端な解説になってますが。
元のエントリーはこちら。
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"で全置換すれば、空の木・片枝を考慮した解答のできあがり、ですｗ
で、ここまで書くとほぼ明らかですが、元々の問題と空の木・片枝を考えた場合の問題とで、本質的に何も変わりません。Leafを「単ノードの木」と解釈してるのは人間の勝手であって、なので字面に惑わされずLeafを「空の木」と脳内変換すれば、コードを書き換える必要すらありません。
拡張問題というより、何か子供だましみたいな感じですね。失礼しました。
