（追記あり）List[Monoid]同士を垂直結合させるためにMonoidを作る必要はなかった・・・

モノイドからなるリストのリストを垂直に結合したい。

tl;dr
「ZipListってのがあるよ」
順にやってみる
- Parallel登場
追記

まずは下準備:

import cats._
import cats.implicits._

// こいつらをぜんぶくっつけたい
val xs = (1 to 9).toList
// xs: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
val ys = (1 to 9).toList
// ys: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
val zs = (1 to 9).toList
// zs: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
val lis = List(xs, ys, zs)
// lis: List[List[Int]] = List(List(1, 2, 3, 4, 5, 6, 7, 8, 9), List(1, 2, 3, 4, 5, 6, 7, 8, 9), List(1, 2, 3, 4, 5, 6, 7, 8, 9))

素朴にcombineAllするとリストは単純に結合されてしまう。

lis.combineAll
// res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9)

ここまでは前回と同じ。

blog.3qe.us

自前でMonoidを作ったらList同士を垂直に結合できることがわかった

tl;dr

で、もうちょっとがんばってみました。

Parallel変換したらスッキリいけるよ
でもNonEmptyList挟むから結局そんなにスッキリしないよ

「ZipListってのがあるよ」

あと、一応 cats 標準に ZipList というラッパー型が存在してます。https://t.co/lGLO6V9NX1
— がくぞ (@gakuzzzz) 2022年6月7日

ZipList というそのものずばりの型があることを教えていただいた。ので、今回はこれを使ってうまく料理する。

順にやってみる

ここで便利データ構造であるZipListを使う。ZipListはApplyなので、ap(<*>)を使うことができる。 apは、複数のZipListから1要素ずつ取り出して関数に適用するという振舞いをとる。

import cats.data.ZipList
val f = (x: Int) => (y: Int) => x + y
// f: Int => Int => Int = <function1>
val zlisAp =
  ZipList(List(f, f, f)) <*> ZipList(xs) <*> ZipList(ys)
// zlisAp: ZipList[Int] = cats.data.ZipList@eadf1da
zlisAp.value
// res1: List[Int] = List(2, 4, 6)

すごい。結構便利そうだ。

ちなみに通常のListにapするとCartesian productになり、各要素の全ての組を取り出そうとする。試しに2つのIntを乗算する g を定義してapしてみよう。

val g = (x: Int) => (y: Int) => x * y
// g: Int => Int => Int = <function1>
val kuku = List(g) <*> xs <*> ys
// kuku: List[Int] = List(
//   1,
//   2,
//   3,
//   4,
//   5,
//   6,
//   7,
//   8,
//   9,
//   2,
//   4,
//   6,
//   8,
//   10,
//   12,
//   14,
//   16,
//   18,
//   3,
//   6,
//   9,
//   12,
//   15,
//   18,
//   21,
//   24,
//   27,
//   4,
//   8,
//   12,
//   16,
//   20,
//   24,
//   28,
//   32,
//   36,
//   5,
//   10,
//   15,
//   20,
//   25,
//   30,
//   35,
//   40,
//   45,
//   6,
//   12,
//   18,
// ...
kuku.grouped(9).toList
// res2: List[List[Int]] = List(
//   List(1, 2, 3, 4, 5, 6, 7, 8, 9),
//   List(2, 4, 6, 8, 10, 12, 14, 16, 18),
//   List(3, 6, 9, 12, 15, 18, 21, 24, 27),
//   List(4, 8, 12, 16, 20, 24, 28, 32, 36),
//   List(5, 10, 15, 20, 25, 30, 35, 40, 45),
//   List(6, 12, 18, 24, 30, 36, 42, 48, 54),
//   List(7, 14, 21, 28, 35, 42, 49, 56, 63),
//   List(8, 16, 24, 32, 40, 48, 56, 64, 72),
//   List(9, 18, 27, 36, 45, 54, 63, 72, 81)
// )

九九の表を生成してしまった。今回やりたいのはそういうことじゃないんだよね。

ところで、Apply単体ではZipListのリストを一気にreduceして畳み込むことができない。そこで、Applyにある便利機能を使う。 Apply.semigroupは、FがApplyで、AがSemigroupであるとき、Semigroup[F[A]]のインスタンスを導出できる。(なんでかって？わからない) 今回はZipListがApplyで、IntはSemigroupなので、ZipList[Int]がSemigroupになった。

implicit val ZipListIsSemigroup: Semigroup[ZipList[Int]] = Apply.semigroup
// ZipListIsSemigroup: Semigroup[ZipList[Int]] = cats.ApplySemigroup@996193b

// xs, ys, zsをZipListにして・・・
val zlis @ Seq(xsz, ysz, zsz) = lis map ZipList.apply
// zlis: List[ZipList[Int]] = List(cats.data.ZipList@51cd0da6, cats.data.ZipList@51cd0da6, cats.data.ZipList@51cd0da6)
// xsz: ZipList[Int] = cats.data.ZipList@51cd0da6
// ysz: ZipList[Int] = cats.data.ZipList@51cd0da6
// zsz: ZipList[Int] = cats.data.ZipList@51cd0da6

// xsz, ysz, zszはSemigroupになったので、直接combineできるようになった。
(xsz |+| ysz).value
// res3: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18)

combineできるということは、このまま一気にcombineAllしたいが、combineAllするにはMonoidである必要がある。空の場合のハンドリングが発生してしまうからだ。今回はSemigroupのインスタンスしか無いので、より制約の緩いかわりにOptionを返すcombineAllOptionを使う。

val result = zlis.combineAllOption
// result: Option[ZipList[Int]] = Some(value = cats.data.ZipList@bed1ec93)
result.map(_.value)
// res4: Option[List[Int]] = Some(value = List(3, 6, 9, 12, 15, 18, 21, 24, 27))

大成功。

ここまでをまとめよう。

いちどList xs, ys, zsをZipListに変換した。
List(xs, ys, zs) を作った。
Apply[ZipList[Int]]から導出したSemigroup[ZipList[Int]]を用いてcombineAllOptionを成功させた。
その後ZipListをListに戻し、結果の値を得た。

Parallel登場

ちなみに、ListとZipListはNonEmptyParallelの関係にある。一瞬 parallel な型に変換して戻す、という曲芸的な行為をやってくれるのがparなんとかメソッドだ。

自分もあまりParallelのことをわかっていないので、このへんの説明を読んでほしい・・・。

qiita.com

Catsの双子っぽい型って、Monad-ComonadみたいなDualとか、Parallelなやつとか、いろいろあるな・・・。(Parallelは自然変換できる関係っぽい？？)

val instance = implicitly[NonEmptyParallel[List]]
// instance: NonEmptyParallel[List] = cats.instances.ListInstances$$anon$3@60b64868
lis.map(instance.parallel(_))
// res5: List[instance.F[Int]] = List(cats.data.ZipList@51cd0da6, cats.data.ZipList@51cd0da6, cats.data.ZipList@51cd0da6)

// NonEmptyParallelに定義されているメソッドを呼ぶために、lisをNonEmptyListにしておくと、色々と便利な事が起こる:
import cats.data.NonEmptyList
NonEmptyList.fromListUnsafe(lis).parReduceMapA(NonEmptyList.fromListUnsafe(_))
// res6: NonEmptyList[Int] = NonEmptyList(head = 3, tail = List(6, 9, 12, 15, 18, 21, 24, 27))

あるいは最初から全てNonEmptyListにしておくと分かりやすい:

val nelxs = NonEmptyList.fromList((1 to 9).toList).get
// nelxs: NonEmptyList[Int] = NonEmptyList(head = 1, tail = List(2, 3, 4, 5, 6, 7, 8, 9))
val nelys = NonEmptyList.fromList((1 to 9).toList).get
// nelys: NonEmptyList[Int] = NonEmptyList(head = 1, tail = List(2, 3, 4, 5, 6, 7, 8, 9))
val nelzs = NonEmptyList.fromList((1 to 9).toList).get
// nelzs: NonEmptyList[Int] = NonEmptyList(head = 1, tail = List(2, 3, 4, 5, 6, 7, 8, 9))
val nel = NonEmptyList(nelxs, List(nelys, nelzs))
// nel: NonEmptyList[NonEmptyList[Int]] = NonEmptyList(
//   head = NonEmptyList(head = 1, tail = List(2, 3, 4, 5, 6, 7, 8, 9)),
//   tail = List(
//     NonEmptyList(head = 1, tail = List(2, 3, 4, 5, 6, 7, 8, 9)),
//     NonEmptyList(head = 1, tail = List(2, 3, 4, 5, 6, 7, 8, 9))
//   )
// )

nel.parReduceMapA(identity)
// res7: NonEmptyList[Int] = NonEmptyList(head = 3, tail = List(6, 9, 12, 15, 18, 21, 24, 27))

非常にシンプルだ。

parReduceMapは、いったんNonEmptyList中の要素をparallel変換してZipListにしたあと、NonEmptyList[ZipList]をmapし、それをSemigroupを使ってreduceする。mapしなくてもよいならidentityを渡せばよさそうだ。

ちょっと遊んでみよう:

nel.parReduceMapA(_.map(_.toString))
// res8: NonEmptyList[String] = NonEmptyList(head = "111", tail = List("222", "333", "444", "555", "666", "777", "888", "999"))
nel.parReduceMapA(_.reverse)
// res9: NonEmptyList[Int] = NonEmptyList(head = 27, tail = List(24, 21, 18, 15, 12, 9, 6, 3))

若干かっこよくZipListへの変換と取り出しを記述することができた。

ただし、Nelを挟む面倒さと比べると、lis map ZipList.applyするのとあまり変わらないと思う。

追記

Align 使うといけるよ派の方が登場して教えていただいた。

Align を使うと「縦に足す」と「xs |+| ys |+| zs ぽく書く」の両方のお題満たせるかな。

中で Ior 使ってる→長さが違えば足さない→単位元いらない→半群になってればOK、という意味でもモノイド要らなかった 💡 https://t.co/ep77Fq7gzN pic.twitter.com/z9pq0dGPED
— yasuabe (@yasuabe2613) 2022年6月13日

Align は、形が違っていてもなんとか結合するための型で、内部的にはIorのListのような振舞いをする。alignCombineを呼び出すことで、リストを横向きに結合する。

import cats._
import cats.implicits._

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

xs alignCombine ys alignCombine zs
// res0: List[Int] = List(12, 15, 18)
List(xs, ys, zs).reduce(_ alignCombine _)
// res1: List[Int] = List(12, 15, 18)