いずれ、もっと詳しく書くつもりだけど、まーともかく、ざっと紹介しますね。説明が不十分かもしんないけど(ごめんなさい)。[追記]詳しく説明しました。[/追記]
二分木を考えます。空な木は認めない。けど、ルートノードだけの木は認めます。ノードにも辺にもラベルは付いてません。形状だけが問題。ノード数が1から7までの例を描けば次のようですね。
いま、なんでもいいから7本の二分木があったとして、例えば次のような“テンプレート”(番号が付いた白丸のところがプレースホルダ)に当てはめると、1本の二分木ができます。
テンプレートは何種類でも用意してよくて、テンプレート内のプレースホルダを埋めるのに与えられた7本の木全部を使う必要もないとします。例えば、テンプレート内のプレースホルダが1個だけでも0個(単なる二分木)でもいいわけ。
7本の二分木(二分木からなる長さ7のタプル [t1, t2, t3, t4, t5, t6, t7])が与えられたとき、この7本の二分木達の形状を見てテンプレートを使い分けてよいので、ともかくも1本の木を構成します。つまり、[t1, t2, t3, t4, t5, t6, t7] → t という写像を具体的に構成します。
二分木全体の集合をTとすると、いま述べた写像は f:T7→T ですが、可逆なfを作ってください。つまり、g:T→T7も具体的に構成して、次が成立するようにするのです。
- g(f([t1, t2, t3, t4, t5, t6, t7])) = [t1, t2, t3, t4, t5, t6, t7]
- f(g(t)) = t
gを作る手段もfとほぼ同じで、tの形状を見て、テンプレートをパターンマッチに使って、部分木t1, ..., t7を抜き出し、[t1, t2, t3, t4, t5, t6, t7] を出力します。
これ難しいです。僕はヒントを知っているけど、できない*1。
[追記]詳細な説明[/追記]