我在尝试在 Scala 2.10 中使用简单的 ADT 时遇到了一个奇怪的问题。
以下程序显示了该问题:
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)))
}
}
}
使用 Scala 2.10.x 编译此代码会导致以下错误:
[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] ^
使用 Scala 2.9.3 编译的相同代码编译成功,程序按预期工作。
我通过将 EmptyTrie 定义更改为:
case class EmptyTrie[T, V]() extends Trie[T, V]
并在特征定义上删除 T 和 V 的协方差规范。
但是,当单个对象实例完成这项工作时,我真的不喜欢实例化新的空类。使用该对象似乎更清洁。
最后我的问题是:
一些帮助编译器的类型提示(我在这方面的所有尝试
惨败)?
最佳答案
典型的类型删除问题(Map 对 Key 是不变的,而 Key 的真实类型在提取器中被删除)。只需在提取器中使用类型定义:
case TrieNode(value, subTrie : Map[T, Trie[T, V]]) => new TrieNode(update(value), subTrie.updated(x, addWith(xs1, subTrie.getOrElse(x, EmptyTrie), update, default)))
关于Scala 2.10 类型推断因 ADT 失败 - 从 2.9.3 回归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22337240/