Scala with Cats 輪読会 第ニ回ノート
tl;dr
e_ntyo.icon が書きました。
このページは、Scala with Cats 輪読会 の第ニ回(2 Monoids and Semigroups)でカバーされる箇所をe_ntyoが読み、重要な箇所をノートとしてまとめたものです。次回以降の担当者はこれにならって(あるいは反面教師として)ノートを事前に作成するようにしてください。 2 Monoids and Semigroups
前回 は、Cats (Scala)における型クラスのつくりかた・つかいかたを、Eq, Showという2つの型クラスを例にとって見てきた。今回は Monoids と Semigroups の 2 つを取り上げる。 2.1 Definition of a Monoid
まずは Monoid。
code:monoid.scala
def combine(x: A, y: A): A
def empty: A
}
combine は 型 Aの値 2 つを「くっつける」関数であり(この表現はすごくHな本から引用 )、 empty は「くっつけると消える」値である。 例: Monoid[Int]
code:monoid-int.scala
package MonoidInstances
import cats.kernel.Monoid
object MonoidInstances {
implicit val intAddMonoid = new MonoidInt { def combine(x: Int, y: Int): Int = x + y;
def empty: Int = 0
}
}
Int の場合、「くっつける」演算足し算と掛け算である(いわゆる「線型結合」)。足し算の場合は0が、掛け算の場合は1が、それぞれ「くっつけると消える値」(いわゆる単位元)である。天下り的ではあるが、実はこの単位元は one or nothing (1つだけあるか、ないか) であるので、 def empty: A = ... というシグネチャで問題ない。
Int の他には、String なんかも Monoid である。
例: Monoid[String]
code:monoid-string.scala
package MonoidInstances
import cats.kernel.Monoid
object MonoidInstances {
implicit val stringMonoid = new MonoidString { def combine(x: String, y: String): String = x ++ y;
def empty: Int = ""
}
}
ここで単位元の件に次ぐ重大天下り的新事実導入のコーナーであるが、実はただ「それっぽく」combineとemptyを実装すればよい、というわけではなく、厳密にMonoid であるためには、combine は associativity を、 empty は identity をそれぞれ満たす必要がある。
code:monoid-raw.scala
def associativeLawA(x: A, y: A, z: A)(implicit m: MonoidA): Boolean = { m.combine(x, m.combine(y, z)) == m.combine(m.combine(x, y), z)
}
def identityLawA(x: A)(implicit m: MonoidA): Boolean = { (m.combine(x, m.empty) == x) && (m.combine(m.empty, x) == x)
}
上記の Scala コードで考えると、Monoid[A] を実装する上で、 いかなる A の値についても associativeLaw と identityLaw が True を返すような実装にしなければならない、ということである。(※これはScala with Cats に書いてあるわけではなくe_ntyo.iconの戯言であるが、まさに fast-check のような Property Based Testing の出番であるといえそうだ。)自前の型の Monoid を実装する時は注意したい。
2.2 Definition of a Semigroup
Monoid のことを理解していれば、 Semigroup のことを理解するのは簡単。なぜなら、Semigroup と Monoid は実は以下のような関係だから。
code:semigroup.scala
def combine(x: A, y: A): A
}
trait MonoidA extends SemigroupA { def empty: A
}
Monoid[A] とは、実は Semigroup[A] の定義を拡張したものだったのである。したがって、すべての Monoid[A] は Semigroup[A] でもある。Semigroup[A] は定義できるが Monoid[A] は定義できないような A の例としては、NonEmptyArray や NonEmptyStringなどがある。
2.5 Monoids in Cats
では、 Cats における Monoid の具体的な使い方を見ていくのだが、これがほとんど Eq, Show と同じようにして使うだけなので、コード例を引用しておしまいにする。
code:monoid-cats.scala
import cats.Monoid
import cats.instances.string._ // for Monoid
import cats.instances.int._ // for Monoid
import cats.instances.option._ // for Monoid
MonoidString.combine("Hi ", "there") // res0: String = "Hi there"
// res1: String = ""
MonoidInt.combine(32, 10) // res5: Int = 42
val a = Option(22)
val b = Option(20)
Monoid[OptionInt].combine(a, b) // res6: OptionInt = Some(42) import cats.syntax.semigroup._ // for |+|
val stringResult = "Hi " |+| "there" |+| MonoidString.empty // stringResult: String = "Hi there"
import cats.instances.int._ // for Monoid
val intResult = 1 |+| 2 |+| MonoidInt.empty // intResult: Int = 3
次に、2.5.4 Exercise: Adding All The Things をやってみる。
The cutting edge SuperAdder v3.5a-32 is the world’s first choice for adding together numbers. The main function in the program has signature def add(items: List[Int]): Int. In a tragic accident this code is deleted! Rewrite the method and save the day!
e_ntyo.iconまあ、add 書くだけなら Monoid の |+|(Monoid[A].combine()) を使わなくともこれでいいかなと思った
code:a.scala
package SuperAdder
import cats.instances.int._
object SuperAdder {
def add(items: ListInt): Int = { items.foldInt(0)((a, b) => a + b) // items.foldInt(0)((a, b) => MonoidInt.combine(a, b)) }
}
Now there is a use case for Monoids. We need a single method that adds Ints and instances of Option[Int]. We can write this as a generic method that accepts an implicit Monoid as a parameter:
add が List[A] の総和を求める関数であってほしいので、ここで Monoid を使って抽象化する必要がありそう。
code:b.scala
object SuperAdder {
def addA(items: ListA)(implicit fa: MonoidA): A = { items.foldA(fa.empty)((a, b) => fa.combine(a, b)) }
}
A = Option[Int] のときは、以下のようにして使う
code:c.scala
import cats.instances.option._ // for Monoid
SuperAdder.add(List(Some(1), None, Some(2), None, Some(3)))
SuperAdder is entering the POS (point-of-sale, not the other POS) market. Now we want to add up Orders:
case class Order(totalCost: Double, quantity: Double)
最後は独自型の Monoid Instance を実装して、そいつを fold せよ的なこと。
まずは Monoid Instance。
code:d.scala
import cats.kernel.Monoid
import POSOrder.{POSOrder}
object MonoidInstances {
implicit val orderMonoid = new MonoidPOSOrder { def combine(x: POSOrder, y: POSOrder): POSOrder =
new POSOrder(x.totalCost + y.totalCost, x.quantity + y.quantity)
def empty: POSOrder = new POSOrder(0, 0)
}
}
今回は何もしていないけれど、先に挙げた associativeLaw と identityLaw を満たしているか注意されたし。 使うのは簡単。
code:e.scala
import MonoidInstances._
import POSOrder._
println(add(List(new POSOrder(100, 3), new POSOrder(300, 3), new POSOrder(0, 0))))
2.6 Applications of Monoids
モノイドの応用例について。
2.6 モノイドの応用
これで、モノイドとは何か、つまり加算または結合の概念を抽象化したものがわかりましたが、どこで役立つのでしょうか。ここに、モノイドが主要な役割を果たすいくつかの大きなアイデアがあります。これらについては、本の後半のケーススタディで詳しく説明します。
2.6.1 ビッグデータ
SparkやHadoopなどのビッグデータアプリケーションでは、データ分析を多くのマシンに分散し、フォールトトレランスとスケーラビリティを提供します。つまり、各マシンはデータの一部について結果を返します。次に、これらの結果を組み合わせて最終結果を取得する必要があります。ほとんどの場合、これはモノイドと見なすことができます。
Webサイトが受け取った訪問者の総数を計算する場合、それはIntデータの各部分でを計算することを意味します。のモノイドインスタンスIntは加算であることがわかっています。これは、部分的な結果を組み合わせる正しい方法です。
Web サイトが受け取ったユニークビジターの数を知りたい場合、Set[User]はデータの各部分に基づいて構築することと同じです。Setのモノイドインスタンスは集合和集合であることがわかっています。これは、部分的な結果を組み合わせる正しい方法です。
サーバーログから99%と95%の応答時間を計算する場合QTreeは、モノイドが存在するaと呼ばれるデータ構造を使用できます。
うまくいけば、あなたはアイデアを得るでしょう。大規模なデータセットに対して実行する可能性のあるほとんどすべての分析はモノイドであるため、このアイデアに基づいて表現力豊かで強力な分析システムを構築できます。これはまさにTwitterのAlgebirdおよびSummingbirdプロジェクトが行ったことです。このアイデアについては、map-reduceのケーススタディでさらに詳しく説明します。
2.6.2 分散システム
分散システムでは、マシンが異なれば、データのビューも異なる可能性があります。たとえば、あるマシンが他のマシンが受信しなかった更新を受信する場合があります。これらの異なるビューを調整して、更新が到着しなくなった場合にすべてのマシンが同じデータを持つようにします。これは結果整合性と呼ばれます。
特定のクラスのデータ型がこの調整をサポートします。これらのデータ型は、可換複製データ型(CRDT)と呼ばれます。重要な操作は、2つのデータインスタンスをマージする機能であり、その結果、両方のインスタンスのすべての情報がキャプチャされます。この操作は、モノイドインスタンスを持つことに依存しています。このアイデアについては、CRDTのケーススタディでさらに詳しく説明します。
map-reduce ケーススタディの章は輪読会ではやらないつもり(ケーススタディは教養としてはいいかもしれんが普段hubの開発する分にはいらんかなと思うので各自で)なので、ちょっと捕捉。
SparkやHadoopなどのビッグデータアプリケーションでは、データ分析を多くのマシンに分散し、フォールトトレランスとスケーラビリティを提供します。つまり、各マシンはデータの一部について結果を返します。次に、これらの結果を組み合わせて最終結果を取得する必要があります。ほとんどの場合、これはモノイドと見なすことができます。
> Webサイトが受け取った訪問者の総数を計算する場合、それはIntデータの各部分でを計算することを意味します。のモノイドインスタンスIntは加算であることがわかっています。これは、部分的な結果を組み合わせる正しい方法です。
e_ntyo.icon これちょうど大学の講習でやった。例えばTwitterの過去ツイートの巨大なアーカイブがあったとき、「『ゆれ』みたいな単語が比較的多く含まれている時間帯は、過去に本当に地震があった時間帯とどの程度一致するか」みたいなことを俺みたいな学生が大量にいて各々で検証しようと思うと、大学としては Hadoop みたいなやつを提供することで上に書いてある通りのメリット(計算機クラスタや分散システムを使う上で、デカいデータを分割して各マシン上でmap的な処理を実行→各実行結果をまとめてreduce的な処理を実行だと効率とかいろいろ良い)を得られる。Hadoop には map-reducer 的なジョブを走らせるのだが、map は Functor が提供するし、reducer は Monoid が提供できるんでいいよねという話だと思う。 Functor は次回やります。
追記
kgtkr.iconさんが貼ってくださった Monoid とマグマ、半群などの比較表
https://gyazo.com/606c96726fcb515fd437b050aced51f7