CL like sort in Scala

Question
1

What’s the most concise way to do a sort in Scala similar the the Common Lisp sort?
Does this already exist as an option of Scala standard library sort function?

The way it works is:
CL sort takes a sequence and a binary compare function and an optional third argument called key.
If key is given, it is a unary function which extracts the value from the element of the sequence to pass to the binary compare function.

http://www.lispworks.com/documentation/lw70/CLHS/Body/f_sort_.htm#sort

For example, to sort a list of pairs of numbers in increasing order, but comparing the 2nd element of
each pair, I’d pass the > function as 2nd argument, and a function to extract the 2nd element of the pair as the 3rd argument.

(sort my-list #'< :key #'cadr)

Another example. To sort a vector of strings ignoring leading white space, I’d pass as 3rd argument a unary function which takes a string and returns the substring skipping leading white space, and 2nd argument a binary function which compares two strings.

2

List(“Hello”, “World”).sortWith(_.length > _.length)

3

If you want to use the default Ordering[String] (meaning alphabetical increasing order):

Vector("      foo", "   bar").sortBy(_.trim)
4

Thanks Jasper and Shane, so if I need to specify both the sortWith function
and also the sortBy function, then I’ll need to repeat the sortBy function
inside the text of the sortWith function? And if its an anonymous
function, I’ll need to name it? Is that right?

seq.sortWith( (a,b) => compare_function(complicated_extractor_function(a),
complicated_extractor_function(b))

Of course I could write my own function to avoid that redundancy, but I’m
just wondering if there’s a library
function which already does it.

5

To get basically the same thing as the Common Lisp sort function:

def customCompare(a: Int, b: Int): Boolean = ???
List((4,2),(3,1),(1,3)).sortBy(_._2)(Ordering.fromLessThan(customCompare))

If you want to skip the custom Ordering creation, Scala provides the tools to add your own fancy lispSort method, though admittedly it gets a little intimidating when you do it with the collection classes:

implicit class LispSort[A, T[x] <: SeqLike[x, T[x]]](private val list: T[A]) extends AnyVal {
  def lispSort[B](f: A => B)(s: (B,B) => Boolean) = list.sortBy(f)(Ordering.fromLessThan(s))
}

List((4,2),(3,1),(1,3)).lispSort(_._2)(customCompare)
1 Like
6

You can pattern match in sortWith and encode a predicate over the tuple parts, if that helps:

scala> val xs = Vector((1,“c”),(2,“a”))
xs: scala.collection.immutable.Vector[(Int, String)] = Vector((1,c), (2,a))

scala> xs.sortWith{ case ((a1, b1), (a2, b2)) => b2 >= b1 }
res0: scala.collection.immutable.Vector[(Int, String)] = Vector((2,a), (1,c))

1 Like
7

jimka http://users.scala-lang.org/users/jimka
March 20

Thanks Jasper and Shane, so if I need to specify both the sortWith function
and also the sortBy function, then I’ll need to repeat the sortBy function
inside the text of the sortWith function? And if its an anonymous
function, I’ll need to name it? Is that right?

That’s right, if you can’t pull out a complicated extractor that sorts in
the right order for sortBy. (For instance, reversing order of a number is
equivalent to sorting on the negative value.)

seq.sortWith( (a,b) => compare_function(complicated_extractor_function(a),
complicated_extractor_function(b))

Of course I could write my own function to avoid that redundancy, but I’m
just wondering if there’s a library
function which already does it.

Look at Scala Standard Library 2.12.1 - scala.math.Ordering to
see what’s available for defining orderings. You have to specify the type,
but it’s entirely possible to

xs.sorted(Ordering.fromLessThan[Int]((a,b) => (a%5) < (b%4)).on((s: String)
=> s.length))

(Also, I was using the email interface, which is pretty broken, and shows up in my inbox way late, which explains why my answers are so slow.)

–Rex

1 Like