Sorting collections

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Sorting collections

liesen

I find sorting stuff with Scala quite cumbersome in the sense that there's no general rule on how it's done. For example, to sort a List there's List.sort :: (A, A) => Boolean. To sort an Array we've got scala.util.Sorting which needs elements to be "comparable" (inherit Ordered[A]). To provide an ordering to a PriorityQueue[A] there's a parameter taking: A => Ordered[A].

Is there a plan to unify this?

In the meantime, here's some code I found useful to cope with it:

I stumbled into this mess trying to use a custom ordering for a PriorityQueue[(Int, Stream[Int])]. I wanted to sort the elements based on the first item in the tuple. I came up with this (inspired by Haskell's compare `on` f):

def compareOn[A, B <% Ordered[B]](f: A => B)(x: A): Ordered[A] = new Ordered[A] { def compare(y: A) = f(x) compare f(y) } This lets me do stuff like: new PriorityQueue[(Int, Stream[Int])()(compareOn(_._1)) ... or sorting an array of strings, as, by length (longest first): scala.util.Sorting.quickSort(as)(compareOn(-_.length)) ... which is quite neat.

To sort a List of strings, it's possible to use the Ordering trait like this:

def orderingOn[A, B <% Ordered[B]](f: A => B): Ordering[A] = new Ordering[A] { def compare(x: A, y: A) = f(x) compare f(y) } List[String](...).sort(orderingOn((_: String).length).lt) One can redefine compareOn to use orderedOn: def compareOn[A, B <% Ordered[B]](f: A => B)(x: A): Ordered[A] = new Ordered[A] { def compare(y: A) = orderingOn(f).compare(x, y) } Hope someone finds this useful.
Reply | Threaded
Open this post in threaded view
|

Re: Sorting collections

Joel Neely
You *might* also find this of use:

http://joelneely.wordpress.com/2008/03/29/sorting-by-schwartzian-transform-in-scala/

-jn-



On Wed, Jul 30, 2008 at 3:08 PM, liesen <[hidden email]> wrote:

> I find sorting stuff with Scala quite cumbersome in the sense that there's
> no general rule on how it's done. For example, to sort a List there's
> List.sort :: (A, A) => Boolean. To sort an Array we've got
> scala.util.Sorting which needs elements to be "comparable" (inherit
> Ordered[A]). To provide an ordering to a PriorityQueue[A] there's a
> parameter taking: A => Ordered[A].
>
> Is there a plan to unify this?
>
> In the meantime, here's some code I found useful to cope with it:
>
> I stumbled into this mess trying to use a custom ordering for a
> PriorityQueue[(Int, Stream[Int])]. I wanted to sort the elements based on
> the first item in the tuple. I came up with this (inspired by Haskell's
> compare `on` f): def compareOn[A, B <% Ordered[B]](f: A => B)(x: A):
> Ordered[A] = new Ordered[A] { def compare(y: A) = f(x) compare f(y) } This
> lets me do stuff like: new PriorityQueue[(Int,
> Stream[Int])()(compareOn(_._1)) ... or sorting an array of strings, as, by
> length (longest first):
> scala.util.Sorting.quickSort(as)(compareOn(-_.length)) ... which is quite
> neat.
>
> To sort a List of strings, it's possible to use the Ordering trait like
> this: def orderingOn[A, B <% Ordered[B]](f: A => B): Ordering[A] = new
> Ordering[A] { def compare(x: A, y: A) = f(x) compare f(y) }
> List[String](...).sort(orderingOn((_: String).length).lt) One can redefine
> compareOn to use orderedOn: def compareOn[A, B <% Ordered[B]](f: A => B)(x:
> A): Ordered[A] = new Ordered[A] { def compare(y: A) =
> orderingOn(f).compare(x, y) } Hope someone finds this useful.
>
> ________________________________
> View this message in context: Sorting collections
> Sent from the Scala - User mailing list archive at Nabble.com.
>



--
Programming is the art of writing essays in crystal clear prose and
making them execute. - Per Brinch Hansen