4

私は実際にこれで約4時間ブロックされています。ペアのリスト[String、Int]を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)
}

編集：最初の関数は、すべてのメンバーに述語を適用することによってリストを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))
4

3 に答える 3

2

述語関数を呼び出すだけなので、パーティション関数にOrderedTは必要ないようです。

以下は（おそらく）機能せず、単にコンパイルするだけです。コードレビューのその他の問題は、余分な中括弧などです。

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
  )
于 2012-12-16T02:14:03.583 に答える
1

何かが足りないのではないかと思いますが、とにかく少しコードを投稿します。

のため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より低く、すべて右側が大きくなります）：

(List((alfred,1), (Xaver,1), (Ulf,2), (Gulliver,3)),List((peter,4), (Alfons,6)))
于 2012-12-16T00:43:25.707 に答える
0

あなたと共有するだけです：これはうまくいきます！私を助けてくれたすべての人に感謝します、あなたはすべて素晴らしいです！

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))
}
于 2012-12-16T13:00:54.583 に答える