2

ピボットを選択するいくつかの方法でクイックソートを実装する必要があるため、ピボット チューザーをパラメーターとして受け取るルーチンを実装しました。しかし、具体的な実装の定義には多くのボイラープレートが含まれています。それらを定義するより簡潔な方法はありますか?

  private def qsort[a <% Ordered[a]](xs: Stream[a])(choosePivot:Stream[a] => a): Stream[a] = {
    if(xs.lengthCompare(1) <= 0) xs
    else {
      val pivot = choosePivot(xs)
      val l = xs.filter(_ < pivot)
      val r = xs.filter(_ > pivot)
      qsort(l)(choosePivot) ++ pivot#::qsort(r)(choosePivot)
    }
  }

  def qsortHead[a <% Ordered[a]](xs: Stream[a]) = qsort(xs)(ys => ys.head)

  def qsortLast[a <% Ordered[a]](xs: Stream[a]) = qsort(xs)(ys => ys.last)

  def qsortRandom[a <% Ordered[a]](xs: Stream[a]) = qsort(xs)(ys => ys(rng.nextInt(ys.length)))

Haskell ではqsortHead = qsort head、ピボット関数の選択が最初のパラメーターであるかqsortHead xs = qsort xs (\ys -> head ys)、2 番目のパラメーターであるかのように書くことができます。Scalaに似たようなものはありますか?

4

2 に答える 2

1

渡されたパラメーターを使用するラムダ式の場合、アンダースコア構文が役に立ちます。_.head

qsort(xs)(_.head)

_.head完全な式に変換されますx => x.head

于 2013-10-10T14:26:51.500 に答える
0

Orderedより一般的なOrdering. 私が知らない前者を使用する正当な理由がない限り、後者の方がおそらくより良い選択です。

それほど良くはないかもしれませんがOrdering、少なくとも使用すれば、醜い<%演算子を取り除くことができます. @maasg が提案したのと同じラムダの短縮形を使用することもお勧めします (ただし、より複雑な Random ラムダには使用できないことに注意してください)。

def qsortHead[A: Ordering](xs: Stream[A]) = qsort(xs)(_.head)
def qsortLast[A: Ordering](xs: Stream[A]) = qsort(xs)(_.last)
def qsortRandom[A: Ordering](xs: Stream[A]) = qsort(xs)(ys => ys(rng.nextInt(ys.length)))

Orderedビュー バウンドとコンテキストバウンドの違いに関する詳細情報が必要な場合は、この質問を見ることができますOrdering: Scala コンテキストとビュー バウンドとは何ですか?

Scala がジェネリック型を処理し、型を推論する方法が原因で、ほとんど何があってもボイラープレートの束で立ち往生することになります。上記はおそらく、あなたが得ることができるのと同じくらい簡潔です。

于 2013-10-11T02:13:32.400 に答える