找不到類型的證據參數的隱式值Ordered [T]

Question

我現在實際上被阻止了大約4個小時。我想要得到一個由int值排序的成對List [String，Int]。功能partiotion工作正常，所以應該bestN，但是當加載到我的解釋器時，我得到：

<console>:15: error: could not find implicit value for evidence parameter of type Ordered[T] 

對我的謂詞。有人看到問題是什麼嗎？我此刻真的絕望了......

這是代碼：

def partition[T : Ordered](pred: (T)=>Boolean, list:List[T]): Pair[List[T],List[T]] = { 
    list.foldLeft(Pair(List[T](),List[T]()))((pair,x) => if(pred(x))(pair._1, x::pair._2) else (x::pair._1, pair._2)) 
} 

def bestN[T <% Ordered[T]](list:List[T], n:Int): List[T] = { 
    list match { 
     case pivot::other => { 
      println("pivot: " + pivot) 
      val (smaller,bigger) = partition(pivot <, list) 
      val s = smaller.size 
      println(smaller) 
      if (s == n) smaller 
      else if (s+1 == n) pivot::smaller 
      else if (s < n) bestN(bigger, n-s-1) 
      else bestN(smaller, n) 
     } 
     case Nil => Nil 
    } 
} 

class OrderedPair[T, V <% Ordered[V]] (t:T, v:V) extends Pair[T,V](t,v) with Ordered[OrderedPair[T,V]] { 
    def this(p:Pair[T,V]) = this(p._1, p._2) 
    override def compare(that:OrderedPair[T,V]) : Int = this._2.compare(that._2) 
} 

編輯：第一個功能通過應用謂詞每個成員把一個表分爲二，bestN函數返回一個列表中最低的n個成員列表。和類是有做對的可比性，在這種情況下，我想你做的是：

val z = List(Pair("alfred",1),Pair("peter",4),Pair("Xaver",1),Pair("Ulf",2),Pair("Alfons",6),Pair("Gulliver",3)) 

這個給定的名單我想例如使用：

bestN(z, 3) 

結果：

(("alfred",1), ("Xaver",1), ("Ulf",2)) 

Answer 1

看起來你不需要分區函數上的Ordered T，因爲它只是調用謂詞函數。

以下不起作用（大概）但只是編譯。代碼審查的其他事項將是額外的大括號和類似的東西。

package evident 

object Test extends App { 

    def partition[T](pred: (T)=>Boolean, list:List[T]): Pair[List[T],List[T]] = { 
    list.foldLeft(Pair(List[T](),List[T]()))((pair,x) => if(pred(x))(pair._1, x::pair._2) else (x::pair._1, pair._2)) 
    } 

    def bestN[U,V<%Ordered[V]](list:List[(U,V)], n:Int): List[(U,V)] = { 
    list match { 
     case pivot::other => { 
     println(s"pivot: $pivot and rest ${other mkString ","}") 
     def cmp(a: (U,V), b: (U,V)) = (a: OrderedPair[U,V]) < (b: OrderedPair[U,V]) 
     val (smaller,bigger) = partition(((x:(U,V)) => cmp(x, pivot)), list) 
     //val (smaller,bigger) = list partition ((x:(U,V)) => cmp(x, pivot)) 
     println(s"smaller: ${smaller mkString ","} and bigger ${bigger mkString ","}") 
     val s = smaller.size 
     if (s == n) smaller 
     else if (s+1 == n) pivot::smaller 
     else if (s < n) bestN(bigger, n-s-1) 
     else bestN(smaller, n) 
     } 
     case Nil => Nil 
    } 
    } 

    implicit class OrderedPair[T, V <% Ordered[V]](tv: (T,V)) extends Pair(tv._1, tv._2) with Ordered[OrderedPair[T,V]] { 
    override def compare(that:OrderedPair[T,V]) : Int = this._2.compare(that._2) 
    } 

    val z = List(Pair("alfred",1),Pair("peter",4),Pair("Xaver",1),Pair("Ulf",2),Pair("Alfons",6),Pair("Gulliver",3)) 
    println(bestN(z, 3)) 
} 

我發現分區函數很難讀取;你需要一個功能來分割所有的parens。這裏有幾個公式，它們也使用了過濾器接受的結果左邊的約定，拒絕是正確的。

def partition[T](p: T => Boolean, list: List[T]) = 
    ((List.empty[T], List.empty[T]) /: list) { (s, t) => 
    if (p(t)) (t :: s._1, s._2) else (s._1, t :: s._2) 
    } 
def partition2[T](p: T => Boolean, list: List[T]) = 
    ((List.empty[T], List.empty[T]) /: list) { 
    case ((is, not), t) if p(t) => (t :: is, not) 
    case ((is, not), t)   => (is, t :: not) 
    } 
// like List.partition 
def partition3[T](p: T => Boolean, list: List[T]) = { 
    import collection.mutable.ListBuffer 
    val is, not = new ListBuffer[T] 
    for (t <- list) (if (p(t)) is else not) += t 
    (is.toList, not.toList) 
} 

這可能是更接近於何意原代碼：

def bestN[U, V <% Ordered[V]](list: List[(U,V)], n: Int): List[(U,V)] = { 
    require(n >= 0) 
    require(n <= list.length) 
    if (n == 0) Nil 
    else if (n == list.length) list 
    else list match { 
    case pivot :: other => 
     println(s"pivot: $pivot and rest ${other mkString ","}") 
     def cmp(x: (U,V)) = x._2 < pivot._2 
     val (smaller, bigger) = partition(cmp, other)  // other partition cmp 
     println(s"smaller: ${smaller mkString ","} and bigger ${bigger mkString ","}") 
     val s = smaller.size 
     if (s == n) smaller 
     else if (s == 0) pivot :: bestN(bigger, n - 1) 
     else if (s < n) smaller ::: bestN(pivot :: bigger, n - s) 
     else bestN(smaller, n) 
    case Nil => Nil 
    } 
} 

箭頭符號是更常見的：

val z = List(
    "alfred" -> 1, 
    "peter" -> 4, 
    "Xaver" -> 1, 
    "Ulf" -> 2, 
    "Alfons" -> 6, 
    "Gulliver" -> 3 
) 

Answer 2

我懷疑我錯過了一些東西，但我會發表一些代碼。

對於bestN，你知道你可以這麼做嗎？

val listOfPairs = List(Pair("alfred",1),Pair("peter",4),Pair("Xaver",1),Pair("Ulf",2),Pair("Alfons",6),Pair("Gulliver",3)) 
val bottomThree = listOfPairs.sortBy(_._2).take(3) 

它給你：

List((alfred,1), (Xaver,1), (Ulf,2)) 

而對於partition功能，你可以這樣做（說你想要的一切對下則4）：

val partitioned = listOfPairs.partition(_._2 < 4) 

其中給出（全部低於左邊4，全部大於右邊）：

​​

Answer 3

只是與大家分享：這個作品！非常感謝所有幫助過我的人，你們都很棒！

object Test extends App { 

    def partition[T](pred: (T)=>Boolean, list:List[T]): Pair[List[T],List[T]] = { 
    list.foldLeft(Pair(List[T](),List[T]()))((pair,x) => if(pred(x))(pair._1, x::pair._2) else (x::pair._1, pair._2)) 
    } 

    def bestN[U,V<%Ordered[V]](list:List[(U,V)], n:Int): List[(U,V)] = { 
    list match { 
     case pivot::other => { 
     def cmp(a: (U,V), b: (U,V)) = (a: OrderedPair[U,V]) <= (b: OrderedPair[U,V]) 
     val (smaller,bigger) = partition(((x:(U,V)) => cmp(pivot, x)), list) 
     val s = smaller.size 
     //println(n + " :" + s) 
     //println("size:" + smaller.size + "Pivot: " + pivot + " Smaller part: " + smaller + " bigger: " + bigger) 
     if (s == n) smaller 
     else if (s+1 == n) pivot::smaller 
     else if (s < n) bestN(bigger, n-s) 
     else bestN(smaller, n) 
     } 
     case Nil => Nil 
    } 
    } 

    class OrderedPair[T, V <% Ordered[V]](tv: (T,V)) extends Pair(tv._1, tv._2) with Ordered[OrderedPair[T,V]] { 
    override def compare(that:OrderedPair[T,V]) : Int = this._2.compare(that._2) 
    } 
    implicit final def OrderedPair[T, V <% Ordered[V]](p : Pair[T, V]) : OrderedPair[T,V] = new OrderedPair(p) 

    val z = List(Pair("alfred",1),Pair("peter",1),Pair("Xaver",1),Pair("Ulf",2),Pair("Alfons",6),Pair("Gulliver",3)) 
    println(bestN(z, 3)) 
    println(bestN(z, 4)) 
    println(bestN(z, 1)) 
}