14

特性がある場合Aは、Ordered[A]このように機能するコードを作成できるようにしたいと思います

val collection: List[List[A]] = ... // construct a list of lists of As
val sorted = collection sort { _ < _ }

リストが辞書式順序でソートされているものを取得します。もちろん、A特性があるからといって、それが特性を持っているOrdered[A]とは限りません。ただし、おそらく、これを行うための「スカラ方式」は、暗黙のdefを使用することです。List[A]Ordered[List[A]]

Aに特性があると仮定して（上記のコードが正しく機能するように） 、暗黙的にaList[A]をaに変換するにはどうすればよいですか？Ordered[List[A]]Ordered[A]

オブジェクトに辞書式順序を使用することを念頭に置いていList[A]ますが、他の順序に適合できるコードが必要です。

4

6 に答える 6

24

Ben Lingsの回答に触発されて、リストを辞書式順序で並べ替える最も簡単な方法のように見えるものを見つけることができました。行を追加します。

import scala.math.Ordering.Implicits._

List [Int]比較を行う前に、暗黙の関数infixOrderingOpsがスコープ内にあることを確認します。

于 2011-03-30T18:57:48.693 に答える
6

（11分前、私は実際にこれを行う方法を知りませんでした。私自身の質問に答えても大丈夫だと考えられることを願っています。）

implicit def List2OrderedList[A <% Ordered[A]](list1: List[A]): Ordered[List[A]] = { 
    new Ordered[List[A]] {
        def compare(list2: List[A]): Int = {
            for((x,y) <- list1 zip list2) {
                val c = x compare y
                if(c != 0) return c
            }
            return list1.size - list2.size
        }
    }
}

ここで注意すべき重要なことは、「ビューバウンド」です。これは、この変換を行う方法があるということだけで、それ自体が必要ではないA <% Ordered[A]ことを保証します。幸いなことに、Scalaライブラリのオブジェクトにはsからsへの暗黙の変換があります。特にsです。AOrdered[A]PredefIntRichIntOrdered[Int]

コードの残りの部分は、辞書式順序を実装しているだけです。

于 2010-06-29T05:01:23.317 に答える
4

ベン・リングスの答えに触発されて、私は自分のバージョンを書きましたsort：

def sort[A : Ordering](coll: Seq[Iterable[A]]) = coll.sorted

これは次と同等です：

def sort[A](coll: Seq[Iterable[A]])(implicit ordering: Ordering[A]) = coll.sorted

orderingは暗黙的にに変換されることに注意してくださいOrdering[Iterable[A]]。

例：

scala> def sort[A](coll: Seq[Iterable[A]])(implicit ordering: Ordering[A]) = coll.sorted
sort: [A](coll: Seq[Iterable[A]])(implicit ordering: Ordering[A])Seq[Iterable[A]]

scala> val coll = List(List(1, 3), List(1, 2), List(0), Nil, List(2))
coll: List[List[Int]] = List(List(1, 3), List(1, 2), List(0), List(), List(2))

scala> sort(coll)
res1: Seq[Iterable[Int]] = List(List(), List(0), List(1, 2), List(1, 3), List(2))

独自の比較関数を提供する方法を尋ねられました（たとえば、の_ > _代わりに_ < _）。使用するだけで十分ですOrdering.fromLessThan：

scala> sort(coll)(Ordering.fromLessThan(_ > _))
res4: Seq[Iterable[Int]] = List(List(), List(2), List(1, 3), List(1, 2), List(0))

Ordering.byOrderingインスタンスがすでに存在する別のタイプに値をマップできます。タプルも順序付けられていることを考えると、これはケースクラスの辞書式比較に役立ちます。

例を示すために、Intのラッパーを定義し、適用して、基になる値を抽出し、同じ結果が得られることを示しましょOrdering.by(_.v)う_.v。

scala> case class Wrap(v: Int)
defined class Wrap

scala> val coll2 = coll.map(_.map(Wrap(_)))
coll2: List[List[Wrap]] = List(List(Wrap(1), Wrap(3)), List(Wrap(1), Wrap(2)), List(Wrap(0)), List(), List(Wrap(2)))

scala> sort(coll2)(Ordering.by(_.v))
res6: Seq[Iterable[Wrap]] = List(List(), List(Wrap(0)), List(Wrap(1), Wrap(2)), List(Wrap(1), Wrap(3)), List(Wrap(2)))

最後に、タプルのコンパレータを再利用して、より多くのメンバーを持つケースクラスで同じことを実行しましょう。

scala> case class MyPair(a: Int, b: Int)
defined class MyPair

scala> val coll3 = coll.map(_.map(MyPair(_, 0)))
coll3: List[List[MyPair]] = List(List(MyPair(1,0), MyPair(3,0)), List(MyPair(1,0), MyPair(2,0)), List(MyPair(0,0)), List(), List(MyPair(2,0)))

scala> sort(coll3)(Ordering.by(x => (x.a, x.b)))
res7: Seq[Iterable[MyPair]] = List(List(), List(MyPair(0,0)), List(MyPair(1,0), MyPair(2,0)), List(MyPair(1,0), MyPair(3,0)), List(MyPair(2,0)))

編集：

上記の私の定義はsort2.13で非推奨になりました：

warning: method Iterable in object Ordering is deprecated (since 2.13.0):
Iterables are not guaranteed to have a consistent order; if using a type
with a consistent order (e.g. Seq), use its Ordering (found in the
Ordering.Implicits object)

代わりに使用してください：

def sort[A](coll: Seq[Seq[A]])(implicit ordering: Ordering[A]) = {
  import Ordering.Implicits._
  coll.sorted
}
于 2011-03-31T00:51:39.767 に答える
4

2.8では、あなたはただすることができるはずですcollection.sorted。sorted暗黙のOrderingパラメータを取ります。を実装するすべてのタイプにOrderedは、対応するものがありますOrdering（暗黙の変換のおかげでOrdering.ordered）。ifが。を持っているようにOrdering.Iterableする暗黙的なものもあります。Iterable[T]OrderingTOrdering

ただし、これを試してみると機能しません。

scala> def sort[A <: Ordered[A]](coll: List[List[A]]) = coll.sorted

<console>:5: error: could not find implicit value for parameter ord: Ordering[List[A]]
       def sort[A <: Ordered[A]](coll: List[List[A]]) = coll.sorted
                                                             ^

：が必要であることを明示的に指定する必要がありますOrdering[Iterable[A]]。

def sort[A <: Ordered[A]](coll: List[List[A]]) = coll.sorted[Iterable[A]]

Ordering[Iterable[A]]コレクションの要素タイプがである場合、コンパイラがifを検出できない理由がわかりませんList[A]。

于 2010-06-29T11:55:57.107 に答える
3

ダニエルのコメントに触発されて、ここに再帰バージョンがあります：

implicit def toOrdered[A <% Ordered[A]](list1: List[A]): Ordered[List[A]] = { 
  @scala.annotation.tailrec
  def c(list1:List[A], list2:List[A]): Int = {
    (list1, list2) match {
      case (Nil, Nil) => 0
      case (x::xs, Nil) => 1
      case (Nil, y::ys) => -1
      case (x::xs, y::ys) => (x compare y) match {
        case 0 => c(xs, ys)
        case i => i
      }
    }
  }
  new Ordered[List[A]] {
    def compare(list2: List[A]): Int = c(list1, list2)
  }
}

コメントに関して：私はそれがより好みの問題だと思っていました。再帰関数の正しさを検証する方が簡単な場合もあります。確かに、バージョンが十分に短いため、再帰を好む理由はありません。

しかし、私はパフォーマンスへの影響に興味をそそられました。だから私はそれをベンチマークしようとしました：http：//gist.github.com/468435を参照してください。再帰バージョンの方が高速であることに驚きました（ベンチマークを正しく実行したと仮定して）。結果は、約長さ10のリストにも当てはまります。

于 2010-06-30T06:39:18.737 に答える
1

私がすでにこれを別の方法で実装したという理由だけで、これは使用しない非再帰バージョンですreturn：

new Ordering[Seq[String]]() {
  override def compare(x: Seq[String], y: Seq[String]): Int = {
    x.zip(y).foldLeft(None: Option[Int]){ case (r, (v, w)) =>
        if(r.isDefined){
          r
        } else {
          val comp = v.compareTo(w)
          if(comp == 0) None
          else Some(comp)
        }
      }.getOrElse(x.size.compareTo(y.size))
    }
  }
于 2019-10-17T07:34:51.640 に答える