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)))

qsortHead = qsort head在 Haskell 中，如果选择枢轴函数是第一个参数还是第二个参数，我可以写一些类似的东西qsortHead xs = qsort xs (\ys -> head ys)。Scala中有类似的东西吗？

4

2 回答 2

1

对于使用传递参数的 lambda 表达式，下划线语法是你的朋友：_.head

qsort(xs)(_.head)

_.head将被翻译成完整的表达式x => x.head

于 2013-10-10T14:26:51.500 回答
0

我想指出Ordered的是，Scala 标准库大部分已被淘汰，取而代之的是更通用的Ordering. 除非您有充分的理由使用我不知道的前者，否则后者可能是更好的选择。

它可能不会好多少，但如果你使用Ordering至少你可以摆脱丑陋的<%运营商。我还建议使用@maasg 建议的相同 lambda 简写（请注意，您不能将它用于更复杂的 Random lambda）：

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 回答