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

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

背景

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

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

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

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

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

半群(semigroup)

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

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

半群の例

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

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

半群ではない例

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

モノイド(monoid)

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

モノイドの例

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

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

モノイドではない例

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

群,可換群…

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

haskellのモノイド

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

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

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

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

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

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

  • 結合法則が保証されていると計算を並列化出来る
  • 似た性質を持つ演算子が増殖しない
  • 単位元は語るまでもなく便利
このエントリーをはてなブックマークに追加 fb-like g-plusone