在Scala中订购编译错误

我在Scala中实现一个不可变BST时遇到了一些麻烦。这个问题似乎是由于某些原因，尽管我已经将K定义为Ordered[K]（第二行），但实际上它正在被Scala编译器考虑为Any。为什么？在Scala中订购编译错误

abstract class BST 
sealed case class Node[K <: Ordered[K], V](key : K, value : V, left : BST, right : BST) extends BST 
sealed case class Empty() extends BST 

object BST { 
    def empty = Empty() 

    def add[K <: Ordered[K], V](key : K, value : V, tree : BST) : BST = tree match { 
    case Empty() => new Node(key, value, Empty(), Empty()) 
    case Node(nodeKey, nodeValue, left, right) => 
     if (key < nodeKey) new Node(nodeKey, nodeValue, add(key, value, left), right) 
     else if (key > nodeKey) new Node(nodeKey, nodeValue, left, add(key, value, right)) 
     else new Node(key, value, left, right) 
    }

来源

2015-09-14 devoured elysium

编译器似乎是由你告诉它的泛型类型K是Ordered[K]亚型混淆。我也有点困惑。这就像说，A是List[A]的子类型，我无法将头围住。一个类型如何成为该类型列表的子类型？在某些情况下，递归定义类型可能有用，但我不认为这是其中之一。

从上下文来看，我觉得你想要的实际语法是[K: Ordered]。这告诉编译器期望在范围内存在隐含的Ordered[K]的通用类型K。这是语法糖，改变你的Node类是这样的：

sealed case class Node[K, V](key : K, value : V, left : BST, right : BST)(implicit evidence: Ordered[K]) extends BST

来源

2015-09-15 03:52:05 Zeimyth

嗯？在Java中，我只想说K延伸了Comparable 并且没有混淆。 –

这是因为在JVM的类型擦除 - 斯卡拉擦除Any。有关如何解决此问题的示例，请参阅此答案：How to pattern match on generic type in Scala?。或者考虑通过一个隐含的Ordering这样的：

sealed case class Node[K, V](key : K, value : V, left : BST, right : BST, 
    implicit cmp: Ordering[K]) extends BST

来源

2015-09-15 03:52:22

隐式参数需要在新的参数列表中。你需要......，右：BST）（隐式cmp：排序[K]）'。 –

我已经得到这归因于编译版本，它可能不是最小的，虽然和一些明确的注解大概可以去除。如果您需要更多解释，请发表评论。

abstract class BST[K : Ordering, V] 
sealed case class Node[K : Ordering, V](key : K, value : V, left : BST[K, V], right : BST[K,V]) extends BST[K, V] 
sealed case class Empty[K : Ordering, V]() extends BST[K, V] 

object BST { 
    def empty[K : Ordering, V] = Empty[K,V]() 

    def add[K : Ordering, V](key : K, value : V, tree : BST[K,V]) : BST[K,V] = tree match { 
    case Empty() => new Node(key, value, Empty(), Empty()) 
    case Node(nodeKey, nodeValue, left, right) => 
     if (implicitly[Ordering[K]].lt(key, nodeKey)) new Node(nodeKey, nodeValue, add(key, value, left), right) 
     else if (implicitly[Ordering[K]].gt(key,nodeKey)) new Node(nodeKey, nodeValue, left, add(key, value, right)) 
     else new Node(key, value, left, right) 
    } 
}

来源

2015-09-15 04:08:35 tryx

好的，谢谢你的帮助。但我认为你们所有的事情都太复杂了。唯一的问题似乎是BST必须也是BST [K，V]：

abstract class BST[K <: Ordered[K], V] 
sealed case class Node[K <: Ordered[K], V](key : K, value : V, left : BST[K, V], right : BST[K, V]) extends BST[K, V] 
sealed case class Empty[K <: Ordered[K], V]() extends BST[K, V] 

object BST { 
    def empty = Empty() 

    def add[K <: Ordered[K], V](key : K, value : V, tree : BST[K, V]) : BST[K, V] = tree match { 
    case Empty() => new Node(key, value, Empty(), Empty()) 
    case Node(nodeKey, nodeValue, left, right) => 
     if (key < nodeKey) new Node(nodeKey, nodeValue, add(key, value, left), right) 
     else if (key > nodeKey) new Node(nodeKey, nodeValue, left, add(key, value, right)) 
     else new Node(key, value, left, right) 
    } 
}

这个编译和按预期工作。

来源

2015-09-15 10:12:03

在Scala中订购编译错误

回答

相关问题