我现在实际上被阻止了大约 4 个小时。我想获得按其 int 值排序的 Pairs[String, Int] 列表。函数分区工作正常,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 个成员的列表。这个类(class)是为了让 Pairs 具有可比性,在这种情况下,我想做的是:
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))
最佳答案
看起来您的分区函数不需要 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))
}
我发现分区函数难以阅读;你需要一个函数来分割所有的括号。这里有几个公式,它们也使用过滤器接受的结果向左走,拒绝向右走的惯例。
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
)
关于scala - 找不到 Ordered[T] 类型的证据参数的隐式值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13897067/