Seven Trees：ちゃんと問題を述べると

昨晩某所で、id:bonotakeさんとid:ku-ma-meさんにお会いしたのですが、ku-ma-meさんがbonotakeさんのアドバイス（そそのかし）により、Seven Treesパズルを解かれたようです（http://d.hatena.ne.jp/ku-ma-me/20081023/p1 参照）。すごいなー。

「これは難しいパズルだ、取り急ぎ紹介」だけでは、問題が理解しにくいところがあるので、もう少し正確な記述をします（「取り急ぎ紹介」のコメント欄も全部読むと、けっこうハッキリしますがね）。ルールを正確に記述すると、必然的にヒントを与えることになりますが、そもそもノーヒントでは難しすぎる問題なので、順次ヒントを追加していく予定です。

解答例は、解けた人が（少なくともku-ma-meさんが）公表するだろうと思いますが、“他の人のお楽しみ”のため、1,2週間くらい期間を空けたらいいんじゃないのかな。

内容：

1. 木を操作する関数達
2. それらの関数達をもう少し詳しく
3. さらにもう少し補足
4. 集合Tの帰納的定義と木を表す式
5. 場合分け処理
6. 問題の記述
7. 実例 兼 ヒント

木を操作する関数達

以下、「木」とか「ツリー」と言ったら、「これは難しいパズルだ、取り急ぎ紹介」に書いたラベルなしニ分木のことです。

基本的には、コメント欄に書いた次のことを、パズルのルールとして採用します。

テンプレートじゃなくて、次のように言ってもいいかもしれません。関数っぽい言語でアルゴリズムを書くことにして、使っていい関数は：

1. ツリーの左の枝を取り出す関数（単一ノードの木では未定義）
2. ツリーの右の枝を取り出す関数
3. ツリーが単一ノードかどうかを判定する述語
4. タプルの各成分を取り出す射影関数
5. 左枝と右枝からツリーを作る関数（ノード1個増える）
6. 成分達からタプルを構成する関数

これだけです。ツリー定数は使い放題。あとはイコールや条件分岐などを使って書いてください。

それらの関数達をもう少し詳しく

特定のプログラミング言語を使うと、バイアスが生じそうなので、抽象的な記法で押し通すことにします。以下では、イコール記号は「等しい」、または「左辺を右辺で定義する」という意味で使います。

木全体の集合をTとします。t∈T は「tは木である」と同じです。ノード1個だけの木を単ノード木と呼ぶことにして、記号εで表します。εは定数です。一般に、f:X→Y は、fが集合Xから集合Yへの全域的に定義された関数（写像）であることを示します。f:X⊃→Y は、fが部分関数（全域で定義されているとは限らない）であることを表すために使いましょう。fがたまたま全域のときに f:X⊃→Y と書いても間違いではありません。

2引数の関数と、1個の2-タプルを引数とする関数は、数学ではたいてい区別されません*1が、プログラミング言語では区別されることもあるので、f:X,X→Y、f':X²â†’Y のように区別することにします。

前の節で挙げた関数達に名前を付けて、域（domain）と余域（codomain）もハッキリさせましょう。グルーピングが不適切に感じたので、上と順番は変えています。

もとの番号	関数	説明
1	left : T ⊃→ T	木の左の枝を取り出す
2	right : T ⊃→ T	木の右の枝を取り出す
5	cons : T, T → T	左枝と右枝から木を作る
3	is_single : T → {true, false}	木が単ノード木かどうかを判定する
4	proj<n>_<i> : Tn → T	タプルの各成分を取り出す
6	tuple<n> : T, ..., T → Tn	成分達からタプルを構成する

is_single(t) はなくても、等式 t = ε で代用できます（なのでもう出てきません^^;）。tuple<n>とproj<n>_<i>は、tuple3, proj3_1, proj3_2, proj3_3 などを総称的に表したものです。pair = tuple2、p = proj2_1、q = proj2_2 の3つだけで間に合います。が、ここでは tuple<n>, proj<n>_<i> 方式にします（趣味的な選択）。

さらにもう少し補足

Tから単ノード木εを取り除いた集合をT_Λとします。記号Λで、左右の枝がちゃん伸びている雰囲気を出したつもり。当然に、T = {ε}∪T_Λ ですが、共通部分がない集合の合併は記号「+」を使って書き、直和と呼ぶのが習慣です。よって、T = {ε} + T_Λ。さらに、I = {ε} と約束して、T = I + T_Λ となります。

leftとrightは部分関数でしたが、T_Λに制限すれば全域関数です。つまり、left : T_Λ → T、right : T_Λ → T とみなせます。left(ε)、right(ε) は未定義ですが、便宜上 left(ε) = undef、right(ε) = undef と書くことにします。プログラミングとしては、undefは例外を投げることだと解釈するのがいいと思います -- 特殊な値だとしてもいいけど、扱いが面倒。

現実的には、正体不明のモノxに対して*2、それが木やタプルであるかどうかを判断したいこともあるので、is_tree(x)、is_tuple2(x) のような述語も使っていいとします。

集合Tの帰納的定義と木を表す式

個々の木を具体的に示すために、木のリテラル表記があると便利ですが、書くのが面倒なのを我慢すれば、関数の組み合わせで個々の木を表せます。

1. 定数εは木を表します。
2. s, tが木を表す式のとき、cons(s, t)は木を表します。
3. これですべての木を表すことができます。

例を挙げれば、cons(ε, cons(ε, ε)) とか cons(cons(ε, cons(ε, ε)), cons(ε, ε)) とか。

この表記を使って left, right を定義すれば、

• left(ε) = undef
• left(cons(s, t)) = s
• right(ε) = undef
• right(cons(s, t)) = t

定数ε、関数cons, left, rightを自由に使って組み立てた式は、なんらかの木を表すか未定義（例外）となります。そのような式を木を表す式と呼ぶことにします。

場合分け処理

E₁、E₂は木を表す式だとします。E₁ = E₂ （等式） は真偽値またはundefを値として持ちます*3。AND, OR, NOT を自由に使用して、木に関する条件を記述できます。Eが何を表すか不明のときは、is_tree(E), is_tuple2(E) などの述語も使っていいです。

さて、場合分け処理とは、「tが木に関する条件を満たすなら、ナニカする」という記述を並べたもので、if-then-else文、case文、三項式（条件? 式1 : 式2）のようなものです。

問題の記述

Seven Treesの問題は、上で列挙した関数の組み合わせと場合分け処理により、集合Tと集合T⁷（長さ7のタプルの集合）のあいだの1:1対応を作れってことです。

プログラミング言語で実装するときは、すべての関数をほんとに定義する必要はありません。二分木のパターンマッチが使える言語なら、left, rightなんて不要です。木をオブジェクトで書くなら、t.left, t.right というフィールドでもいいでしょう。値の並びからタプルを暗黙に作ってくれる言語なら、tuple<n>も要らないでしょう。proj<n>_<i>もインデックスとかで代用できます。その辺は柔軟に考えてください。

実例 兼 ヒント

T と I + T² の同型（1:1対応）を作ってみます。場合分けは三項式で書くことにします。（「:=」は定義する、「=」は等しいの意味）

// T --> I + T^2 の方向

decompose(t) :=

 t = ε ? ε :

 tuple2(left(t), right(t))
// I + T^2  --> T の方向

compose(x) := 

 x = ε ? ε :

 // xは長さ2のタプル

 cons(proj2_1(x), proj2_2(x))

[追記]KeisukeNakanoさんのココにもヒント(?)が載っています。[/追記]

*1:複圏（multicategory）や多圏（polycategory）の議論では区別されます。

*2:ほんとに正体不明というわけではなくて、バリアントな値です。

*3:undefを例外として実装するなら、「真偽値またはundefを値として持つ」は、計算が成功して値が真偽値となるか、または失敗して例外が投げられることです。