Yokohama.scala 第一回

0.md

Monoid で 集約操作を簡単に

Yokohama.scala 2018/06/16 At 株式会社アットウェア

自己紹介

• 中村 学(Nakamura Manabu)
• @gakuzzzz
• Tech to Value 代表取締役
• Opt Technologies 技術顧問
• F-CODE CTO

前提コード

case class Article(
  id: ArticleId, 
  subject: Subject,
  body: Body,
  createdAt: DateTime, 
  category: Category
)

最初の仕様

• 全記事で lastVisitTime 以降に作成された記事の件数を出したい。
• 各カテゴリ毎に、lastVisitTime 以降に作成された記事の件数を出したい。
• 各カテゴリ毎に記事の集合を出したい。

val articles: List[Article] = ...
val lastVisitTime: DateTime = ...
type NewArticleCount = Int

val totalCount: NewArticleCount = ...
val byCategory: Map[Category, (NewArticleCount, List[Article])] = ... 

手続き的に書き下してみる

val newArticleCount: NewArticleCount = articles
  .count(_.createdAt > lastVisitTime)

val newArticleCountByCategory: 
     Map[Category, (NewArticleCount, List[Article])] = articles
  .groupBy(_.category)
  .mapValues(list => (list.count(_.createdAt > lastVisitTime), list))

Monoid を使ってみる

Monoid とは

ループで遊ぼう

以下の性質を満たす集合と2項演算の組み合わせ

* 演算結果も集合の要素である(演算に対し閉じている)
    基本的に集合は型で表す
    つまり引数の型と戻り値の型が同じという事
* 演算が結合法則を満たす
    a, b, c を集合の要素として、演算を |+| とした時
    (a |+| b) |+| c == a |+| (b |+| c) が成り立つという事
    交換法則(可換則) ではない事に注意
* 単位元が存在する
    e |+| a == a
    a == a |+| e
    全ての要素に対して上記が成り立つ e が存在するという事

これをコードにすると以下の様になります

trait Monoid[A] {
  def zero: A
  def plus(v1: A, v2: A): A
}

implicit val intAdd: Monoid[Int] = new Monoid[Int] {
  def zero: Int = 0
  def plus(v1: Int, v2: Int): Int = v1 + v2
}

implicit def listConcat[A]: Monoid[List[A]] = new Monoid[List[A]] {
  def zero: List[A] = Nil
  def plus(v1: List[A], v2: List[A]): List[A] = v1 ++ v2
}

foldMap を使うと、集合に対して操作するのが簡単になります。

def foldMap[A, B](list: List[A])(f: A => B)(implicit m: Monoid[B]): B = {
  list.foldLeft(m.zero) { (b, a) => m.plus(b, f(a)) } 
}

foldMap(List("a", "b", "c"))(_.size) // 1 + 1 + 1  ---> 3

foldMap(List("a", "b", "c")) { v => List(v, v) }
  // List("a", "a") ++ List("b", "b") ++ List("c", "c")
  // ---> List("a", "a", "b", "b", "c", "c")

何がうれしいの？

Monoidは合成できる

// Monoid[A] と Monoid[B] から Monoid[(A, B)] が作れます
implicit def tuple2Monoid[A, B](implicit ma: Monoid[A], mb: Monoid[B]): Monoid[(A, B)] = {
  new Monoid[(A, B)] {
    def zero: (A, B) = (ma.zero, mb.zero)
    def plus(v1: (A, B), v2: (A, B)): (A, B) = {
      val ((v1a, v1b), (v2a, v2b)) = (v1, v2)
      (ma.plus(v1a, v2a), mb.plus(v1b, v2b))
    }
  }
}

// Monoid[A] から Monoid[Map[K, A]] が作れます
// Map同士を足してKeyが衝突する場合にValueをMonoid演算する形になります。
implicit def mapMonoid[K, A](implicit ma: Monoid[A]): Monoid[Map[K, A]] = {
  new Monoid[Map[K, A]] {
    def zero: Map[K, A] = Map()
    def plus(v1: Map[K, A], v2: Map[K, A]): Map[K, A] = {
      v1.foldLeft(v2) { case (acc, (k, v)) =>
        acc.updated(k, ma.plus(x, acc.get(k) orElse ma.zero))
      }
    }
  }
}

これを使うと「グループ毎に集約したい」という処理をfoldMapで書けます

val articles: List[Article] = ...
val lastVisitTime: DateTime = ...
type NewArticleCount = Int

val byCategory: Map[Category, (NewArticleCount, List[Article])] = 
  foldMap(articles) { article =>
    val newCount = if (article.createdAt > lastVisitTime) 1 else 0
    Map(article.category -> (newCount, List(article)))
  }

さらに言えば、totalCount と byCategory も、ひとつの foldMap で得る事ができます。

val (totalCount, byCategory) = foldMap(articles) { article =>
  val newCount = if (article.createdAt > lastVisitTime) 1 else 0
  (newCount, Map(article.category -> (newCount, List(article))))
}

最初のコードと比較すると

val newArticleCount = articles
  .count(_.createdAt > lastVisitTime)

val newArticleCountByCategory: = articles
  .groupBy(_.category)
  .mapValues(list => (list.count(_.createdAt > lastVisitTime), list))

まとめ

• 型クラスは合成するのが簡単
• Monoidを合成することで、複数の集約処理を一度の走査で実現できる