Deep conversion of Map to TreeMap

Question

I need to convert arbitrary nested Map to TreeMap. Examples:

Map[Int, String] -> TreeMap[Int, String]
Map[Int, Map[Int, String]] -> TreeMap[Int, TreeMap[Int, String]]
... etc

I've got working solution with type gymnastics and implicit conversions, however I have problems with types

trait ToTreeMap[M[_, _], K, V] {
  type Result

  def treeMap(x: M[K, V]): TreeMap[K, Result]
}

trait LowerPriorityToTreeMap {
  implicit def plainMap[K, V](implicit ord: Ordering[K]): ToTreeMap[Map, K, V] =
    new ToTreeMap[Map, K, V] {
      type Result = V

      def treeMap(x: Map[K, V]): TreeMap[K, Result] = TreeMap(x.toArray: _*)
    }
}

object ToTreeMap extends LowerPriorityToTreeMap {
  implicit def nestedMap[K1, K2, V](implicit inner: ToTreeMap[Map, K2, V], ord: Ordering[K1]): ToTreeMap[Map, K1, Map[K2, V]] = {
    new ToTreeMap[Map, K1, Map[K2, V]] {
      type Result = TreeMap[K2, inner.Result]

      def treeMap(x: Map[K1, Map[K2, V]]): TreeMap[K1, Result] = TreeMap(x.mapValues(v => inner.treeMap(v)).toArray: _*)
    }
  }

  implicit class MapOps[K, V](map: Map[K, V]) {
    def asTreeMap(implicit as: ToTreeMap[Map, K, V]) = as.treeMap(map)
  }
}

This works fine, however type ToTreeMap[..]#Result doesn't match with TreeMap that I need

  import ToTreeMap._

  val map: Map[Int, Map[Int, Map[Int, String]]] =
    Map(
      1000 -> Map(
        100 -> Map(
          10 -> "aa",
          1 -> "bb"
        ),
        99 -> Map(
          10 -> "aa",
          1 -> "bb"
        )
      ),
      999 -> Map(
        100 -> Map(
          10 -> "aa",
          1 -> "bb"
        ),
        99 -> Map(
          10 -> "aa",
          1 -> "bb"
        )
      )
    )

  val m = Map(1 -> "aaa")

  println(map.asTreeMap)
  println(m.asTreeMap)

  // This line fails to compile
  val tm: TreeMap[Int, TreeMap[Int, TreeMap[Int, String]]] = map.asTreeMap

Any ideas how to do it properly?

Scalac picks correct type in this example: Two dimensional array as a function which is not too much different from this one as I think

I can solve this type problem with 'asIntanceOf' but I'd like to do it without this dirty hack.

Answer 1

You need to be sure not to throw away the Return values in your instance methods' return types:

trait ToTreeMap[M[_, _], K, V] {
  type Result

  def treeMap(x: M[K, V]): TreeMap[K, Result]
}

trait LowerPriorityToTreeMap {
  implicit def plainMap[K, V](
    implicit ord: Ordering[K]
  ): ToTreeMap[Map, K, V] { type Result = V } =
    new ToTreeMap[Map, K, V] {
      type Result = V

      def treeMap(x: Map[K, V]): TreeMap[K, Result] = TreeMap(x.toArray: _*)
    }
}

object ToTreeMap extends LowerPriorityToTreeMap {
  implicit def nestedMap[K1, K2, V](
    implicit inner: ToTreeMap[Map, K2, V], ord: Ordering[K1]
  ): ToTreeMap[Map, K1, Map[K2, V]] {
    type Result = TreeMap[K2, inner.Result]
  } = {
    new ToTreeMap[Map, K1, Map[K2, V]] {
      type Result = TreeMap[K2, inner.Result]

      def treeMap(x: Map[K1, Map[K2, V]]): TreeMap[K1, Result] =
        TreeMap(x.mapValues(v => inner.treeMap(v)).toArray: _*)
    }
  }

  implicit class MapOps[K, V](map: Map[K, V]) {
    def asTreeMap(implicit as: ToTreeMap[Map, K, V]) = as.treeMap(map)
  }
}

This works, and looks perfectly reasonable to me.