[Scala] Re: Mapの置換にみるジェネリクス表現

お題:

Map を Mapに変換するメソッドを作るという話題。

Mapの置換にみるジェネリクス表現 - プログラマーの脳みそ

元の話はJavaなんだけどScalaではできるかどうかやってみた。
バージョンはScala 2.11.2

ベースの実装

Javaのベースの実装

public static <K,V,
	R extends Map<V,K>,
	P extends Map<K,V>>
R swap2(P origin, Supplier<R> supplier) {
// 略
}

これをScalaに機械的に翻訳してみる。
Mapはとりあえずmutableなやつとして実装も書く。

  import scala.collection.mutable.Map
  def swap2[V, K, R <: Map[V, K], P <: Map[K, V]](origin: P, supplier: () => R): R = {
    val result = supplier()
    origin foreach (result += _.swap)
    result
  }

Mapはforeachすると(キー, 値)となるタプルを取り出せるのでキーと値をswapして結果に追加していくという実装です。
使う側

  import scala.collection.mutable.HashMap

  val original = HashMap("A" -> 123, "B" -> 456)
  val supplier = () => new HashMap[Int, String]

  val swap: HashMap[Int, String] = swap2[Int, String, HashMap[Int, String], HashMap[String, Int]](original, supplier)

ただしこれでは渡すのがListMapでも動く

  import scala.collection.mutable.HashMap
  import scala.collection.mutable.ListMap

  val original = ListMap("A" -> 123, "B" -> 456)
  val supplier = () => new HashMap[Int, String]

  val swap: HashMap[Int, String] = swap2[Int, String, HashMap[Int, String], ListMap[String, Int]](original, supplier)

型コンストラクタを使う

例えばHashMap[Int, String]でいうところのHashMapはそれ自体は具体型ではなく、型パラメータを受け取って具体型を返す、いわゆる「型コンストラクタ」といわれる。
(型コンストラクタについてはcf: (もりそば)Scalaによる高階型変数 - Higher-kind Generics - ( ꒪⌓꒪) ゆるよろ日記)

Scalaは型コンストラクタを型の宣言の中で扱えるようになっている。

  import scala.language.higherKinds

  def swap2[V, K, M[X, Y] <: Map[X, Y], R <: M[V, K], P <: M[K, V]](origin: P, supplier: () => R): R = {
    val result = supplier()
    origin foreach (result += _.swap)
    result
  }

この場合、型パラメータが二つある型コンストラクタMを取り、PがM[K, V]でRがM[V, K]であるということが表現できている。
ちなみにここに出てくるXとYはMapとMの型パラメータの対応付けに使われているだけなので気にしなくていいです。
呼び出し側

  import scala.collection.mutable.HashMap

  val original = HashMap("A" -> 123, "B" -> 456)
  val supplier = () => new HashMap[Int, String]

  val swap: HashMap[Int, String] = swap2[Int, String, HashMap, HashMap[Int, String], HashMap[String, Int]](original, supplier)

MがHashMapで、PとRにはそれぞれHashMap[String, Int]とHashMap[Int, String]を指定してるのでつじつまがあう。
ただし、共通の親クラスを指定してもコンパイルは通るので、最終的な型の型コンストラクタが一致してる保証にはならない。

  import scala.collection.mutable.HashMap
  import scala.collection.mutable.ListMap

  val original = ListMap("A" -> 123, "B" -> 456)
  val supplier = () => new HashMap[Int, String]

  val swap: HashMap[Int, String] = swap2[Int, String, Map, HashMap[Int, String], ListMap[String, Int]](original, supplier)

generalized type constraintsを使う

Scalaでは、型パラメータ間の制約をgeneralized type constraintsというので書けるようになっている。
(generalized type constraintsについてはcf: Scalaで<:<とか=:=を使ったgeneralized type constraintsがスゴすぎて感動した話 - ( ꒪⌓꒪) ゆるよろ日記)
暗黙の引数として制約を書くことでコンパイル時にチェックすることができる。

  def swap2[V, K, M[X, Y] <: Map[X, Y], R <: M[V, K], P <: M[K, V]](origin: P, supplier: () => R)(implicit ev1: P =:= M[K, V], ev2: R =:= M[V, K]): R = {
    val result = supplier()
    origin foreach (result += _.swap)
    result
  }

上の例では、PとM[K, V]が等しく、RとM[V, K]が等しいという制約になっている。
これを使って、具体型同士が等しいという制約を書けば上での共通の親クラスを指定して逃げることが防げる。

    import scala.collection.mutable.HashMap
    import scala.collection.mutable.ListMap

    val original = ListMap("A" -> 123, "B" -> 456)
    val supplier = () => new HashMap[Int, String]

    val swap: HashMap[Int, String] = swap2[Int, String, Map, HashMap[Int, String], ListMap[String, Int]](original, supplier)
    // 以下のようなエラーが出てコンパイルできない
    // Cannot prove that scala.collection.mutable.Map[Int,String] =:= scala.collection.mutable.HashMap[Int,String]

もっともPとRにも共通の親クラスを指定した場合はコンパイルは通ってしまう。

    val swap: Map[Int, String] = swap2[Int, String, Map, Map[Int, String], Map[String, Int]](original, supplier)

おまけ: CanBuildFromを使う

制約の話からはちょっと離れるけど。
ScalaでListやMapにmapを適用すると元のクラスと同じクラスが帰ってくる。

scala> val m1 = scala.collection.immutable.HashMap("A" -> 123, "B" -> 456)
m1: scala.collection.immutable.HashMap[String,Int] = Map(A -> 123, B -> 456)

scala> m1 map (_.swap)
res0: scala.collection.immutable.HashMap[Int,String] = Map(456 -> B, 123 -> A)

scala> val m2 = scala.collection.immutable.TreeMap("A" -> 123, "B" -> 456)
m2: scala.collection.immutable.TreeMap[String,Int] = Map(A -> 123, B -> 456)

scala> m2 map (_.swap)
res1: scala.collection.immutable.TreeMap[Int,String] = Map(123 -> A, 456 -> B)

scala> val l1 = List(("A", 123), ("B", 456))
l1: List[(String, Int)] = List((A,123), (B,456))

scala> l1 map (_.swap)
res2: List[(Int, String)] = List((123,A), (456,B))

これはmapメソッドが暗黙の引数としてCanBuildFromを受け取って戻り値の生成に使用することで実現している。

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {…

基本的なコレクションには対応するCanBuildFromが用意されているので自動的に戻りの型を合わせてくれている。
真似してみる。

  import scala.language.higherKinds
  import scala.collection.mutable.Builder
  import scala.collection.generic.CanBuildFrom

  def swap[M[X, Y] <: TraversableOnce[(X, Y)], T1, T2](a: M[T1, T2])(implicit bf: CanBuildFrom[M[T1, T2], (T2, T1), M[T2, T1]]): M[T2, T1] = {
    val b: Builder[(T2, T1), M[T2, T1]] = bf apply ()
    a foreach (b += _.swap)
    b.result
  }

動かしてみる。

scala> swap(scala.collection.immutable.HashMap("A" -> 123, "B" -> 456))
res0: scala.collection.immutable.HashMap[Int,String] = Map(456 -> B, 123 -> A)

scala> swap(scala.collection.immutable.TreeMap("A" -> 123, "B" -> 456))
res1: scala.collection.immutable.TreeMap[Int,String] = Map(123 -> A, 456 -> B)

scala> type ListOfTuple2[X, Y] = List[(X,Y)]
defined type alias ListOfTuple2

scala> swap(List(("A", 123), ("B", 456)): ListOfTuple2[String, Int])
res2: ListOfTuple2[Int,String] = List((123,A), (456,B))

Listはもともとは型パラメータ1つなので明示してやらないとダメっぽい。
↓でもいい。

scala> swap[({type λ[α, β] = List[(α, β)]})#λ, String, Int](List(("A", 123), ("B", 456)))
res3: List[(Int, String)] = List((123,A), (456,B))

おまけ2: コレクション以外でも使う

型パラメータを入れ替える汎用のtraitを作っていろいろな型で入れ替えられるようにする。

import scala.language.higherKinds
import scala.language.postfixOps

trait SwapTypeParams[A[_, _]] {
  def apply[T1, T2](a: A[T1, T2]): A[T2, T1]
}
object SwapTypeParams {
  def swap[M[_, _], T1, T2](x: M[T1, T2])(implicit op: SwapTypeParams[M]): M[T2, T1] = op.apply(x)
  def swap2of3[M[_, _, _], T1, T2, T3](x: M[T1, T2, T3])(implicit op: SwapTypeParams[({ type λ[α, β] = M[α, β, T3] })#λ]): M[T2, T1, T3] = op.apply(x)

  // Tuple用
  implicit def tuple2Swap = new SwapTypeParams[Tuple2] {
    def apply[T1, T2](t: Tuple2[T1, T2]): Tuple2[T2, T1] = t swap
  }
  // Map用
  implicit def mapSwap = new SwapTypeParams[Map] {
    def apply[T1, T2](m: Map[T1, T2]): Map[T2, T1] = m map (_ swap)
  }
  // HashMap用
  import scala.collection.immutable.HashMap  
  implicit def hashmapSwap = new SwapTypeParams[HashMap] {
    def apply[T1, T2](m: HashMap[T1, T2]): HashMap[T2, T1] = m map (_ swap)
  }
  // List用
  implicit def listOfTuple2Swap = new SwapTypeParams[({ type λ[α, β] = List[(α, β)] })#λ] {
    def apply[T1, T2](m: List[(T1, T2)]): List[(T2, T1)] = m map (_ swap)
  }
  // Function2用
  implicit def function2Swap[R] = new SwapTypeParams[({ type λ[α, β] = Function2[α, β, R] })#λ] {
    def apply[T1, T2](f: Function2[T1, T2, R]): Function2[T2, T1, R] = (v2: T2, v1: T1) => f(v1, v2)
  }

}

つかう

scala> import SwapTypeParams._
import SwapTypeParams._

scala> swap(("A",123))
res0: (Int, String) = (123,A)

scala> swap(Map("A" -> 123, "B" -> 456))
res1: scala.collection.immutable.Map[Int,String] = Map(123 -> A, 456 -> B)

scala> swap(scala.collection.immutable.HashMap("A" -> 123, "B" -> 456))
res2: scala.collection.immutable.HashMap[Int,String] = Map(456 -> B, 123 -> A)

scala> swap(scala.collection.immutable.TreeMap("A" -> 123, "B" -> 456))
<console>:17: error: could not find implicit value for parameter op: SwapTypeParams[scala.collection.immutable.TreeMap]
              swap(scala.collection.immutable.TreeMap("A" -> 123, "B" -> 456))
                  ^

scala> swap[({type λ[α, β] = List[(α, β)]})#λ, String, Int](List(("A", 123), ("B", 456)))
res3: List[(Int, String)] = List((123,A), (456,B))

scala> type ListOfTuple2[X, Y] = List[(X,Y)]
defined type alias ListOfTuple2

scala> swap(List(("A", 123), ("B", 456)): ListOfTuple2[String, Int])
res4: ListOfTuple2[Int,String] = List((123,A), (456,B))

scala> val swapped1 = swap[({type λ[α, β] = Function2[α, β, String]})#λ, String, Int](((str: String, n: Int) => str * n))
swapped1: (Int, String) => String = <function2>

scala> swapped1(10, "w")
res5: String = wwwwwwwwww

scala> type Function2String[X, Y] = Function2[X, Y, String]
defined type alias Function2String

scala> val swapped2 = swap(((str: String, n: Int) => str * n): Function2String[String, Int])
swapped2: Function2String[Int,String] = <function2>

scala> swapped2(10, "w")
res6: String = wwwwwwwwww

scala> val swapped3 = swap2of3((str: String, n: Int) => str * n)
swapped3: (Int, String) => String = <function2>

scala> swapped3(10, "w")
res7: String = wwwwwwwwww

まあ特に使い途は思いつかない。