Chapter 38

13 自由モノイド

さのたけと
さのたけと
2021.06.02に更新

原文:3. Free Monoids

モノイドは圏論とプログラミングの両方で重要な概念だ。圏論は強い型付け言語に対応し、モノイドは型なし言語に対応する。これは、モノイドにおいてはどの2つの関数も合成でき、これがちょうど型なし言語において任意の2つの関数を合成できるのと同じだからである(もちろん、プログラムを実行するときにランタイムエラーが起こるという結末になるかもしれない)。

これまで、モノイドは1つの対象の圏として記述できることを見てきており、モノイドの規則は射の合成の条件にエンコードできるのだった。この圏論的モデルは、モノイドのもっと伝統的な集合論的定義と完全に同値である。この定義は、集合の2つの元を「かけ算」すると3つ目の元が得られるというものだった。この「かけ算」の過程はさらに、まず集合のペアをつくり、そしてすでに存在する(「積」になる)元とこのペアとを同一視するという2段階に分解することができる。

このかけ算の第2段階(ペアをとすでに存在する元とを同一視する段階)をなくしてみると何がおこるだろう?具体的には、任意の集合から始めて、ありうる元のペアを全て作り、そしてそれらを新しい元とよぶのだ。そしてそれら新しい元と全てのありうる元とをペアにして、と続ける。これは連鎖反応である。この新しい元を加えるとことを永遠に続けるのだ。この結果(無限集合になる)は、 ほどんど モノイドである。しかし、モノイドには単位元と結合則も必要なはずだ。問題ない。特別な単位元をつけ加えて、いくらかのペアを同一視すればよい。これでちょうど、単位元と結合則をサポートするようになる。

これがどんな風になるかを簡単な例で見てみよう。2元集合\{a, b\}から始めよう。これらを自由モノイドの生成元とよぶ。まず、単位元の役割をする特別な元eをつけ加える。次に、元のペアをすべてつけ加え、それらを「積」とよぶ。abとの積はペア(a, b)である。baとの積はペア(b, a)であり、aaとの積は(a, a)であり、bbとの積は(b, b)である。eとペアを作ることもでき、(a, e)(e, b)などのようになるが、これらはabと同一視する。この回では、(a, a), (a, b), (b, a), (b, b)だけをつけ加えることになり、集合\{e, a, b, (a, a), (a, b), (b, a), (b, b)\}で終わりになる。

次の回では、次のように元を追加しつづける: (a, (a, b)), ((a, b), a)、などなど。この時点で、結合則がなりたつようにしなければならないので、(a, (b, a))((a, b), a)とを同一視する、などなどをする。言い換えると、内側の括弧は我々にはいらないのである。

この過程の最終結果が何になるかは推測できるだろう: abのありうるすべてのリストを作ることになるのだ。実際、eが空リストを表現しているということにすると、この「かけ算」はリストの連結以外の何者でもない。

この種の、元のありうる組み合わせを作り続け(法則を守るための)最小限の同一視をする構成は、自由構成とよばれる。我々がいまやったのは、生成元の集合\{a, b\}から 自由モノイド を構成するということだった。

(和訳:@ashiato45