Currying by second argument

Question

I need to implement quicksort with several ways to select pivot, so I've implemented a routine that takes a pivot chooser as a parameter. But definitions of concrete implementations contain lots of boilerplate, is there a more concise way to define them?

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

In Haskell I could just write something like qsortHead = qsort head if the choose pivot function is the first parameter or qsortHead xs = qsort xs (\ys -> head ys) if it's the second. Is there something similar in Scala?

Answer 1

I want to point out that Ordered has been mostly phased out of the Scala standard library in favor of the more general Ordering. Unless you have a good reason for using the former that I don't know about, the latter is probably a better choice.

It might not be much better, but if you use Ordering at least you can get rid of the ugly <% operators. I'd also recommend using the same lambda shorthand that @maasg suggested (note that you can't use it for the more complex Random lambda though):

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

You can look at this question if you want more info on the difference between the view-bound Ordered and context-bound Ordering: What are Scala context and view bounds?

Due to the way that Scala handles generic types and does type inference, you're going to be stuck with a bunch of boilerplate pretty much no matter what. The above is probably about as succinct as you're going to be able to get.

Answer 2

For the lambda expressions making use of the passed parameter, the underscore syntax is your friend: _.head

qsort(xs)(_.head)

_.head will be translated to the full expression x => x.head