• 作成:

haskellプログラマ向けのモノイドの解説

  • 半群とモノイド
  • 数学のモノイドとhaskellのモノイドの差異

背景

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

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

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

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

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

半群(semigroup)

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

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

半群の例

整数と加++の組は半群である.

整数と積**の組は半群である.

半群ではない例

有理数と除法//の組は半群ではない. 反例は(2/2)/4=14(2 / 2) / 4 = \frac{1}{4}, 2/(2/4)=42 / (2 / 4) = 4. 結合法則を満たしていない.

モノイド(monoid)

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

モノイドの例

整数と加++の組はモノイドであり, 単位元はe=0e = 0である.

整数と積**の組はモノイドであり, 単位元はe=1e = 1である.

モノイドではない例

0を除いた整数と加++の組はモノイドではない.

群, 可換群…

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

haskellのモノイド

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

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

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

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

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

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

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