Scalaで辞書編集順にリストのコレクションを並べ替えるにはどうすればよいですか？

StackOverflow https://stackoverflow.com/questions/3137918

質問

もしも A 持っています Ordered[A] 特性、私はこのように機能するコードを持っていることを望んでいます

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

リストが辞書編集順にソートされた場所を取得します。もちろん、という理由だけで A 特性があります Ordered[A] それを意味しません List[A] 特性があります Ordered[List[A]]. 。おそらく、これを行うための「Scala Way」は暗黙のdefであると思われます。

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

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

役に立ちましたか？

解決

ベン・リングスの答えに触発されて、私は自分のバージョンを書きました 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))

独自の比較機能を提供する方法が尋ねられました。注文を使用するだけで十分です。

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

Ordering.by 既に順序付けインスタンスがある別のタイプに値をマッピングできます。タプルも注文されていることを考えると、これはケースクラスの辞書的な比較に役立ちます。

例を挙げると、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)))

他のヒント

ベン・リングスの答えに触発されて、私はリストを辞書的に並べ替える最も簡単な方法のように思えるものをなんとか解決することができました：ラインを追加する

import scala.math.Ordering.Implicits._

リスト[int]比較を行う前に、暗黙の関数を確認するために infixOrderingOps 範囲内です。

（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], 、それを保証します A それ自体が必要ではありません Ordered[A], 、この変換を行う方法があるだけです。幸いなことに、Scala Libraryのオブジェクト Predef からの暗黙の変換があります Ints to RichInt特にそうです Ordered[Int]s。

残りのコードは、辞書編集の順序を実装するだけです。

2.8では、あなただけができるはずです collection.sorted. sorted 暗黙的になります Ordering パラメーター。実装する任意のタイプ Ordered 対応するものがあります Ordering （暗黙の変換のおかげです Ordering.ordered）。暗黙的なものもあります Ordering.Iterable それは Iterable[T] 一つ持っている Ordering もしも T 持っています Ordering.

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

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]] コレクションの要素タイプがある場合 List[A].

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

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のリストのリストにも当てはまります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top