このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

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':X2→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を自由に使って組み立てた式は、なんらかの木を表すか未定義(例外)となります。そのような式を木を表す式と呼ぶことにします。

場合分け処理

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

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

問題の記述

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

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

実例 兼 ヒント

T と I + T2 の同型(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を値として持つ」は、計算が成功して値が真偽値となるか、または失敗して例外が投げられることです。