半群 (Semigroup)

2023/10/21

関数型プログラミング
代数的データ型
数学
Scala

想定読者

Scala を触ったことがある人
型クラスが気になっている人
半群について知りたい人
Scala とか型クラスとは半群とか知らんけど新しいことを知りたい人

はじめに

この記事ではゆるふわに半群と、それをプログラミングで扱う方法を学ぶ。ゆるふわなので厳密な定義や証明は行なわないし、説明のため意図的に正確ではない表記を用いたりしてる。説明のためのプログラミング言語として Scala 3 を使うが Scala 3 の知識は都度説明する。何かしらのプログラミング言語を学んだことがある人であれば理解できると思う。

それでは、型クラスによるプログラミングの世界を体験する最初の一歩を踏み出そう。

半群とは？

さっそくだが半群とは何だろうか？

数学における半群（はんぐん、英: semigroup）は、集合 S とその上の結合的二項演算とをあわせて考えた代数的構造である。
-- Wikipedia

それでは代数的構造とは何だろうか？

代数的構造は、集合とその集合上の演算によって決まる構造のこと。
-- Wikipedia

代数的構造の具体例をいくつか上げると以下のようなものがある。

半群
モノイド
群
環
体
束

どのような代数的構造に馴染みがあるかは、大学でどのような分野を専攻していたかに依存するだろう。数学ではさまざまな代数的構造を考えるが、プログラマは モノイド を覚えておけばいい。そして、モノイドよりも満すべき条件がゆるい代数的構造として半群がある。

御託はこの辺にして半群の定義を見てみよう。

半群

集合 $S$ とその集合上の二項演算 $\circ: S \times S \to S$ の組 $(S, \circ)$ が以下の条件を満すとき半群という。

二項演算 $\circ$ が 結合律 を満たす

また、集合 $S$ のことを 台集合 と呼ぶ。

結合律

$x, y, z \in S$ に対して、

$(x \circ y) \circ z = x \circ (y \circ z)$

が成り立つ。

ゆるい説明

定義から群は、

集合 $S$
二項演算子 $\circ: S \times S \to S$

の 2 つを考えて、二項演算子が結合律を満していればよい。また、群はそのような集合 $S$ と二項演算子 $\circ$ の組 $(S, \circ)$ のことを言う。

集合は説明は不要だろう。結合律は、中学や高校では 結合法則 と呼ばれている。整数の足し算を例に学んだことがあるのではないだろうか。

整数 $x$ , $y$ , $z$ について、

$(x + y) + z = x + (y + z)$

が成り立ち、整数の足し算では足す順序に依らず計算結果が変わらないという法則を習っただろう。中学、高校までは結合法則、結合則と呼んでいた記憶があるが、大学数学以降では整数の足し算の結合則のような性質は結合律と呼ぶことが多いように感じる。私が通っていた大学では、すべての講義で結合律と呼んでいたと思う。これは名称の違いというだけだ。

この例で結合律と呼ばれるものがどのようなものであるか掴めたのではないだろうか。整数の足し算は二項演算ですべての整数について定義され結合律を満している。

まさに半群の例の一つとして $(\mathbb{Z}, +)$ が見つかった ( $\mathbb{Z}$ は整数の集合を表す)。

閑話

ログイン不要の匿名アンケートなので気が向いたら答えてね。

読者アンケート

※ 「読者アンケート」をクリックするとアンケートが表示される。

数学における半群の例

例示は理解の試金石 -- 数学ガール

例で理解するのは大切だ。例は抽象的な定義よりも理解しやすいし、自分で例を作ることより深い理解を助ける。それでは $(\mathbb{Z}, +)$ 以外の例として以下のような組が上げられる。

$(\mathbb{Z}, \times)$
$(\mathbb{Q}, +)$
$(\mathbb{Q}, \times)$
$(\mathbb{Q} \backslash \{0\}, \div)$
$(\{\mathtt{true}, \mathtt{false}\}, \land)$
$(\{\mathtt{true}, \mathtt{false}\}, \lor)$

加算だけでなく、乗算についても半群となることは定義を確認すればわかるだろう。また、台集合を有理数 ( $Q$ ) まで広げて $0$ を除いてあげれば除算についても半群となる。二値論理における論理積、論理和のようなものも半群であることが直ぐにわかるだろう。

このように半群はゆるい代数的構造なので至るところに登場する。

プログラミングにおける半群の例

(Int, +)
(Int, *)
(String, ++)
(List[T], ++)
(Option[Semigroup[T]], |+|)
(Map[K, Semigroup[V]], ++)
(A => A, compose)

Int は Long 、 Float 、 Double にしても成り立つ。 (Option[Semigroup[T]], |+|) や (Map[K, Semigroup[V]], ++) は正確性に欠ける表記だが、これらの表記については後で解説する。

半群 in Scala 3

いよいよ本題に入って、Scala 3 のコードで半群を表現してみよう。

半群の定義

半群の定義を Scala 3 のコードに落とし込むと以下のようになる。

scala

1trait Semigroup[T]:
2  extension (x: T) def combine(y: T): T

このコードは型クラスと呼ばれる言語機能を使っている。型クラスを持つプログラミング言語として有名なのはHaskellだろう。 Rustを触ったことがある人は Rust のトレイトと似ていると感じる人がいるかもしれない。

型クラスはアドホック多相をサポートするための機能の一つだ。アドホック多相はポリモーフィズムの一種で、オブジェクト指向プログラミング言語の特徴の一つとして上げられることが多いが、オブジェクト指向の文脈ではサブタイピングを指すことが多いだろう。この辺りの用語や定義については一旦忘れてもらい、上記のコードが何を定義していて、このコードを使うと何ができるかを見てみよう。

先程のコードは 1 行目で、

scala

trait Semigroup[T]:

と書くことで Semigroup (半群) という型は何かしらの型 T を受け取る型ですよ、と宣言している。

そして2 行目では、

scala

extension (x: T) def combine(y: T): T

ある型 T は combine という名前で引数に型 T の値を受け取り、型 T の値を返すメソッドを持つ、と宣言している。

正確性には欠けるものの、以下のような対応が成り立つ。

Scala 3	数学
型 `T`	集合 $S$
メソッド `combine`	二項演算 $\circ$

「型 = 集合」という理解は正確ではないであるため、あくまで直観的にはこのような対応となっている、という点に注意して欲しい。

さて、改めて最初に見たコードを見直しみると、これはまさしく半群を定義していることがわかるだろう。

半群のインスタンス (Int, +)

半群がソースコード上で定義できたので、次はその例 (instance) を表現してみよう。 Scala 3 では以下のように書くことで型クラスのインスタンスを定義できる。

scala

1given Semigroup[Int] with
2  extension (x: Int) def combine(y: Int): Int = x + y

上記のコードは半群の例として見た整数上の加算を定義している。型クラスを定義したコードとの構文的な違いは trait と given 、 : と with 、メソッドの定義がされているあたりだろうか。

さて、この定義をすると Int 型の値に対してcombine が呼べるようになる。

scala

3.combine(4).combine(5)

3.combine(4).combine(5) は $(3 \circ 4) \circ 5$ に対応する。 Scala ではメソッド名に記号が使えるのに加えて、引数が一つのメソッドは二項演算子のように . や括弧を省略することができるため、次のように Semigroup に |+| メソッドを追加することで、

scala

1trait Semigroup[T]:
2  extension (x: T)
3    def combine(y: T): T
4    def |+|(y: T): T = combine(y)

より半群の定義で使った記法 (二項演算 $\circ$ ) に近づけることができる。この定義により以下のような呼び出しが可能となる。

scala

3 |+| 4 |+| 5

より二項演算が定義されている感じがするだろう。

半群のインスタンス (List[T], ++)

次に半群 (List[T], ++) を実装してみよう。半群の定義は既にしているため、インスタンスの実装を考えればよい。リストの場合は型パラメータを一つ受け取るため、 (Int, +) と少しだけ異なる構文を使わなければならない。

scala

1given listSemigroup[T]: Semigroup[List[T]] with
2  extension (x: List[T])
3    def combine(y: List[T]): List[T] = x ++ y

これにより、リストに対しても半群の二項演算が追加され、以下のようなコードを書ける。

scala

List(1, 2, 3) |+| List(4, 5)

リストの半群としてのインスタンスを定義したが大切なことを忘れている。それは (List[_], ++) が半群であるかどうかだ。 Scala 3 による Semigroup のインスタンスを定義する方法を見てもらうとわかるが、 combine メソッドを定義することができればコンパイルは通ってしまう。そのため、 List と二項演算 ++ の組合せが半群としての性質である結合律を満たすことはインスタンスがコンパイルに通ることと分けて考えなければならない。

リスト xs 、 ys 、 zs について、

scala

(xs ++ ys) ++ zs == xs ++ (ys ++ zs)

が成り立つことは直観的には正しいことがわかるだろう。証明についてはここでは省略する。

半群のインスタンス (Option[Semigroup[T]], |+|)

次に半群 (Option[Semigroup[T]], |+|) を考える。初めに断りを入れされてもらうとこの表記は正確ではない、がこの後の説明を読んでもらえれば何故このように書いたか理解してもらえると思う。

半群の台集合から見ていこう。この半群の台集合は Option[Semigroup[T]] だ。この表記は正確ではないが、直観としては Option[T] 型で T が特に半群であることを ~~表している~~ 表そうとしている。つまり、型 Option[T] の型変数部分である型 T が半群のときは、 Option[T] も半群にすることができるという主張だ。

それでは、二項演算について見てみよう。二項演算は |+| となっている。台集合が Option[T] であるから、二項演算の型は (Option[T], Option[T]) => Option[T] だ。結合律が満されるような定義のうち自然な定義は次のような演算だろうか。

None |+| None = None
None |+| Some(y) = None
Some(x) |+| None = None
Some(x) |+| Some(y) = ???

問題は最後のパターンだろう。この場合に型 T が半群であることを生かして次のように定義する。

Some(x) |+| Some(y) = x |+| y

ただし、右辺の |+| は半群 (T, |+|) で定義される |+| を使う。これによって、 (Option[Semigroup[T]], |+|) が半群となる。

ここで一つの疑問が浮ばないだろうか？ Some(x) |+| Some(y) = None と定義しても半群になるのでないかと？この疑問は今回の例に限らず、今までのすべての例で浮ぶ疑問だろう。半群の定義に従えば、そのような二項演算を定義しても半群となる。しかし、そのような半群を考えても有益な場合は少ないだろう。そのため、基本的には使い道のある自然な二項演算の定義だけが利用される。

今回の例では、複数の Option[T] 型の値が存在し、いずれか一つでも None が存在すれば計算結果全体が None となり、すべて Some であれば存在する値を自然な半群の定義による二項演算での計算結果を Some で包んで得られる。このような計算は恣意的なサンプル上のコードではなく、業務で書くようなコードでも現れるだろう。最も関数型プログラミングにおけるテクニックは単純なサンプルコードを見ても自身のコーディングに生かせるか気がつけるようになるまでの最初の一歩が難しいものではあると思う。

さて、 (Option[Semigroup[T]], |+|) の気持ちを理解できたところでScala 3 による実装を見てみよう。

scala

 1given optionSemigroup[T](using Semigroup[T]): Semigroup[Option[T]] with
 2  extension (x: Option[T])
 3    def combine(y: Option[T]): Option[T] = x match {
 4      case Some(a) =>
 5        y match {
 6          case Some(b) => Some(a |+| b)
 7          case None => None
 8        }
 9      case None => None
10    }

listSemigroup との違いは (using Semigroup[T]) だろう。 Scala 3 では、このように書くことで型 T に対して Semigroup のインスタンスが定義されている場合のみ、 Option[T] を Semigroup として扱うことができる。 combine の定義について先ほど説明した定義をそのまま素直にコードに落としただけである。型 T には Semigroup に対して定義されたメソッドが呼び出せるので、 Some(a |+| b) のように Semigroup に対して定義された二項演算を使って自然なコードが書ける。

この例より前に見てきた例は、すでに定義された演算を使って半群のインスタンスを実装していたが、今回の例では Scala に元からある二項演算をそのまま使うのではなく、結合律を満した上で有益な演算を考えて実装した。使った型は Option といった Scala に標準で定義さている型ではあるが、標準で用意されている型だけでなく自らが定義した型に対しても結合律を満すような演算が定義できるのであれば、 Semigroup のインスタンスを定義して利用することができる。 Semigroup だけでは加算や乗算のような単純な計算の延長上にあるようなことしかできないが、他の数学的な構造と組み合わせることでインスタンスを定義しただけで便利な操作を自動で手に入れられる。

おわりに

代数的構造の中でも単純な半群について見た。半群だけを考えても面白みは少ないが、

代数的構造とは何か
プログラミングへの活用
型クラスの定義、使い方

を最小の知識で学ぶことができる。それでも初めて代数学や型クラスに触れた人にとってはとっつき難いかもしれない。半群がプログラミングで役に立つのは、半群に対して単位元を加えたモノイドと Foldable のような型クラスの組合せを知ったときだろう。

わからないところがあれば気軽にコメントしてください。

参考URL

Semigroup