3

From the scala reference: http://www.scala-lang.org/files/archive/nightly/docs/library/index.html#scala.math.Ordering

  case class Person(name:String, age:Int)
  val people = Array(Person("bob", 30), Person("ann", 32), Person("carl", 19))

  // sort by age
  object AgeOrdering extends Ordering[Person] {
      def compare(a:Person, b:Person) = a.age compare b.age
  }

But if I want to sort a Seq using an Ordering object:

  // Want to sort a Seq, or event and IndexedSeq
  val ps = people.asInstanceOf[collection.Seq[Person]]

  // Type not enough arguments 
  // for method stableSort: (implicit evidence$6: scala.reflect.ClassTag[Person], 
  // implicit evidence$7: scala.math.Ordering[Person])Array[Person]. Unspecified value 
  // parameter evidence$7.  
  Sorting.stableSort(ps)(AgeOrdering)

the compiler chokes. But the stableSort API says it will take an Seq. So why does the above fail?

user48956
  • 14,850
  • 19
  • 93
  • 154

1 Answers1

2

In Sorting, the quickSort implementation is done in-place, with a bunch of index-based moves which are only suitable to be done on an Array (and a Seq does not define indexing at all).

quickSort[K](a: Array[K] ..): Unit

The quickSort method performs side-effects on the input and returns Unit.

The stableSort however, has two different forms. One that takes an Seq and one that takes an Array. 

stableSort[K](a: Seq[K] ..): Array[K]
stableSort[K](a: Array[K] ..): Unit

The form that takes an Array also returns Unit and modifies the input (as quickSort but ensuring stability), while the form takes a Seq returns a new Array object (and the input sequence is not modified).

The error is because the quickSort method has the signature for the second parameter group: (implicit arg0: math.Ordering[K]) while the stableSort method has: (implicit arg0: ClassTag[K], arg1: math.Ordering[K]) - that is, it also requires a ClassTag[K/Person].

Even though the ordering was specified, no ClassTag[K] argument is specified (or implicitly resolved) and Scala needs this to create the Array[Person] that is used internally (and returned). Due to Scala being limited by Java's type erasure, the method doesn't get to know what type K really is without additional help.

I'm not sure why it's not being resolved implicitly (so much of Scala implicits is still "magic" to me!), but it's fairly easy to pass in explicitly:

val results = Sorting.stableSort(ps)(classTag[Person], AgeOrdering)

Some rational and usages of TypeTag/ClassTag is discussed in TypeTags and Manifests.

Also see Scala: What is a TypeTag and how do I use it?

Community
  • 1
  • 1
user2864740
  • 60,010
  • 15
  • 145
  • 220
  • All good -- but then why does stableSort fail to compile with the provided Seq in the example above? – user48956 Dec 21 '13 at 01:13
  • @user48956 Include the *full* compiler message in the post and then we'll see some answers address that ;-) Also remove the `quickSort` call in such case as it simply isn't defined over Seq. – user2864740 Dec 21 '13 at 01:13
  • 2
    Couldn't get classTag/ClassTag to work, but adding mainfest[Person] did: http://stackoverflow.com/questions/2627919/scala-how-can-i-sort-an-array-of-tuples-by-their-second-element – user48956 Dec 21 '13 at 01:59
  • @user48956 The Tags are newer (in Scala 2.10); which version are you targeting? In any case, glad you solved it! – user2864740 Dec 21 '13 at 02:01
  • 1
    Using 2.10. Missing an import for classTag - where does that come from? ClassTag (with import reflect.ClassTag) complains about not enough parameters. – user48956 Dec 21 '13 at 02:05
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/43643/discussion-between-user2864740-and-user48956) – user2864740 Dec 21 '13 at 04:00