title: Deep conversion of Map to TreeMap
body: <p>I need to convert arbitrary nested Map to TreeMap. Examples:</p>
  
  <pre><code>Map[Int, String] -&gt; TreeMap[Int, String]
  Map[Int, Map[Int, String]] -&gt; TreeMap[Int, TreeMap[Int, String]]
  ... etc
  </code></pre>
  
  <p>I've got working solution with type gymnastics and implicit conversions, however I have problems with types</p>
  
  <pre><code>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 =&gt; inner.treeMap(v)).toArray: _*)
      }
    }
  
    implicit class MapOps[K, V](map: Map[K, V]) {
      def asTreeMap(implicit as: ToTreeMap[Map, K, V]) = as.treeMap(map)
    }
  }
  </code></pre>
  
  <p>This works fine, however type ToTreeMap[..]#Result doesn't match with TreeMap that I need</p>
  
  <pre><code>  import ToTreeMap._
  
    val map: Map[Int, Map[Int, Map[Int, String]]] =
      Map(
        1000 -&gt; Map(
          100 -&gt; Map(
            10 -&gt; "aa",
            1 -&gt; "bb"
          ),
          99 -&gt; Map(
            10 -&gt; "aa",
            1 -&gt; "bb"
          )
        ),
        999 -&gt; Map(
          100 -&gt; Map(
            10 -&gt; "aa",
            1 -&gt; "bb"
          ),
          99 -&gt; Map(
            10 -&gt; "aa",
            1 -&gt; "bb"
          )
        )
      )
  
    val m = Map(1 -&gt; "aaa")
  
    println(map.asTreeMap)
    println(m.asTreeMap)
  
    // This line fails to compile
    val tm: TreeMap[Int, TreeMap[Int, TreeMap[Int, String]]] = map.asTreeMap
  </code></pre>
  
  <p>Any ideas how to do it properly?</p>
  
  <p>Scalac picks correct type in this example: <a href="https://stackoverflow.com/questions/26848093/two-dimensional-array-as-a-function/26849903#26849903">Two dimensional array as a function</a> which is not too much different from this one as I  think</p>
  
  <p>I can solve this type problem with 'asIntanceOf' but I'd like to do it without this dirty hack.</p>