Infering generic type parameters in Scala

Question

Hi, I've been trying to unify collection of nested maps. So I want to implement a method with signature:

def unifyMaps(seq: Seq[Map[String, Map[WordType, Int]]]): Map[String, Map[WordType, Int]]

(WordType is a Java Enum.) The first approach was to do manual map-merging.

def unifyMapsManually(seq: IndexedSeq[Map[String, Map[WordType, Int]]]): Map[String, Map[WordType, Int]] = {
  seq reduce { (acc, newMap) =>
    acc ++ newMap.map { case (k, v) =>
      val nestedMap = acc.getOrElse(k, Map.empty)
      k -> (nestedMap ++ v.map { case (k2, v2) => k2 -> (nestedMap.getOrElse(k2, 0) + v2) })
    }
  }
}

It works, but what I'm doing here is recursively applying the exact same pattern, so I thought I'd make a recursive-generic version. Second approach:

def unifyTwoMapsRecursively(m1: Map[String, Map[WordType, Int]], m2: Map[String, Map[WordType, Int]]): Map[String, Map[WordType, Int]] = {
  def unifyTwoMaps[K, V](nestedMapOps: (V, (V, V) => V))(m1: Map[K, V], m2: Map[K, V]): Map[K, V] = {
    nestedMapOps match {
      case (zero, add) =>
        m1 ++ m2.map { case (k, v) => k -> add(m1.getOrElse(k, zero), v) }
    }
  }
  val intOps = (0, (a: Int, b: Int) => a + b)
  val mapOps = (Map.empty[WordType, Int], unifyTwoMaps(intOps) _)
  unifyTwoMaps(mapOps)(m1, m2)
}

But it fails with:

Error:(90, 18) type mismatch;
 found   : (scala.collection.immutable.Map[pjn.wierzba.DictionaryCLP.WordType,Int], (Map[Nothing,Int], Map[Nothing,Int]) => Map[Nothing,Int])
 required: (scala.collection.immutable.Map[_ <: pjn.wierzba.DictionaryCLP.WordType, Int], (scala.collection.immutable.Map[_ <: pjn.wierzba.DictionaryCLP.WordType, Int], scala.collection.immutable.Map[_ <: pjn.wierzba.DictionaryCLP.WordType, Int]) => scala.collection.immutable.Map[_ <: pjn.wierzba.DictionaryCLP.WordType, Int])
    unifyTwoMaps(mapOps)(m1, m2)
                 ^

So ok, I have no idea about upper bound on map key, but the curried function clearly is not inferred correctly. I had similar error with intOps, so I tried to provide exact types:

val mapOps = (Map.empty[WordType, Int], unifyTwoMaps(intOps)(_: Map[String, Map[WordType, Int]], _: Map[String, Map[WordType, Int]]))

But this time it fails with:

Error:(89, 67) type mismatch;
 found   : Map[String,Map[pjn.wierzba.DictionaryCLP.WordType,Int]]
 required: Map[?,Int]
    val mapOps = (Map.empty[WordType, Int], unifyTwoMaps(intOps)(_: Map[String, Map[WordType, Int]], _: Map[String, Map[WordType, Int]]))
                                                                  ^

And this time I have absolutely no idea what to try next to get it working.

EDIT: I've found solution to my problem, but I'm still wondering why do I get type mismatch error in this code snippet:

val mapOps = (Map.empty[WordType, Int], unifyTwoMaps(intOps) _)

According to this answer scala type inference works per parameter's list - this is exactly what I've been doing here for currying purposes. My unifyTwoMaps function takes two parameters' lists and I'm trying to infer just the second one.

Answer 1

Solution to generic-recursive solution

Ok, so after spending morning on it I've finally understood that I've been providing wrong exact types.

val mapOps = (Map.empty[WordType, Int], unifyTwoMaps(intOps)(_: Map[String, Map[WordType, Int]], _: Map[String, Map[WordType, Int]]))

Should've been

val mapOps = (Map.empty[WordType, Int], unifyTwoMaps(intOps)(_: Map[WordType, Int], _: Map[WordType, Int]))

Because I needed to pass the type of Map's V, Map[WordType, Int], and not the type of whole outer map. And now it works!

Solution to underlying problem of nested map merging

Well, abstracting over maps' V zero and add should ring a bell, I've been reinventing Monoid. So I thought I'd try Scalaz |+| Semigroups operator solution from this answer.

import scalaz.Scalaz._
def unifyMapsWithScalaz(seq: Seq[Map[String, Map[WordType, Int]]]): Map[String, Map[WordType, Int]] = {
  seq reduce (_ |+| _)
}

And it works!

What's interesting is that I already saw that post before trying my solution, but I thought that I'm not sure it'd work for nested data structure, especially with my map's keys being Java Enum. I thought I'd have to provide some custom implementation extending Semigroups's typeclass.
But as it turned out during my reinventing-the-wheel implementation, the enum is only needed as a passed type and map key and it works pretty well. Well done Scalaz!

Well, that would've made a good blog post actually..

EDIT: but I still don't understand why I had this type inference problem in the first place, I've updated the question.