CODEWITHSUNDEEP
scalasortingfunctional-programmingscala-collections
jimmy_terra
jimmy_terra

Reputation: 1520

How to sort a list in Scala by an unknown number of items?

I have seen this question How to sort a list in Scala by two fields?

This is similar but not a duplicate.

I can easily sort a List[DataPoint] using the answer from the earlier question:

case class DataPoint(keys: List[String], value: Double)

listOfDataPoints.sortBy(point => (point.keys(0), point.keys(1)))

However I don't know the number of items in keys. What I do know is that every DataPoint in a given list will have the same number of keys, so there is never a case of sorting List("a") and List("a", "b").

So how can I sort the list by an unknown number of keys?

Upvotes: 3

Views: 571

Answers (2)

Shadowlands
Shadowlands

Reputation: 15074

You could define your own Ordering[List[String]]. For example, you could define:

class ListOrdering[A](implicit aOrd: math.Ordering[A]) extends Ordering[List[A]] {    
  def compare(a1: List[A], a2: List[A]) = (a1, a2) match {
    case (Nil, _) => if (a2.isEmpty) 0 else -1
    case (_, Nil) => 1
    case (h1 :: t1, h2 :: t2) => if (aOrd.compare(h1, h2) == 0) compare(t1, t2) else aOrd.compare(h1, h2)
  }    
}

Then making the following available somewhere in scope:

implicit val listOrd = new ListOrdering[String]

you can write:

dps.sortBy(_.keys)

and it should work.

Note that my definition of ListOrdering is generalised to be useable for any type A with an implicit Ordering[A] in scope, and can handle lists of variable length (even though you say that in your case your key lists are always the same length).

Upvotes: 1

Martijn
Martijn

Reputation: 12092

What you want to do is

datapoints.sortby(_.keys)

This evidently doesn't work. When we take a look at the signature of sortby, it becomes evident why it doesn't work: 

sortBy[B](f: (A) ⇒ B)(implicit ord: math.Ordering[B]): List[A]

Your B is a List[String] and you don't have an instance of Ordering[List[String]]. So what do we do? We supply one!

What we need to do for that is implement the method

def compare(x: T, y: T): Int

We want to compare on the following:

  • If the first key is different between two items, then use that key for sorting
  • Otherwise, sort by the rest of the List
  • If one of the lists is empty, the other one comes first[1]

Our T's here are Strings, but all we need for the T's is to be comparable for this, so we can be a little more general.

def listOrdering[T](implicit ord: Ordering[T]): Ordering[List[T]] = new Ordering[List[T]] {
  def compare(x: List[T], y: List[T]): Int = {
    (x, y) match {
      case (Nil, Nil) => 0 //both empty => equal
      case (Nil, _)   => -1 //one of the two empty => empty is the smallest
      case (_, Nil)   => 1 //one of the two empty => empty is the smallest
      case (xhead :: xtail, yhead :: ytail) => {
        val headdiff = ord.compare(xhead, yhead)
        if (headdiff == 0) compare(xtail, ytail) //recursively compare the tails if equivalent
        else (headdiff ) //otherwise, the difference in the heads
      }  
    }
  }
}

now we can supply the ordering to the sortby method explicitly:

datapoints.sortby(_.keys)(listOrdering)

or provide them in implicit scope

[1]: you indicated this never happens, so any choice is good enough

Upvotes: 3

Related Questions