Scalaで集合論・代数 半群(SemiGroup)【1】

まとめはこっち
　

半群とは？

　Scalaで集合論・代数、ということで第一回は半群（SemiGroup）について勉強します。
そもそも半群とは何か・・というと、

　群とか束とか環とかいった代数的構造から共通する性質を抜き出したもの

です。
　
　先ず代数的構造ってナニ？　となりますがそこはWikipedia様に譲るとします。
http://ja.wikipedia.org/wiki/%E4%BB%A3%E6%95%B0%E7%9A%84%E6%A7%8B%E9%80%A0
　
　具体的にどういう性質を持つかというと、
集合Sと演算*が与えられた時に、次の2つの条件を満たせば半群となります。
　

条件1.　集合Sが演算*に対して閉じている

　すなわち、S上の任意の元a, b に対して、演算結果 a * b は再び S に属する。

　

条件2.　集合S上の演算*は結合法則を満たす。

　すなわち、S上の任意の元a, b, c に対して、

　(a * b) * c = a * (b * c)

　

具体的には？

例1)
整数Z上の加法+を考える。
整数aと整数bを足して得られる数cは整数に属する。
また足し算は順序を入れ替えても結果は同じ。
(1 + 2) + 3 = 1 + (2 + 3)
よって整数Zと加法+の組、(Z, +)は半群。

例2)
非負整数N上の加法+、(N, +)を考える。
これも例1)と同じように半群である。
　
例3)
整数Zと乗法*の組

例4)
文字列と文字列の結合演算

他にもいっぱいいっぱいあります。

Scalaで実装してみよう

先の節の例1、整数Zと加法の組について実装します。
とりあえずJava風に書いてみます。

trait SemiGroup[S] {

  def append(a: S, b: S): S

}

 

object IntSemiGroup extends SemiGroup[Int] {

  def append(a: Int, b: Int) = a + b

}
val three = IntSemiGroup.append(1, 2)

『Sの元a, bに対して、演算結果もSに属する』
というのが、
『型Sの値2つを取って型Tの結果を返す』
ということに対応してるのが分かると思います。

さて、この実装では、条件2の結合法則については満たすことを保証できません。
あくまでもSemiGroupのインスタンスを作る人がその性質を満たすように作らねばなりません。
Haskellで型クラスMonadのインスタンスがモナド則満たさないように作れてしまうようなもん？

コード修正

さっきのコードは、Scalaならもっと綺麗に書けそうな気がします。

class SemiGroup[S](f: (S, S) => S) {

  def append(a: S, b: S) = f(a, b)

}

 

val three = new SemiGroup[Int](_ + _).append(1, 2)

コンストラクタに高階関数を渡す形になりました。
このほうが (Z, +)の形に近く見えるので直感的にもわかりやすい気がします。

文字列の結合についての半群なら

class SemiGroup[S](f: (S, S) => S) {

  def append(a: S, b: S) = f(a, b)

}

 

val abc = new SemiGroup[String](_ + _).append("a", "bc")

となります。

半群ではないものは？

これまで半群になるものばかり挙げて来ましたが、半群でないものを考えましょう。

負整数の集合と乗法を考えると、半群にはなりません。
負整数同士の乗算の結果は正整数なので、演算結果が元の集合に属しません。

case class NegativeInteger(i: Int) {

  if (i < 0)

    throw new IllegalArgumentException()

  

  def +(that: NegativeInteger) = 

    NegativeInteger(this.i + that.i)

}
// これは実行時エラー

val one = new SemiGroup[NegativeInteger](_ * _)

        .append(NegativeInteger(-1), NegativeInteger(-1))

参考：
wikipedia：半群
　
scalaz.Semigroup