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

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

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

参照用 記事

二分木の平坦化定理

圏論の計算をしていて、組み合わせ的な議論に行き着くことはよくあります。モノイド圏をいじっていたら、二分木のプリミティブな組み合わせ的事実が必要になりました。その話をします。
\newcommand{\I}{\mathrm{I}}
\newcommand{\A}{\wedge }
\newcommand{\L}{\mathrm{L} }
\newcommand{\moveTo}{\rightsquigarrow }
\newcommand{\cat}[1]{\mathcal{#1} }

内容:

二分木とリスト

二分木〈binary tree〉のテキスト記法としては、「BUNツリーの亜群オペラッド構造 // BUNツリー」で導入した記法を使います。単に「BUNツリー」と言った場合でも、「BUNツリーの亜群オペラッド構造 // 伸縮同値関係」で導入した伸縮同値関係の同値類を意味します。それ以前の記事「反ラックス・モノイド関手の一般余結合律」で定義した二分木は、BUNツリー(の伸縮同値類)と考えることができます。

幅(プレースホルダーの個数)が n であるBUNツリーの集合は、|{\bf BUNTree}(n)| と書きます。絶対値記号で囲っているのは、{\bf BUNTree}(n) と書くと単なるBUNツリーだけではなくて、マックレーン変形などの高次構成素も持つ複雑な構造を表すからです。

n = 0, 1, 2, \cdots に対して、BUNツリー \L(n) を定義します*1

  • \L(0) = \,!
  • \L(1) = (\I-)
  • \L(2) = (-\A-)
  • \L(3) = ( (-\A-)\A-) = (\L(2)\A-)
  • \L(4) = ( ( (-\A-)\A-)\A-) = (\L(3)\A-)
  • \L(k + 1) = (\L(k)\A-)

L(0), L(1) はほんとの二分木ではありませんが、“用語の乱用”で二分木と呼んでしまいますプレースホルダー “-” の出現に左から順に番号を付けて、二分木を次のように(ブラケット囲みの)リストと同一視します。

  • \L(0) = \,! = []
  • \L(1) = (\I 1) = [1]
  • \L(2) = (1\A 2) = [1, 2]
  • \L(3) = ( (1\A 2)\A 3) = (\L(2)\A 3) = [1, 2, 3]
  • \L(4) = ( ( (1\A 2)\A 3)\A 4) = (\L(3)\A-) = [1, 2, 3, 4]
  • \L(k + 1) = (\L(k)\A k+1) = [1, \cdots, k, k + 1]

リストの囲み記号をブラケットにしているのは、ツリーの囲み記号の丸括弧と区別するためで他意はありません。

リストのスプライシングと平坦化

二分木(用語の乱用) \L(n) に関して、BUNツリーとしての幅(プレースホルダーの個数)とリストとしての長さは同じです。

\quad \mathrm{width}(\L(n)) = \mathrm{length}(\L(n)) = n

あるいは、\L(n) \in |{\bf BUNTree}(n)|

1 \le i \le n として、\L(n)i 番目の位置に \L(m) を置換スプライシングすると次のようになります。


\quad [1, \cdots, i-1, [1, \cdots, m], i+1, \cdots,n ]

何をやったのかと言うと:

  1. \L(n)i 番目の要素(番号付きプレースホルダー)を取り除き、“穴”を開ける。
  2. その穴に、\L(n) を挿入する。

これだと、プレースホルダーの番号が左から右に増えてません。それを調整すると:


\quad [1, \cdots, i-1, [i, \cdots, m + i - 1 ], m + i, \cdots, m + n -1]

入れ子のリストを平坦にすると:


\quad [1, \cdots, i-1, i, \cdots ,m + i - 1 , m + i, \cdots, m + n -1]

以上の変形プロセスを、二分木(BUNツリー)へのマックレーン変形で実行できます。このことを示しましょう。

二分木の平坦化定理

ここから先、絵で説明しています。視覚的直感に頼っているので厳密性に欠けますが、それでも説得力は十分にあると思います。

置換スプライシングの一般的な状況は次のように描けます。

赤い部分が挿入された \L(m) で、\L(n) は2つの部分(青と緑)に分断されます。リスト形式で書くなら次のようです。


\quad [1, \cdots, i-1, [i, \cdots, m + i - 1 ], m + i, \cdots, m + n -1]

入れ子を平坦化するプロセスが、マックレーン変形で実行できることを、自然数 m に関する数学的帰納法で示します。m = 0, 1 の場合は個別に調べます。

まず、m = 0 の場合。

この場合は、黒丸を相対ルートとするサブツリーにマックレーン基本変形 \mathrm{RDel} を適用すれば平坦化できます。リスト形式で書くなら次のようです。


\quad [1, \cdots, i-1, [ ], i, \cdots, n -1] \\
\moveTo [1, \cdots, i-1, i, \cdots, n -1]

次に、m = 1 の場合。

この場合は、何もすることがありません。リスト形式で書くなら次のようです。


\quad [1, \cdots, i-1, [i ], 1 + i, \cdots, 1 + n -1]\\
\moveTo [1, \cdots, i-1, i, 1 + i, \cdots, 1 + n -1]

数学的帰納法のステップとして、\L(m) の置換スプライシングの平坦化は出来るとして、\L(m+1) の場合を考えましょう。

黒丸を相対ルートとするサブツリーにマックレーン基本変形 \mathrm{RSw} = \mathrm{LSw}^{-1} を適用すると、\L(m) を置換スプライシングした形に変形できます。数学的帰納法の仮定から、この形はマックレーン変形で平坦化できるので、全体もマックレーン変形で平坦化できます。

何に使うか?

余計な話? 厳密2-亜群オペラッドとモノイド圏」で、\mathrm{S2GO}(\cat{K}) のオペラッド結合を定義する際に、対象のリストの置換スプライシング \vec{A} *_i \vec{B} を使っています。この演算 *_i (記号はオペラッド結合とオーバーロードしている)をちゃんと定義するには、二分木の平坦化定理が必要です。

もっと簡単な例として、単一の圏 \cat{D} から、{\bf Cat}(\cat{D}^n, \cat{D}) を複ホム圏とするような圏-オペラッド(圏で豊饒化〈豊穣化〉されたオペラッド)を作る場合も二分木の平坦化定理が必要です。

*1:Lispにおけるリストの構成と似てますが、完全に同じではありません。