List[Monoid]同士を垂直結合させるようなMonoidが欲しいので作った

追記: 解決編から見よう

blog.3qe.us

最近型クラスまわりで遊んでいて、ちまちま応用例を見付けられているので嬉しい。

今回は、モノイドのリスト同士を結合することについて考えていきたい。

まずは下準備:

import cats._
import cats.implicits._

val xs = List(1, 2, 3)
// xs: List[Int] = List(1, 2, 3)
val ys = List(4, 5, 6)
// ys: List[Int] = List(4, 5, 6)
val zs = List(7, 8, 9)
// zs: List[Int] = List(7, 8, 9)

3つのInt (注: Intはモノイドだ) のリスト、 xs ys zs を用意した。これらを垂直に結合したい。垂直に、というのは、つまり同じインデックスの要素同士を足し合わせたい、ということである。この目的は、 zip と map によって達成できる:

xs zip ys
// res0: List[(Int, Int)] = List((1, 4), (2, 5), (3, 6))

xs.zip(ys).map(pair => pair._1 |+| pair._2)
// res1: List[Int] = List(5, 7, 9)

しかしこのままだと、複数のリストを結合するのが厄介だ。Intがモノイドであることを利用して、良い感じにリストを垂直結合できないだろうか？ちなみに F : Monoidのとき、List[F] は自動的にモノイドになるので、なにもせずにcombine関数を呼び出すことができる。(そもそも、リスト自体がモノイドだ)

xs |+| ys |+| zs
// => List(1, 2, 3, 4, 5, 6, 7, 8, 9)

もちろん、普通に combine すると水平にリストを結合してしまう。しょうがないので、自分で List[F : Monoid] がモノイドになることを証明する:

implicit def ListMonoidIsMonoid[F: Monoid]: Monoid[List[F]] =
  Monoid.instance(
    List.empty[F],
    { case (x, y) =>
      x.zipAll(y, Monoid[F].empty, Monoid[F].empty).map { case (xx, yy) =>
        xx |+| yy
      }
    }
  )

ListMonoidIsMonoid[Int].combine(xs, ys)
// res2: List[Int] = List(5, 7, 9)

// monoid law
val e = List[Int]()
// e: List[Int] = List()
ListMonoidIsMonoid[Int].combine(xs, e) == xs
// res3: Boolean = true
ListMonoidIsMonoid[Int].combine(e, xs) == xs
// res4: Boolean = true
ListMonoidIsMonoid[Int].combine(e, e) == e
// res5: Boolean = true
val leftwards = List(xs, ys, zs).foldLeft(ListMonoidIsMonoid[Int].empty) {
  case (x, y) => ListMonoidIsMonoid[Int].combine(x, y)
}
// leftwards: List[Int] = List(12, 15, 18)
val rightwards = List(xs, ys, zs).foldRight(ListMonoidIsMonoid[Int].empty) {
  case (x, y) => ListMonoidIsMonoid[Int].combine(x, y)
}
// rightwards: List[Int] = List(12, 15, 18)
leftwards == rightwards
// res6: Boolean = true

見たところ、すくなくともList[Int]についてモノイド則は満たせているようだ。モノイドにできたことで、combineAll を呼び出してリストをまとめて結合できるようになった:

ListMonoidIsMonoid[Int].combineAll(Seq(xs, ys, zs))
// res7: List[Int] = List(12, 15, 18)

本当はxs |+| ys |+| zsと書いたりSeq(xs, ys, zs).combineAll と書きたかったけれど、標準搭載のモノイドインスタンスを隠す方法がわからず、うまくsyntaxを使うことができなかった。任意のインスタンスを使いながらsyntaxを使う方法を知っている人がいたら教えてください。

そもそも、こういう用途はありふれていそうなので、既にインスタンスがcatsのどこかに定義されているかもしれない。知っていたら教えてください。