Monoidを学ぶ
学習ノートです
集合の初歩的な知識を前提知識としてます
Monoidとは
Monoid(モノイド)とは、1つの結合的 二項演算 と単位元を持つ代数的構造である
二項演算
二項演算 (binary operation)とは、
ある集合
例えば、加法
より正確には、集合
直積が
また、
例えば、自然数同士の足し算結果は必ず自然数なので「
閉じていない演算を考えることもできるはずですが、不便だしあんまり嬉しいこともないので普通は考えず(多分)、定義を工夫して扱えるようにすると思います
例えば自然数上での引き算は閉じていないので、マイナス方向へ拡張した整数で考えるといった感じです
結合的
結合的 (associativity)な二項演算とは、2回以上演算する場合、式のどの場所から演算しても同じ結果になるということです
要素
例えば自然数の加法は結合則を満たすため、
単位元
単位元(identity element)または中立元(neutral element)とは、どんな値に演算しても値を変えないような値のことです
数学っぽく言うと、ある要素
例えば
また、
例えば、
右単位元・左単位元は複数存在し得るらしいですが、右単位元
代数的構造
代数的構造 (algebraic structure)とは、集合
これは厳密には代数系 (algebraic system) と言うらしいですが、分野によっては同一視するらしいですしこのくらいの理解でいいんじゃないですか
今回はそこまで踏み込んで抽象的にするつもりはないのでこのくらいで勘弁してくだしあ…
関連キーワード？: Algebraic structure (Wikipedia), 台集合 (underlying set)
続・Monoidとは
以上の用語を踏まえ、おさらいしてみましょう
Monoidとは、1つの結合的二項演算と単位元を持つ代数的構造である
つまり、何らかの値を集めたものである集合
ちなみに、集合
さらに、マグマの演算子に結合則
例えば
半群へさらに単位元が定義されることで、やっとモノイドになります
もちろん
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関数などでも実装できます
結合則はまぁ成り立つのがわかってますよね
単位元を
Rustに
#[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));
}
参考
- Monoid - Wikipedia
- Binary operation - Wikipedia
- 二項演算 - Wikipedia
- Operation - Wikipedia
- Associative property - Wikipedia
- Identity element - Wikipedia
- Algebraic structure - Wikipedia
Discussion