概要

Scala with Catsを日本語で要約してみた ~第1章イントロダクション~ の続き

Monoids and Semigroups

Integer addition

Intの加算は"閉じた"二項演算である。つまり2つのIntは常にIntを生成する
a + 0 == 0 + a == aというプロパティをもつ単位元(identity element)0がある
- 単位元
足す順番に関係なく同じ結果を常に得られるという、結合法則(associativity)がある¹
- 結合法則

(1 + 2) + 3 // 6
1 + (2 + 3) // 6

Integer multiplication

掛け算の場合、単位元が0ではなく1になる

1 * 3 // 3
3 * 1 // 3

掛け算は同じく結合法則がある

(1 * 2) * 3 // 6
1 * (2 * 3) // 6

String and sequence concatenation

文字列連結の単位元は空文字

"" + "Hello" // Hello
"Hello" + "" // Hello

文字列連結も結合法則がある

("One" ++ "Two") ++ "Three" //OneTwoThree
"One" ++ ("Two" ++ "Three") //OneTwoThree

Definition of a Monoid

Aのモノイドは以下の要素から成り立つ
- (A, A) => Aという組み合わせ(combine)操作
- Aの空要素

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

またモノイドのcombineとempty操作はいくつかの法則(laws)に従う必要がある
- combineは結合法則(associative)に、emptyは単位元の法則に従う

def associativeLaw[A](x: A, y: A, x: A)(implicit m: Monoid[A]): Boolean = {
  m.combine(x, combine(y, z)) == m.combine(m.combine(x, y), z)
}

def identityLaw[A](x: A)(implicit m: Monoid[A]): Boolean = {
  (m.combine(x, m.empty) == x) && (m.combine(m.empty, x) == x)
}

引き算は結合法則が成り立たないのでモノイドではない

(1 - 2) - 3 // -4
1 - (2 - 3) // 2

Definition of a Semigroup

Semigroup(半群)は、モノイドの結合(combine)部分のこと
多くのSemigroupはモノイドだが、Semigroupのデータ型の中には空要素(empty element)を定義できないものもある
- 例えば、空の要素を認めないnon-emptyなSequenceや正の数が制限された場合などは、emptyを定義できない
- CatsのNonEmptyListはSemigroupの実装だが、モノイドの実装ではない

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

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

Monoids in Cats

The Monoid Type Class

Monoidの型クラスはcats.kernel.Monoidで、cats.Monoidはそのエイリアス

Monoid Instances

cats.instancesパッケージにある
データ型によってパッケージが異なる

import cats.Monoid
import cats.instances.string._

Monoid[String].combine("Hello", " World") //Hello World
Monoid[String].empty // ""

Optionを使う場合Option内のデータ型と合わせてインポートする

import cats.Monoid
import cats.instances.int._
import cats.instances.option._

Monoid[Option[Int]].combine(Option(10), Option(20)) // Some(30)

Monoid Syntax

catsはcombineメソッドのSyntax(|+|)を用意している
使うにはcats.syntax.semigroupをインポートする

import cats.instances.string._
import cats.syntax.semigroup._

"Hello" |+| " World" |+| Monoid[String].empty // "Hello World"

Applications of Monoids

モノイドの概念は分かったが、こいつは便利なのか?

Big Data

SparkやHadoopのようなマシンをまたがり、フォールトトレランスかつスケーラブルな分散データ分析Big Dataのアプリケーションでは、各マシンは計算結果の一部を返すので、最終的にそれらを組み合わせる(combine)必要があるが、ほとんどの場合これはモノイドと見做すことができる
- サイトのトータルビジターの計算ならInt、ユニークユーザーならSet[User]、99%-95%のレスポンスタイムならQTreeのデータ型のモノイドで計算できる
大規模データセットに対する分析はほとんどがモノイドであるため、このアイデアで表現力豊かで強力な分析システムを構築できる
- TwitterのAlgebirdやSummingbirdはこれを行った

Distributed Systems

分散システムでは異なるマシンが異なるデータの見方で終わる可能性がある
- 例えば、あるマシンが他のマシンが受け取らなかったアップデートを受信する可能性がある
このようなマシン間のデータ差分は、これ以上更新がなければ同じデータを保持していることになる
これら結果整合性と呼ばれる(分散システム間で最終的にデータを同じにすること)
特定のデータ型は結果整合性の調整をサポートする。これらは可換複製データ型(CRDT)と呼ばれる
CRDTにおいて重要な操作は2つのインスタンスをマージする機能であり、その結果両方のインスタンスの情報がキャプチャされる
この2つのインスタンスをマージする機能はモノイドインスタンスをもつことに依存している

その他

TwitterのSummingbirdとモノイドに関してはこちらのブログでも紹介されています
- Hadoop/Storm の統合を実現する Twitter の SummingBird

結合律や結合則とも言う ↩