Scala 2.10 type inference failing with ADT - regression from 2.9.3

Question

I'm encountering a weird problem trying to use a simple ADT in Scala 2.10. The following program shows the issue:

sealed trait Trie[+T, +V]
case object EmptyTrie extends Trie[Nothing, Nothing]
case class TrieNode[T, V](data: V, subTrie: Map[T, Trie[T, V]]) extends Trie[T, V]
case class TrieLeaf[T, V](data: V) extends Trie[T, V]

object Trie {
  def emptyTrie[T, V](): Trie[T, V] = EmptyTrie

  def addWith[T, V](xs: List[T], trie: Trie[T, V], update: (V => V), default: V): Trie[T, V] =
    xs match {
      case Nil => trie match {
        case EmptyTrie                => new TrieLeaf(default)
        case TrieNode(value, subTrie) => new TrieNode(update(value), subTrie)
        case TrieLeaf(value)          => new TrieLeaf(update(value))
      }
      case x :: xs1 => trie match {
        case EmptyTrie                => new TrieNode(default, Map(x -> addWith(xs1, EmptyTrie, update, default)))
        case TrieNode(value, subTrie) => new TrieNode(update(value), subTrie.updated(x, addWith(xs1, subTrie.getOrElse(x, EmptyTrie), update, default)))
        case TrieLeaf(value)          => new TrieNode(update(value), Map(x -> addWith(xs1, EmptyTrie, update, default)))
      }
    }
}

Compiling this code with Scala 2.10.x result in the following errors:

[error] /tmp/rendererkH7rTCTbYi/src/main/scala/test.scala:22: type mismatch;
[error]  found   : x.type (with underlying type T)
[error]  required: ?T4 where type ?T4 <: T (this is a GADT skolem)
[error]         case TrieNode(value, subTrie) => new TrieNode(update(value), subTrie.updated(x, addWith(xs1, subTrie.getOrElse(x, EmptyTrie), update, default)))
[error]                                                                                      ^
[error] /tmp/rendererkH7rTCTbYi/src/main/scala/test.scala:22: type mismatch;
[error]  found   : x.type (with underlying type T)
[error]  required: ?T4 where type ?T4 <: T (this is a GADT skolem)
[error]         case TrieNode(value, subTrie) => new TrieNode(update(value), subTrie.updated(x, addWith(xs1, subTrie.getOrElse(x, EmptyTrie), update, default)))
[error]                                                                                                                        ^

The same code compiled with Scala 2.9.3 compiles successfully and the programs works as expected.

I've worked the problem around by changing the EmptyTrie definition to:

case class EmptyTrie[T, V]() extends Trie[T, V]

and dropping the covariance specification on T and V on the trait definition.

However I really don't like having to instantiate new empty classes when a single object instance would do the job. Using the object just seems a lot cleaner.

In the end my questions are:

• Is this a regression in the scala compiler?
• Is it possible to add some type hints to aid the compiler (all my attempts at this miserably failed)?

Answer 1

Typical type erasure problem (Map is invariant by Key and real type of Key is erased in extractor). Just use type definition in extractor:

case TrieNode(value, subTrie : Map[T, Trie[T, V]]) => new TrieNode(update(value), subTrie.updated(x, addWith(xs1, subTrie.getOrElse(x, EmptyTrie), update, default)))