🍣

Monoidを学ぶ

2021/08/19に公開

学習ノートです
集合の初歩的な知識を前提知識としてます

Monoidとは

Monoid(モノイド)とは、1つの結合的 二項演算単位元を持つ代数的構造である

二項演算

二項演算 (binary operation)とは、1+2=3のように、2つの値を用いて新たな値を求める操作のことです

ある集合S[1]の要素a,bに対して、a \cdot b = cのように新たな値を求められる時「\cdotは集合S上の二項演算」[2]と言います
例えば、加法+は自然数\mathbb{N}や整数\mathbb{Z}上の二項演算です

より正確には、集合S上の二項演算とは、直積(デカルト積)S \times Sの要素をSへと移す写像です

f| S \times S \rightarrow S

直積が(a,a), (a,b), \dotsのように要素同士の全組み合わせを表しており、Sの要素2つから新たにSの要素を生成していることがわかります
また、Sのペアに対して行った演算結果もまたSの要素になってることから「演算子\cdotS上の閉じた (closed) 演算」や「閉性 (closure property) を持つ」などと言います
例えば、自然数同士の足し算結果は必ず自然数なので「\mathbb{N}+の下に閉じている」と言います
閉じていない演算を考えることもできるはずですが、不便だしあんまり嬉しいこともないので普通は考えず(多分)、定義を工夫して扱えるようにすると思います
例えば自然数上での引き算は閉じていないので、マイナス方向へ拡張した整数で考えるといった感じです

結合的

結合的 (associativity)な二項演算とは、2回以上演算する場合、式のどの場所から演算しても同じ結果になるということです
要素a,b,c \in Sに対して、(a \cdot b) \cdot c = a \cdot (b \cdot c)が成り立つ時、演算子\cdotは「結合則 (associative law)を持つ」「結合的 (associativity)な演算子」などと言います
例えば自然数の加法は結合則を満たすため、(1+2)+3 = 1+(2+3) = 6です

単位元

単位元(identity element)または中立元(neutral element)とは、どんな値に演算しても値を変えないような値のことです
数学っぽく言うと、ある要素e \in S\forall a \in S, a \cdot e = e \cdot a = aとなるとき、eは単位元です
例えば(\mathbb{N}, +)における単位元は0 (57+0=0+57=57)で、(\mathbb{N}, \times)における単位元は1 (57 \times 1 = 1 \times 57 = 57)です

また、a \cdot e = aは右単位元、e \cdot a = aは左単位元と言い、上では両方持っている前提みたいな感じでしたが、片方しか持たない場合もあります
例えば、a \cdot b = a^bの時、単位元は右単位元1しか存在しません(a^1 = a, 1^a \neq a)
右単位元・左単位元は複数存在し得るらしいですが、右単位元e_rと左単位元e_lを両方持つ場合、以下に示すようにそれらの値は必ず一致します

e_l = e_l \cdot e_r = e_r

代数的構造

代数的構造 (algebraic structure)とは、集合Sと演算\cdotの組み合わせ(S, \cdot)のことです
これは厳密には代数系 (algebraic system) と言うらしいですが、分野によっては同一視するらしいですしこのくらいの理解でいいんじゃないですか
今回はそこまで踏み込んで抽象的にするつもりはないのでこのくらいで勘弁してくだしあ…

関連キーワード?: Algebraic structure (Wikipedia), 台集合 (underlying set)

続・Monoidとは

以上の用語を踏まえ、おさらいしてみましょう

Monoidとは、1つの結合的二項演算と単位元を持つ代数的構造である

つまり、何らかの値を集めたものである集合Sと、Sのある値を使って新たなSの値を計算する操作である演算子\cdotの組み合わせ(S, \cdot)であり、なおかつ演算子\cdotはどのような順番で計算してもいいような法則を持っており、どの値に演算しても元の値を返すような特殊な値を持っている、ということをモノイドと呼ぶわけです

ちなみに、集合Sとその上の演算子\cdotを組み合わせただけのものをマグマ (magma) と呼びます
さらに、マグマの演算子に結合則(a \cdot b) \cdot c = a \cdot (b \cdot c)が成り立つと、半群 (semigroup) となります
例えば(\mathbb{N}, +)(\mathbb{N}, \times)は、マグマだし半群です
半群へさらに単位元が定義されることで、やっとモノイドになります
もちろん(\mathbb{N}, +)(\mathbb{N}, \times)はモノイドでもあります

Rustで書いてみる

せっかくなのでなんかのプログラムにしてみましょう
Rustで書きましたが、簡単な説明も添えてるので書いたことがなくてもなんとなくわかると思います
Rustだとまず以下のように関数の組み合わせを定義します
他の言語でのabstruct classみたいな感じです

trait Monoid {
    // identity element
    fn e() -> Self;
    fn operate(&self, rhs: &Self) -> Self;
}

fn e()が単位元でfn operateが二項演算ですね
残念ながら結合性については表現できないのでテストで検証するものとしましょう

とりあえず自然数の足し算を定義してみましょう

#[derive(Debug, PartialEq)]
struct NAddMonoid(usize);
impl Monoid for NAddMonoid {
    fn e() -> Self {
        NAddMonoid(0)
    }
    fn operate(&self, rhs: &Self) -> Self {
        NAddMonoid(self.0 + rhs.0)
    }
}

Rustを触ってないと不思議に思うかもしれませんが、Tuple structというものがあり、タプルみたいな感じで新しく型を宣言しています
その下のimpl文は、Monoid traitをNAddMonoidへ実装しているということです
deriveとかいうよくわからんやつはデバッグ用の記述です

テストしてみましょう
#[test]でテスト関数を定義し、assert_eq!で2つの値が正しいかどうか検証できます

#[test]
fn n_add_associative() {
    let a = NAddMonoid(10);
    let b = NAddMonoid(23);
    assert_eq!(a.operate(&b), b.operate(&a));
}

#[test]
fn n_add_identity() {
    let a = NAddMonoid(33);
    let e = NAddMonoid::e();
    assert_eq!(a, a.operate(&e));
    assert_eq!(a, e.operate(&a));
}

ちゃんとコンパイルできました

もう1つ書いてみましょう
法則を満たしていればどんな組み合わせでもいいので、min関数などでも実装できます
結合則はまぁ成り立つのがわかってますよね
単位元を+\inftyとすればモノイドとして定義できそうです
Rustに+\inftyは無いので、型の最大値で代用しましょう

#[derive(Debug, PartialEq)]
struct NMinMonoid(usize);
impl Monoid for NMinMonoid {
    fn e() -> Self {
        NMinMonoid(usize::MAX)
    }
    fn operate(&self, rhs: &Self) -> Self {
        NMinMonoid(self.0.min(rhs.0))
    }
}

#[test]
fn n_min_associative() {
    let a = NMinMonoid(10);
    let b = NMinMonoid(23);
    assert_eq!(a.operate(&b), b.operate(&a));
}

#[test]
fn n_min_identity() {
    let a = NMinMonoid(33);
    let e = NMinMonoid::e();
    assert_eq!(a, a.operate(&e));
    assert_eq!(a, e.operate(&a));
}

コンパイルできました。いい感じです

終わり

Rust Playgroundのリンクを貼っておきます
テストする場合は1番左上の点々からTestをを選択してください

今回のコード
trait Monoid {
    // identity element
    fn e() -> Self;
    fn operate(&self, rhs: &Self) -> Self;
}

#[derive(Debug, PartialEq)]
struct NAddMonoid(usize);
impl Monoid for NAddMonoid {
    fn e() -> Self {
        NAddMonoid(0)
    }
    fn operate(&self, rhs: &Self) -> Self {
        NAddMonoid(self.0 + rhs.0)
    }
}

#[test]
fn n_add_associative() {
    let a = NAddMonoid(10);
    let b = NAddMonoid(23);
    assert_eq!(a.operate(&b), b.operate(&a));
}

#[test]
fn n_add_identity() {
    let a = NAddMonoid(33);
    let e = NAddMonoid::e();
    assert_eq!(a, a.operate(&e));
    assert_eq!(a, e.operate(&a));
}

#[derive(Debug, PartialEq)]
struct NMinMonoid(usize);
impl Monoid for NMinMonoid {
    fn e() -> Self {
        NMinMonoid(usize::MAX)
    }
    fn operate(&self, rhs: &Self) -> Self {
        NMinMonoid(self.0.min(rhs.0))
    }
}

#[test]
fn n_min_associative() {
    let a = NMinMonoid(10);
    let b = NMinMonoid(23);
    assert_eq!(a.operate(&b), b.operate(&a));
}

#[test]
fn n_min_identity() {
    let a = NMinMonoid(33);
    let e = NMinMonoid::e();
    assert_eq!(a, a.operate(&e));
    assert_eq!(a, e.operate(&a));
}

参考

脚注
  1. Sは集合を表す英語"Set"の頭文字です ↩︎

  2. ここでは慣習に習い中黒で表してますが、掛け算をしているというわけではないです。また、中黒に限らずどんな記号でも構わない(はず)です。例えば+記号で掛け算のような振る舞いをする二項演算を定義してもいいはずですが、紛らわしいので普通しません ↩︎

Discussion