背景

私は高校2年生(2012年)頃に, すごいHaskellたのしく学ぼう!を読んで, haskellを使い始めた.

その中にはモノイドの解説もあり, 当然haskellのコードでもモノイドを使っていたが, haskellのモノイドが何処からきた概念なのか, どうしてこういう設計になっているのか, それをさっぱり理解していなかった.

2014年頃に大学の授業で半群, モノイド, 群を学習して, 多少は理解が深まった. しかしその頃はアウトプットを行っていなかったので, 何処かに書き留めておこうとは思わなかった.

最近群論をまた学ぶ機会が来たので, 拙い数学知識ながらも書き留めておこうと思う. 数学は全く得意ではない.間違いがあればemailやtwitterなどで是非指摘して頂きたい.

私は数学者ではなくプログラマであり, この文章もプログラマ向けに書いている. なので, この文章ではプログラマ向けの言葉を使う.

半群(semigroup)

型$A$と二項演算子$<> :: A -> A -> A$が結合法則を満たすならば, その組は半群である. ここで$<>$は具体的な演算子を指すわけではなく, 任意の演算子であることに注意する.

結合法則とは, 型$A$の任意の変数$a, b, c$に対して, $(a <> b) <> c == a <> (b <> c)$が満たされることである.

モノイド(monoid)

型$A$と二項演算子$<> :: A -> A -> A$が半群であり, 単位元$e$を持てば, その組はモノイドである. 単位元$e$は型Aの変数であり, 型Aの任意の変数$a$に対して$e <> a == a <> e == a$である. 単位元$e$も型と演算子の組に対して決まるのであり, 型だけで決まるのではないことに注意する.

群, 可換群…

更に制約を付け加えたもの.この文書では扱わない.

haskellのモノイド

前述の通り, 本来半群やモノイドは型と2項演算子の組に対して定義されるものである.

ところが, haskellでは型単体でモノイドのインスタンスを作ってしまっている. つまりhaskellのモノイドは数学のモノイドとは違うものである.

haskellのモノイドは例えば整数Intに対して和と積でインスタンスを分けられない. そこでSum, Productといったラッパー型を作ることで対処している.

その点AddとMulが分けられているrustの設計は綺麗に見えるが, アレは半群とは関係ないか.

プログラミングの役に立つの

同級生が｢結合法則とかプログラミングのなんの役に立つんだ…?｣みたいなことを言っていたので書く.

• 結合法則が保証されていると計算を並列化出来る
• 似た性質を持つ演算子が増殖しない
• 単位元は語るまでもなく便利