If A
has the Ordered[A]
trait, I'd like to be able to have code that works like this
val collection: List[List[A]] = ... // construct a list of lists of As
val sorted = collection sort { _ < _ }
and get something where the lists have been sorted in lexicographic order. Of course, just because A
has the trait Ordered[A]
doesn't mean that List[A]
has the trait Ordered[List[A]]
. Presumably, however, the 'scala way' to do this is with an implicit def.
How do I implicitly convert a List[A]
to a Ordered[List[A]]
, assuming A has the trait Ordered[A]
(so that the code above just works)?
I have in mind using the lexicographic ordering on List[A]
objects, but I'd like code that can be adapted to others orderings.
Inspired by Ben Lings' answer, I wrote my own version of
sort
:which is equivalent to:
Note that
ordering
is implicitly converted toOrdering[Iterable[A]]
.Examples:
It was asked how to supply your own comparison function (say,
_ > _
instead of_ < _
). It suffices to useOrdering.fromLessThan
:Ordering.by
allows you to map your value into another type for which there is already an Ordering instance. Given that also tuples are ordered, this can be useful for lexicographical comparison of case classes.To make an example, let's define a wrapper of an Int, apply
Ordering.by(_.v)
, where_.v
extracts the underlying value, and show that we obtain the same result:Finally, let's do the same thing on a case class with more members, reusing the comparators for Tuples:
EDIT:
My definition of
sort
above is deprecated in 2.13:Use instead:
(11 minutes ago I actually didn't know how to do this, I hope it's considered okay to answer my own question.)
An important thing to note here is the 'view bound'
A <% Ordered[A]
, which ensures thatA
needn't itself by anOrdered[A]
, just that there's a way to do this conversion. Happily, the Scala library's objectPredef
has an implicit conversion fromInt
s toRichInt
s, which in particular areOrdered[Int]
s.The rest of the code is just implementing lexicographic ordering.
Inspired by Ben Lings' answer, I managed to work out what seems like the simplest way to sort lists lexicographically: add the line
before doing your List[Int] comparison, to ensure that the implicit function
infixOrderingOps
is in scope.Inspired by Daniel's comment, here is a recursive version:
With respect to the comment: I used to think it's more a matter of taste. Sometimes it's easier to verify correctness on a recursive function, and certainly your version is short enough that there is no compelling reason to prefer recursive.
I was intrigued by the performance implications though. So I tried to benchmark it: see http://gist.github.com/468435. I was surprised to see that the recursive version is faster (assuming I did the benchmark correctly). The results still hold true for list of about length 10.
Just because I already implemented this another way, here is a non-recursive version that does not use
return
:In 2.8, you should be able to just do
collection.sorted
.sorted
takes an implicitOrdering
parameter. Any type that implementsOrdered
has a correspondingOrdering
(thanks to the implicit conversionOrdering.ordered
). There is also the implicitOrdering.Iterable
that makes anIterable[T]
have anOrdering
ifT
has anOrdering
.However, if you try this it doesn't work:
You need to explicitly specify that you want the
Ordering[Iterable[A]]
:I'm not sure why the compiler can't find the
Ordering[Iterable[A]]
if the element type of the collection isList[A]
.