圏論の小咄をしようかと思ったのですが、大文字のパイ「Π」なんて記号を出すと見慣れないで戸惑う人もいるかなー、と。とりあえず今日は記号の説明だけ書いておきます。
ある文脈では、大文字のパイ「Π」も大文字のシグマ「Σ」もほとんど同じ意味で使うんですが、掛け算と足し算の違いがあります。ところで、掛け算とか足し算とは何を意味するか? まずはモノイドの話から。
モノイドは、集合X上のなんらかの二項演算 □:X×X→X と特別な要素e(e∈X)からなる構造です。結合律と単位律を満たします。
- (x□y)□z = x□(y□z)
- e□x = x□e = x
今は、「□」なんて変な記号を使いましたが、掛け算の記号であるアスタリスク「*」やナカグロ「・」がよく使われます。演算が可換のとき、つまり x□y = y□x なら足し算のプラス記号「+」がふさわしいでしょう。
演算にどんな記号を使うかは、実はどうでもいいことですが、次の約束に従うことにします。
次に総積(総乗)について; a1, a2, ..., an がモノイドの要素の列のとき、a1*a2* ... *an を Π(i = 1 to n | ai) と書くことにします。上付き下付きを使えば、Πi=1n(ai) ですが、書くのがめんどくさいですね。ai の下付きも a[i] とインデックス形式で書くとフラットテキストで書けます。
- Π(i = 1 to n | a[i]) = a[1]*a[2]* ... *a[n]
ちょっと変わったfor文を導入すると、次のように書けます。
for (result = 1; i = 1 to n) { result *= a[i] }
このfor文は、for (初期化; インデックスの範囲) {代入操作} の形で、result変数の最後の値を全体の値とします。値を持つので、for文というよりfor式です。
5の階乗なら次のように書けます。これは、a[i] = i のケースです。
for (result = 1; i = 1 to 5) { result *= i }
「Σ」は、演算が足し算の形に書かれているときに使う記号で、意味は「Π」とまったく同じです。
- Σ(i = 1 to n | a[i]) = a[1] + a[2] + ... + a[n]
先ほどのfor形式で Σ(i = 1 to 5 | i*i) を書くと:
for (result = 0; i = 1 to 5) { result += i*i }
モノイドの要素の列をリストとして a = [a1, a2, ..., an] のように書くことにします。ΠやΣは、1つのリストを受け取る関数だとも思えます。例えば、普通の整数で考えて、Π([1, 2, 3, 4, 5]) = 1*2*3*4*5 = 120、Σ([1, 2, 3, 4, 5]) = 1 + 2 + 3 + 4 + 5 = 15 とか。集合Xのリストの全体を List<X> と書くことにして、Xがモノイドになっているなら、Π:List<X>→X のような関数が定義できます。
Πは二項演算*を任意の長さのリストに拡張したものですが、長さ0,長さ1のリストには特別な定義が必要です。
- Π([]) = 1
- Π([x]) = x
長さが2以上なら、*の繰り返し計算になります。どこから計算してもいいことは結合法則が保証します。しかし、リストの並び順を変えると結果は変わるかもしれません(非可換性)。
モノイドの演算が可換なら、リストの並び順を気にする必要はありません。並び順を無視したリストをバッグ(またはマルチセット)と呼びます。可換モノイドに関するΣは、Σ:Bag<X>→X という関数だと思ってもかまいません。
ΠやΣの使い方に慣れると、モナドのアイレンベルク/ムーア圏の構成(Eilenberg-Moore construction)も割とスンナリ理解できると思います。また、ベックによる複合モナドの構成法に出てくる分配法則(分配律)がどうして分配法則と呼ばれるかも見当が付くでしょう。