5種類に分類するのがさっぱり分からん
http://d.hatena.ne.jp/KeisukeNakano/20081024/1224806200
には5種類に分類すればいいと書いてあるので、考えてみたのだがさっぱり分からない。
その代わり考えるヒントが生まれた。
2〜6の場合に存在しないことを証明するために考えてたので、この問題を解くためのヒントにはならないと思う。
最初のルールの説明にあったテンプレートは実は重要っぽい。
テンプレートは
Tmpl := | Leaf : Tmpl | Node : Tmpl -> Tmpl -> Tmpl | Hole : Tmpl
で定義できて、テンプレートtをインスタンシエートした結果の全体はTree全体Tの部分集合I(t)と考えることができる。
テンプレートの穴の数をh(t)と書くことにする。
テンプレートの組x = (t1, t2, ..., tn)を持ってきて、T が
T = I(t1) + I(t2) + ... + I(tn)
と直和に分解できたとする。この分解は全単射
Match_x : T -> T^h(t1) (+) T^h(t2) (+) ... (+) T^h(tn)
を導く。
テンプレートの組 y = (s1, s2, ..., sn) を持ってきて、少し厳密さを失うが T^7 を
T^7 = I(s1) + I(s2) + ... + I(sn)
のように直和に分解できて、x による T の分解と同じ形だとしたら
f(v) = Match_x(Match_y^-1(v)) g(v) = Match_y(Match_x^-1(v))
が求める関数になる。
逆にルールに従った全単射があれば、上のようにデストラクションとコンストラクションの合成関数になると思う(←証明したい)。
5個に分類する話に戻ると、僕はこれを5個のテンプレートで直和分解すると解釈して、
考えうる直和分解を順番に書き出してみたのだが、どう考えてもうまくいきそうにないわけだ…