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

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

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

参照用 記事

データ型のクレイジー計算

sumiiさん曰く

「積型(組)と和型(バリアント)はあるから、多項式テイラー展開すれば√τみたいな型も考えられる」という話を思い出しました。どこで聞いたのか思い出せないのですが…

R. F. C. Waltersの"Categories and Computer Science (Cambridge Computer Science Texts)"って本のChaper 4 "Data Types"に、crazy calculation と称して無限級数の計算が載っています(sumiiさんのソースとは違う気がするが)。けっこう笑えるので紹介しましょう。

項目がAである列

まず、「I + A + AA + AAA + ... って面白いよ」と同じ例。項目の型(値の集合だと思ってください)がAである列(sequence)をSとすると、方程式は:

  • S = I + A×S (Iは空列だけからなる単元集合、×は“タプルを作る”)

BNF(線形文法規則と言っても同じ)で次のように書いた方が馴染みやすいでしょうかね:

  • s ::= ε | a s (εは空列、a∈A, s∈S)

これを順次代入で、S0 = O(空), S1 = I + A×O, S2 = I + A×I, S3 = I + A×(I + A), ... と解いてもいいのだけど(それが正統的)、Waltersは次のクレイジー計算をしてます。

S = I + A×S
 ↓A×Sを移項して
S - A×S = I
 ↓S = I×Sだから
I×S - A×S = I
 ↓分配法則を使って
(I - A)×S = I
 ↓両辺を(I - A)で割り算して
S = I/(I - A)
 ↓I/(I - A)の級数展開から
S = I + A + A×A + A×A×A + ...

ノードラベルがAである二進ツリー

次は二進ツリー(binary tree)。Aはノードラベルの集合として、Aでラベルされた二進ツリーの集合をTだとすると:

  • T = I + T×A×T

ここで、Iは空ツリーだけからなる単元集合、左部分ツリーと頂点(ラベルが付く)と右部分ツリーを組(3-タプル)にするからT×A×Tですね。文法規則風だと:

  • t :: = ε | t a t (εは空ツリー、a∈A, t∈T)

以下、Tを無限級数で表現する計算、相当にクレイジー。([追記 time="夕方"]間違いがあったので訂正追加した。[/追記]

// ×は省略、累乗は^で表す
T = I + TAT
 ↓Tを移項して整理すると
AT^2 - T + I = O
 ↓二次方程式の解の公式(!)から
T = (I ± sqrt(I - 4A))/2A

ところで、
  sqrt(I - 4A) 
= (I - 4A)^(1/2) 
 ↓二項定理を使って展開すると((a b)は二項係数)
= I - (1/2 1)4A + (1/2 2)4^2 A^2 - (1/2 3)4^3 A^3 + ...

もとの解の公式のマイナスのほうに代入して二項係数をゴニョゴニョして、
T = I + A + 2A^2 + 5A^3 + 14A^4 + ... + 1/(n + 1)(2n n)A^n + ...

例えばA = {a, b}とでもして、n個のノード(a, bでラベルする)を持つ二進ツリー(バランスしてるとは限らない)が何種類できるかを勘定してみると、1, A, 2A^2, 5A^3, 14A^4 という各項の意味が分かると思います。特に、ラベルの集合が単元集合のときは、1, 1, 2, 5, 14, ..., 1/(n + 1)(2n n) はnノードツリーの形状の個数になり、カタラン数と呼ぶそうです。

クレイジーじゃない計算もあるからね

上の例では、引き算、割り算、分数とかを平気で使っているあたりがクレイジーなんですが、型(データ集合)の直和、直積、べき指数(これはなくてもいい)があって、ある程度の完備性と連続性があれば、無限級数の計算は正当化できます。

最小/最大不動点(に対応する型)とかモナドの構成や合成では、無限級数の計算が使われることがあります。クレイジー計算も、まったくのウソ/タワゴトってわけではないです。