How can I sort List[Int] objects?

Question

What I want to do is sort List objects in Scala, not sort the elements in the list. For example If I have two lists of Ints:

val l1 = List(1, 2, 3, 7)
val l2 = List(1, 2, 3, 4, 10)

I want to be able to put them in order where l1 > l2.

I have created a case class that does what I need it to but the problem is that when I use it none of my other methods work. Do I need to implement all the other methods in the class i.e. flatten, sortWith etc.?

My class code looks like this:

class ItemSet(itemSet: List[Int]) extends Ordered[ItemSet] {

  val iSet: List[Int] = itemSet

  def compare(that: ItemSet) = {

    val thisSize = this.iSet.size
    val thatSize = that.iSet.size
    val hint = List(thisSize, thatSize).min
    var result = 0
    var loop = 0

    val ths = this.iSet.toArray
    val tht = that.iSet.toArray

    while (loop < hint && result == 0) {
      result = ths(loop).compare(tht(loop))
      loop += 1
    }
    if (loop == hint && result == 0 && thisSize != thatSize) {
      thisSize.compare(thatSize)
    } else
      result
  }

}

Now if I create an Array of ItemSets I can sort it:

val is1 = new ItemSet(List(1, 2, 5, 8))
val is2 = new ItemSet(List(1, 2, 5, 6))
val is3 = new ItemSet(List(1, 2, 3, 7, 10))

Array(is1, is2, is3).sorted.foreach(i => println(i.iSet))

scala> List(1, 2, 3, 7, 10)
List(1, 2, 5, 6)
List(1, 2, 5, 8)

The two methods that are giving me problems are:

def itemFrequencies(transDB: Array[ItemSet]): Map[Int, Int] = transDB.flatten.groupBy(x => x).mapValues(_.size)

The error I get is:

Expression of type Map[Nothing, Int] doesn't conform to expected type Map[Int, Int]

And for this one:

def sortListAscFreq(transDB: Array[ItemSet], itemFreq: Map[Int, Int]): Array[List[Int]] = {
  for (l <- transDB) yield
    l.sortWith(itemFreq(_) < itemFreq(_))
}

I get:

Cannot resolve symbol sortWith.

Is there a way I can just extend List[Int] so that I can sort a collection of lists without loosing the functionality of other methods?

Answer 1

The standard library provides a lexicographic ordering for collections of ordered things. You can put it into scope and you're done:

scala> import scala.math.Ordering.Implicits._
import scala.math.Ordering.Implicits._

scala> val is1 = List(1, 2, 5, 8)
is1: List[Int] = List(1, 2, 5, 8)

scala> val is2 = List(1, 2, 5, 6)
is2: List[Int] = List(1, 2, 5, 6)

scala> val is3 = List(1, 2, 3, 7, 10)
is3: List[Int] = List(1, 2, 3, 7, 10)

scala> Array(is1, is2, is3).sorted foreach println
List(1, 2, 3, 7, 10)
List(1, 2, 5, 6)
List(1, 2, 5, 8)

The Ordering type class is often more convenient than Ordered in Scala—it allows you to specify how some existing type should be ordered without having to change its code or create a proxy class that extends Ordered[Whatever], which as you've seen can get messy very quickly.