114
votes

I have a list of simple scala case class instances and I want to print them in predictable, lexicographical order using list.sorted, but receive "No implicit Ordering defined for ...".

Is there exist an implicit that provides lexicographical ordering for case classes?

Is there simple idiomatic way to mix-in lexicographical ordering into case class?

scala> case class A(tag:String, load:Int)
scala> val l = List(A("words",50),A("article",2),A("lines",7))

scala> l.sorted.foreach(println)
<console>:11: error: No implicit Ordering defined for A.
          l.sorted.foreach(println)
            ^

I am not happy with a 'hack':

scala> l.map(_.toString).sorted.foreach(println)
A(article,2)
A(lines,7)
A(words,50)
7
I've just written up a blog post with a couple of generic solutions here.Travis Brown

7 Answers

161
votes

My personal favorite method is to make use of the provided implicit ordering for Tuples, as it is clear, concise, and correct:

case class A(tag: String, load: Int) extends Ordered[A] {
  // Required as of Scala 2.11 for reasons unknown - the companion to Ordered
  // should already be in implicit scope
  import scala.math.Ordered.orderingToOrdered

  def compare(that: A): Int = (this.tag, this.load) compare (that.tag, that.load)
}

This works because the companion to Ordered defines an implicit conversion from Ordering[T] to Ordered[T] which is in scope for any class implementing Ordered. The existence of implicit Orderings for Tuples enables a conversion from TupleN[...] to Ordered[TupleN[...]] provided an implicit Ordering[TN] exists for all elements T1, ..., TN of the tuple, which should always be the case because it makes no sense to sort on a data type with no Ordering.

The implicit ordering for Tuples is your go-to for any sorting scenario involving a composite sort key:

as.sortBy(a => (a.tag, a.load))

As this answer has proven popular I would like to expand on it, noting that a solution resembling the following could under some circumstances be considered enterprise-grade™:

case class Employee(id: Int, firstName: String, lastName: String)

object Employee {
  // Note that because `Ordering[A]` is not contravariant, the declaration
  // must be type-parametrized in the event that you want the implicit
  // ordering to apply to subclasses of `Employee`.
  implicit def orderingByName[A <: Employee]: Ordering[A] =
    Ordering.by(e => (e.lastName, e.firstName))

  val orderingById: Ordering[Employee] = Ordering.by(e => e.id)
}

Given es: SeqLike[Employee], es.sorted() will sort by name, and es.sorted(Employee.orderingById) will sort by id. This has a few benefits:

  • The sorts are defined in a single location as visible code artifacts. This is useful if you have complex sorts on many fields.
  • Most sorting functionality implemented in the scala library operates using instances of Ordering, so providing an ordering directly eliminates an implicit conversion in most cases.
50
votes
object A {
  implicit val ord = Ordering.by(unapply)
}

This has the benefit that it is updated automatically whenever A changes. But, A's fields need to be placed in the order by which the ordering will use them.

29
votes

To summarize, there are three ways to do this:

  1. For one-off sorting use .sortBy method, as @Shadowlands have showed
  2. For reusing of sorting extend case class with Ordered trait, as @Keith said.
  3. Define a custom ordering. The benefit of this solution is that you can reuse orderings and have multiple ways to sort instances of the same class:

    case class A(tag:String, load:Int)
    
    object A {
      val lexicographicalOrdering = Ordering.by { foo: A => 
        foo.tag 
      }
    
      val loadOrdering = Ordering.by { foo: A => 
        foo.load 
      }
    }
    
    implicit val ord = A.lexicographicalOrdering 
    val l = List(A("words",1), A("article",2), A("lines",3)).sorted
    // List(A(article,2), A(lines,3), A(words,1))
    
    // now in some other scope
    implicit val ord = A.loadOrdering
    val l = List(A("words",1), A("article",2), A("lines",3)).sorted
    // List(A(words,1), A(article,2), A(lines,3))
    

Answering your question Is there any standard function included into the Scala that can do magic like List((2,1),(1,2)).sorted

There is a set of predefined orderings, e.g. for String, tuples up to 9 arity and so on.

No such thing exists for case classes, since it is not easy thing to roll off, given that field names are not known a-priori (at least without macros magic) and you can't access case class fields in a way other than by name/using product iterator.

8
votes

The unapply method of the companion object provides a conversion from your case class to an Option[Tuple], where the Tuple is the tuple corresponding to the first argument list of the case class. In other words:

case class Person(name : String, age : Int, email : String)

def sortPeople(people : List[Person]) = 
    people.sortBy(Person.unapply)
7
votes

The sortBy method would be one typical way of doing this, eg (sort on tag field):

scala> l.sortBy(_.tag)foreach(println)
A(article,2)
A(lines,7)
A(words,50)
5
votes

Since you used a case class you could extend with Ordered like such:

case class A(tag:String, load:Int) extends Ordered[A] { 
  def compare( a:A ) = tag.compareTo(a.tag) 
}

val ls = List( A("words",50), A("article",2), A("lines",7) )

ls.sorted
0
votes

My personal favorite method is using the SAM(Single abstraction method) with 2.12 as mentioned over the below example:

case class Team(city:String, mascot:String)

//Create two choices to sort by, city and mascot
object MyPredef3 {
  // Below used in 2.11
  implicit val teamsSortedByCity: Ordering[Team] = new Ordering[Team] {
    override def compare(x: Team, y: Team) = x.city compare y.city
  }

  implicit val teamsSortedByMascot: Ordering[Team] = new Ordering[Team] {
    override def compare(x: Team, y: Team) = x.mascot compare y.mascot
  }

  /*
     Below used in 2.12
     implicit val teamsSortedByCity: Ordering[Team] =
    (x: Team, y: Team) => x.city compare y.city
     implicit val teamsSortedByMascot: Ordering[Team] =
    (x: Team, y: Team) => x.mascot compare y.mascot

   */
}

object _6OrderingAList extends App {
  //Create some sports teams
  val teams = List(Team("Cincinnati", "Bengals"),
    Team("Madrid", "Real Madrid"),
    Team("Las Vegas", "Golden Knights"),
    Team("Houston", "Astros"),
    Team("Cleveland", "Cavaliers"),
    Team("Arizona", "Diamondbacks"))

  //import the implicit rule we want, in this case city
  import MyPredef3.teamsSortedByCity

  //min finds the minimum, since we are sorting
  //by city, Arizona wins.
  println(teams.min.city)

}