はじめに

こんにちは。マイクロアドでソフトウェアエンジニアをしている飛田と申します。私は主に UNIVERSE Ads というプロダクトの開発に携わっています。 UNIVERSE Ads では、より関数型ライクな設計や実装を取り入れることにより、高い保守性を目指しています。

この記事では、関数型プログラミングの入門的な話として、モノイドについて調べてみたので、この記事で共有させていただきたいと思います。

モノイドについてより深い理解をするために、まず、圏論と絡めたモノイドの説明をしたいと思います。そしてその次に、より理解を深めるために、Scala のサンプルコードを用いて、モノイドについて説明したいと思います。

圏論について全く知らない方は、下記のブログ記事で圏について説明していますので、よろしければご覧ください。

developers.microad.co.jp

モノイド

代数学

まず、モノイドの代数学的な説明をさせていただきます。

$X$ が集合であるとき、写像 $f: X \times X \rightarrow X$ のことを二項演算といいます。モノイドとは、以下の条件を満たす、組(X, f, e)のことです。

単位元といわれる元 $e \in X$ が存在し、すべての $a \in X$ に対し、 $f(a, e) = f(e, a) = a$ となる
すべての $a, b, c \in X$ に対し、 $f(f(a, b), c) = f(a, f(b, c))$ が成り立つ(結合法則)

次に、モノイドの例として、加算(二項演算) $+: Z \times Z \rightarrow Z$ が定義された整数 $Z$ について説明させていただきます。

整数 $Z$ は、上述したモノイドが満たすべき条件(1)(2)を以下のように満たします。

単位元 $0$ が存在し、すべての整数 $a$ に対し、 $a + 0 = 0 + a = a$ となる
すべての $a, b, c \in Z$ に対し、 $(a + b) + c = a + (b + c)$ が成り立つ(結合法則)

つまり、単位元 $0$ に関しては、どんな整数 $a$ と加算しても、整数 $a$ のままで、結合法則に関しては、加算の順序を問わないということです。

圏論

次に圏論と絡めたモノイドの説明をさせていただきます。

以下の条件を満たす、対象がただ 1 つだけの圏 $M$ をモノイドと言います。

恒等射 $id_M$ が存在し、任意の射 $f$ に対し $f \circ id_M = id_M \circ f = f$ を満たす
任意の射 $f, g, h$ が $h \circ (g \circ f) = (h \circ g) \circ f$ を満たす(結合法則)

先ほどの代数学的な説明では、単位元は $0$ つまり集合の要素ですが、圏論的な定義では、恒等射 $id_M$ として定義しました。このように圏として定義したモノイドは、「元や集合」の存在に先立って「射と対象」が主体となって定義されます。 *1

次に、モノイドの例として、整数の加算の圏について説明します。こちらの圏では、対象が整数で、射は与えられた整数に $n$ を加算する関数 $f_n$ を表しています。

f:id:tobita_yoshiki:20200419002559p:plain

射は結合法則を満たし、1を加算する射を $f_1$ 、2を加算する射を $f_2$ 、3を加算する射を $f_3$ とすると、 $(f_1 \circ f_2) \circ f_3 = f_1 \circ (f_2 \circ f_3)$ が成り立ちます。

また、この圏のただ一つの対象はの恒等射は 0 を加算する射 $id$ で、任意の射を $f$ とすると、 $id \circ f = f, f \circ id = f$ が成り立ちます。

「圏として定義したモノイドは対象ではなく射が主体となって定義されている」と上述しましたが、整数の加算の圏に関しても同様に、整数の加算が満たすべき条件(単位元に関する法則と結合法則)が主に射によって満たされています。このため、代数的な説明で行った整数 $n$ は、圏として定義したモノイドの射 $f_n$ と同一視することができるかと思います。

Scalaでモノイドを実装する

次にScalaでモノイドを実装してみましょう。以下はモノイドをScalaのコードで表したものです。

trait Monoid[A] {
  def combine(a1: A, a2: A): A // 二項演算
  def empty: A // 単位元
}

代数学的な定義に従った整数を加算するモノイドの実装

まず、代数学的な定義に従った整数を加算するモノイドの実装を示します。

// 整数を加算するモノイド
val intAdditionMonoid = new Monoid[Int] {
  def combine(x: Int, y: Int): Int = x + y
  def empty: Int = 0
}

val one = 1
val two = 2
val three = 3

// 単位元に関する法則
intAdditionMonoid.combine(one, intAdditionMonoid.empty) == one
intAdditionMonoid.combine(intAdditionMonoid.empty, one) == one

// 結合法則
intAdditionMonoid.combine(one, intAdditionMonoid.combine(two, three)) == intAdditionMonoid.combine(intAdditionMonoid.combine(one, two), three)

ソースコード中に単位元に関する法則と結合法則をチェックする記述がありますが、これは上記で代数学的なモノイドの定義で言及した数式に従って実装しています。

つまり、単位元に関する法則については「単位元 $e \in X$ が存在し、 $a \in X$ に対し、 $f(a, e) = f(e, a) = a$ となる」ということをチェックしていて、結合法則に関しては、「 $a, b, c \in Z$ に対し、 $(a + b) + c = a + (b + c)$ が成り立つ」が成り立つかどうかをチェックしています。*2

圏論的な定義に従った整数を加算するモノイドの実装

次に、圏論的な定義に従った整数を加算するモノイドの実装を示します。

case class IntAddition(a: Int) extends (Int => Int) {
  override def apply(x: Int): Int = x + a
  def unwrap: Int = a
  def compose(that: IntAddition): IntAddition = IntAddition(a + that.unwrap)
}

val intAdditionMonoidC = new Monoid[IntAddition] {
  def combine(x: IntAddition, y: IntAddition): IntAddition = x compose y
  def empty: IntAddition = IntAddition(0)
}

val f1 = IntAddition(1)
val f2 = IntAddition(2)
val f3 = IntAddition(3)

// 恒等射に関する法則
intAdditionMonoidC.combine(f1, intAdditionMonoidC.empty) == f1
intAdditionMonoidC.combine(intAdditionMonoidC.empty, f1) == f1

// 結合法則
intAdditionMonoidC.combine(f1, intAdditionMonoidC.combine(f2, f3)) == intAdditionMonoidC.combine(intAdditionMonoidC.combine(f1, f2), f3)

ソースコード中に恒等射に関する法則と結合法則をチェックする記述がありますが、これは上記で圏論的なモノイドの定義で言及した数式に従って実装しています。

つまり、恒等射に関する法則について「恒等射 $id_M$ が存在し、任意の射 $f$ に対し $f \circ id_M = id_M \circ f = f$ を満たす」ということをチェックしていて、結合法則に関しては、「任意の射 $f, g, h$ が結合法則 $h \circ (g \circ f) = (h \circ g) \circ f$ を満たす」ということをチェックしています。*3

モノイドの合成

ここで、複数モノイドを合成する方法について考えてみます。次に、圏 ${\bf C}, {\bf D}$ の直積の圏 ${\bf C} \times {\bf D}$ について考えてみます。

圏 $\bf C$ の対象を $C, C'$ 、圏 $\bf D$ の対象を $D, D'$ とすると、圏 ${\bf C} \times {\bf D}$ の対象には、順序対 $(C, D)$ および $(C', D')$ が存在して、射には $(C, D) \rightarrow (C', D')$ が存在することになります。

f:id:tobita_yoshiki:20200419020639p:plain — 直積の圏のイメージ

また、こちらの圏の恒等射は $1_{C, D} = (1_C, 1_D)$ で、射の合成は $(f, g) \circ (f', g') = (f \circ f', g \circ g')$ になります。

さらに、圏 ${\bf C}, {\bf D}$ がそれぞれモノイドである場合について考えてみます。

このとき、圏 ${\bf C}, {\bf D}$ はそれぞれ対象を1つしか持たないので、直積の圏 ${\bf C} \times {\bf D}$ も $(C, D)$ という唯一の対象しか持たなくなります。したがって、圏 ${\bf C}, {\bf D}$ がモノイドであれば、直積の圏 ${\bf C} \times {\bf D}$ もモノイドになります。

このようにモノイドは、モノイド同士で合成することができます。

Catsによるモノイドの利用例

モノイドの利用例として、複数モノイドの畳み込み処理について説明させていただきます。なるべく実務で書くようなソースコードに近い利用例を示すために、ソースコードにはCatsというライブラリを用いました。

Catsでは、モノイドは以下のように定義されており、combineとemptyメソッドを持ちます。*4

trait Semigroup[A] {
  def combine(x: A, y: A): A
}

trait Monoid[A] extends Semigroup[A] {
  def empty: A
}

以下は、モノイドを合成する処理と複数モノイドを畳み込む処理です。 *5

// モノイドの合成
def productMonoid[A,B](A: Monoid[A], B: Monoid[B]): Monoid[(A, B)] =
  new Monoid[(A, B)] {
    def combine(x: (A, B), y: (A, B)): (A, B) =
      (A.combine(x._1, y._1), B.combine(x._2, y._2))
    val empty: (A, B) = (A.empty, B.empty)
  }

// 平均値を求める(複数モノイドを畳み込む)
def mean(nums: List[Int]): Double = {
  val m = productMonoid(intAdditionMonoid, intAdditionMonoid)
  val p = foldMap(nums)(a => (1, a))(m)
  p._2 / p._1.toDouble
}

// 説明のためfoldMapを自前実装しましたが、CatsのFoldable#foldMapを使えば同じことができます
def foldMap[A, B](as :List[A])(f: A => B)(mb: Monoid[B]): B =
  as.foldLeft(mb.empty)((b, a) => mb.combine(b, f(a)))

mean(List(1, 2, 3, 4)) // 2.5

このように、複数のモノイドを1つに合成することによって、データ構造を畳み込むときに複数の計算を同時に実行することが可能になります。 (ケースバイケースですが)「一度に複数の計算を同時にやる」より「走査を2度やる」方が計算コストが高くつくため、モノイドが複数存在する場合は合成した方がパフォーマンス的に良くなります。

// 2回の走査で平均値の求める
val xs = List(1, 2, 3, 4) 
val mean = xs.foldLeft(0)(_ + _) / xs.foldLeft(0){(x, _) => x + 1}.toDouble

おわりに

ご覧いただき、ありがとうございました。

今後、関数型ライクな思考や圏論を理解し、プロダクトの実装に取り入れて、より良い広告配信システムを作っていきたいと思います。

マイクロアドでは「広告配信システムをつくりたい！」「関数型プログラミング言語をガンガン使っていきたい！」「圏論を理解できるようになりたい！」というエンジニアを積極的に募集しています。ご興味を持たれた方はこちらから是非ご応募下さい！

recruit.microad.co.jp

*1:このことに関してはモノイドに限った話ではなくて、一般的に圏に関しても言えるかと思います。

*2:ソースコードでは1, 2, 3などの特定の数値のみをテストデータに用いて単位元に関する法則と結合法則をテストしていますが、ScalaCheckなどのライブラリを用いてランダムに生成された値をテストデータに使用して、より正確なテストをすべきだと思います。モノイドの話を脱線させないために、ここではScalaCheckの話を割愛しました。

*3:ソースコードでは1, 2, 3などの特定の数値のみをテストデータに用いて単位元に関する法則と結合法則をテストしていますが、ScalaCheckなどのライブラリを用いてランダムに生成された値をテストデータに使用して、より正確なテストをすべきだと思います。モノイドの話を脱線させないために、ここではScalaCheckの話を割愛しました。

*4:実際のCatsのMonoidのソースコードを簡略化して掲載しています

*5:ソースコードはhttps://github.com/fpinscala/fpinscalaから引用、一部改変