Scala with Catsを日本語で要約してみた ~第2章 Monoids and Semigroups~

概要

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

---

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