（追記あり）ScalaのMapをmapしてkeyが衝突するのを回避する方法

ScalaにはMapというデータ構造があり、辞書を表現している。

val m = Map("windy" -> "melt", "fizz" -> "buzz")
m("windy") // => "melt"

そして、Mapにはmapメソッドが生えていて、KeyとValueとの双方を一気に変換することができる:

val m = Map(0 -> "foo", 1 ->"bar", 2 -> "buzz")
val f = (n: Int) => n % 2
m map { case (k, v) => f(k) -> v }

しかしながら、Keyを変換するパターンではKeyが同じ値に投影されてしまって衝突してしまうことがある。上掲の例でもそうなり、値が消えてしまう:

m map { case (k, v) => f(k) -> v }
// res0: Map[Int, List[String]] = Map(0 -> "buzz", 1 -> "bar")

これを回避するために、catsのMonoidを使うことができる。

下準備として、値のほうを一時的にListでおく。

val m = Map((0, List("foo")), (1, List("bar")), (2, List("buzz")))
// m: Map[Int, List[String]] = Map(0 -> List("foo"), 1 -> List("bar"), 2 -> List("buzz"))

もちろん、このまま map しても値は消えてしまう:

// 値が消える
m map { case (k, v) => f(k) -> v }
// res0: Map[Int, List[String]] = Map(0 -> List("buzz"), 1 -> List("bar"))

ここでちょっとしたテクニックを使う。

Fがモノイドのとき、Map[_, F]もまたモノイドになる。
Listはモノイドなので、Map[_,List] もモノイドになる。
いちどSeq[Map[_, List[_]]]の形にmapしてからreduceすることで、Mapを再構成できる。

import cats._
import cats.implicits._
// いちどMapを挟み、その後でreduceする
m map { case (k, v) => Map(f(k) -> v) } reduce (_ |+| _)
// res1: Map[Int, List[String]] = Map(1 -> List("bar"), 0 -> List("foo", "buzz"))

ところで、val m0 = Map(0 -> "foo", 1 -> "bar", 2 -> "buzz")の状態からval m = Map(0 -> List("foo"), 1 -> List("bar"), 2 -> List("buzz")) にするのは、型さえあれば(ListはApplicativeだから)ほぼ自動的にできるはずだけれど、以下のように書かなくちゃいけない:

val m = m0.view.mapValues(_.pure[List]).toMap

まあ、これはしょうがないか。

追記（同日）

がくぞさんからこういう便利メソッドあるよと教えていただいた。mapとreduceとが連続するときはfoldMapに押し込められるようだ。

map(...).reduce(...) が連続するときは foldMap も便利です。https://t.co/wcBFT8Cr9J https://t.co/Qic4NwlrBb pic.twitter.com/dDZLScsBwO
— がくぞ (@gakuzzzz) 2022年6月13日

import cats._
import cats.implicits._

val f = (n: Int) => n % 2
// f: Int => Int = <function1>
val m = Map(0 -> "foo", 1 -> "bar", 2 -> "buzz")
// m: Map[Int, String] = Map(0 -> "foo", 1 -> "bar", 2 -> "buzz")
val result = m.toSeq.foldMap { case k -> v => Map(f(k) -> List(v)) }
// result: Map[Int, List[String]] = Map(0 -> List("foo", "buzz"), 1 -> List("bar"))
println(result)
// Map(0 -> List(foo, buzz), 1 -> List(bar))

ところでreduceする過程でListのconcatが発生する。Listのconcatは $O(n)$ のコストが発生するので、場合によってはよりコストが安いChainも検討できるとのことだった。ChainはCatsが導入するデータ型で、prependとappendとが $O(1)$ で実行できるListのようなもの。

typelevel.org

Chainを使うだけで、ほぼコードは変化しない:

import cats._
import cats.implicits._
import cats.data.Chain
val f = (n: Int) => n % 2
// f: Int => Int = <function1>
val m = Map(0 -> "foo", 1 -> "bar", 2 -> "buzz")
// m: Map[Int, String] = Map(0 -> "foo", 1 -> "bar", 2 -> "buzz")
val result = m.toSeq.foldMap { case k -> v => Map(f(k) -> Chain(v)) }
// result: Map[Int, Chain[String]] = Map(0 -> Append(leftNE = Singleton(a = "foo"), rightNE = Singleton(a = "buzz")), 1 -> Singleton(a = "bar"))
println(result)
// Map(0 -> Chain(foo, buzz), 1 -> Chain(bar))

標準の関数groupMapを使うこともできるけど、この場合は2回分解しなければならない。

val f = (n: Int) => n % 2
// f: Int => Int = <function1>
val m = Map(0 -> "foo", 1 -> "bar", 2 -> "buzz")
// m: Map[Int, String] = Map(0 -> "foo", 1 -> "bar", 2 -> "buzz")
val result = m.groupMap { case (k, _) => f(k) } { case (_, v) => v }
// result: Map[Int, collection.immutable.Iterable[String]] = Map(0 -> List("foo", "buzz"), 1 -> List("bar"))