Could not find implicit value for proof parameter of type Ordered [T]

Question

In fact, I am locked on this for about 4 hours. I want to get a list of [String, Int] pairs ordered by their int value. The partiotion function works fine, so it's better to use N, but when I load this into my interpreter, I get:

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

in my predicate. Does anyone see what the problem is? I'm really desperate at the moment ...

This is the code:

 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, ns-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) } 

Edit: the first function divides the list into two, applying a predicate to each member, the bestN function should return a list of the smallest n members of the list. And the class should make the pairs comparable, in this case I want to do this:

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

with this list, which I want to get, for example, with

 bestN(z, 3) 

result:

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

Answer 1

It doesn't seem like you need an ordered T for your split function, since it just calls the predicate function.

It does not work (presumably), but simply compiles. Other questions for checking the code would be extra brackets and the like.

 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, ns-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)) } 

I found that the section function is hard to read; you need a function to separate all the guys. Here are some formulations that also use the agreement, the results accepted by the filter go to the left, deviations go to the right.

 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) } 

This may be closer to the source code:

 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 } } 

The arrow values ​​are more common:

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

Answer 2

I suspect I'm missing something, but I will still send the code.

For bestN , do you know you can just do it?

 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) 

What gives you:

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

And for the partition function, you can simply do this (let's say you wanted all pairs to be below 4):

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

Which gives (all lower than 4 on the left, more on the right):

 (List((alfred,1), (Xaver,1), (Ulf,2), (Gulliver,3)),List((peter,4), (Alfons,6))) 

Answer 3

Just share with you: it works! Thanks to all the people who helped me, you are all healthy!

 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, ns) 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)) }