斯卡拉的訂購和沒有什麼

Question

斯卡拉的Ordered特性是depricated，所以我們必須使用Ordering。我試圖重寫我的BST類以使用Ordering，並且出現了編譯錯誤。任何人都可以解釋我如何正確使用Ordering和Nothing。這裏是我的代碼：

abstract sealed class Tree[+A: Ordering] { 
    def value: A 
    def left: Tree[A] 
    def right: Tree[A] 
    def isEmpty: Boolean 

/** 
    * Time - O(1) 
    * Space - O(1) 
    */ 
def mkTree(v: A, l: Tree[A] = Leaf, r: Tree[A] = Leaf): Tree[A] = 
    Branch(v, l, r) 

/** 
    * Fails with message. 
    */ 
def fail(s: String): Nothing = 
    throw new NoSuchElementException(s) 
} 

case object Leaf extends Tree[Nothing] { 
    def value: Nothing = fail("Empty tree.") 
    def left: Tree[Nothing] = fail("Empty tree.") 
    def right: Tree[Nothing] = fail("Empty tree.") 
    def isEmpty: Boolean = true 
} 

case class Branch[A: Ordering](value: A, left: Tree[A], right: Tree[A]) extends Tree[A] { 
    def isEmpty: Boolean = false 
} 

編譯時，我得到了以下內容：

Tree.scala:21: error: No implicit Ordering defined for Nothing. 
case object Leaf extends Tree[Nothing] { 
      ^
    one error found 

我以前寫這個類作爲abstract class Tree[+A <% Ordered[A]]它工作得很好。

Answer 1

我認爲這個問題與你設置樹的方式不太一樣，Ordering。錯誤消息是不言自明的：你已經說過應該有一個類型參數的隱式排序，但是在Leaf的情況下，你給它的類型參數是Nothing，它沒有排序。

所以我會說每個Tree有一個排序的要求是不正確的。您需要做的只是從第一行中刪除: Ordering，因爲您已經在Branch中包含了該要求，因此它的確有意義。

你mkTree方法將需要(implicit ord: Ordering[A])參數，但我不認爲這種方法用於什麼目的呢 - 它看起來就像是一個陪伴對象所屬（這是這樣，因爲你只是推遲到科工廠方法對象） - 所以我會刪除它。

Answer 2

Luigi是正確的，順序沒有意義的樹型。但是這個要求會更加明顯，如果使用Algebraic Data Type，設計會更清晰。這些使用類層次結構作爲接口的一部分，因此它們比面向對象（如Scala中的Option和List）更具功能性。

然後，您直接使用案例類來實例化它們（不需要mkTree函數），並通過模式匹配來檢索它們。

例如：

sealed trait Tree[+A] { 
    def isEmpty: Boolean 
} 

case object Leaf extends Tree[Nothing] { 
    def isEmpty: Boolean = true 
} 

case class Branch[+A: Ordering](value: A, left: Tree[A] = Leaf, right: Tree[A] = Leaf) extends Tree[A] { 
    def isEmpty: Boolean = false 
} 

def depthFirstSearch[A: Ordering](tree: Tree[A], expected: A): Option[Branch[A]] = { 
    import Ordering.Implicits._ 

    tree match { 
    case t @ Branch(value, _, _) if value == expected => Some(t) 
    case Branch(value, left, _) if value > expected => depthFirstSearch(left, expected) 
    case Branch(value, _, right) if value < expected => depthFirstSearch(right, expected) 
    case _ => None 
    } 
}