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?

I guess that (ys => xs(rng.nextInt(xs.length))) should read (ys => ys(rng.nextInt(ys.length))) — maasg
– maasg, Commented Oct 10, 2013 at 14:32
@maasg yeah, that's some buggy code I've submitted, the qsort routine is also incorrect. — synapse
– synapse, Commented Oct 10, 2013 at 14:56
Multiple parameter lists are quite distinct from currying. You're talking about multiple parameters lists. — Randall Schulz
– Randall Schulz, Commented Oct 10, 2013 at 17:49
@RandallSchulz - I totally agree, and it really bugs me to see the two concepts mixed up. Partially applied functions are not the same as curried functions! Unfortunately, the Scala community seems to enjoy conflating "multiple parameter lists" and "curried." Even Odersky's book seems to mix the two together, or at least blur the boundary. — DaoWen
– DaoWen, Commented Oct 11, 2013 at 0:24

maasg · Accepted Answer · 2013-10-10 14:31:54Z

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

Community · Accepted Answer · 2017-05-23 10:25:45Z

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.

Collectives™ on Stack Overflow

Currying by second argument

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related