Sorting and lambda functions¶

Java class library offers e.g the class functions Arrays.sort for sorting plain arrays and Collections.sort for sorting lists (e.g. also ArrayList). These functions sort Java’s basic number and string types into “natural” ascending order. If the sorted objects do not readily support values comparison, or we wish to use some other sorting order (e.g. descending), we may give these sorting functions a custom comparison function as a second parameter. Java lists (including ArrayList) also have a member function sort that always requires a comparison function as a parameter (even when sorting Java’s basic number or string types).

A comparison function for values of some type T has the form int compare(T a, T b): the function takes two compared items of type T as parameters and returns an int that describes the result of comparing them. A negative return value means that the first item is smaller, zero that they are equal, and a positive that the second item is smaller.

It is often most convenient to define a custom comparison function as a so-called lambda function directly inside the sorting function call. A lambda function is a simplified anonymous function definition that consists of a parameter list, an arrow “->”, and the function body. Parameter types can be omitted from the parameter list, the parameter list does not need to be enclosed in parentheses if there is only one parameter, and the function body can be given either as a usual code block or alternatively as a single expression that computes the function’s return value (without performing an explicit return operation). Java lambda function syntax is almost identical with JavaScript lambda functions. We give below three simple lambda functions that perform essentially the same operations. Each of them takes two parameters a and b, which are assumed to be numbers (so they can be compared with < and >), and compares a and b according to descending sorting order. The example illustrates on one hand how the parameter types are optional and on the other hand how a simple function body can be given as an expression instead of a code block. Note that the middle lambda function is actually a little bit more restricted than the other two because it explicitly defines the parameter types as double. A lambda function without parameter types behaves as if the parameters were defined using the inferred parameter type var.

(a, b) -> a < b ? 1 : (a > b ? -1 : 0)

(double a, double b) -> a < b ? 1 : (a > b ? -1 : 0)

(a, b) -> {
  if(a < b) {
    return 1;
  }
  if(a > b) {
    return -1;
  }
  return 0;
}

The example below demonstrates Java’s sorting and lambda functions. The program sorts its command line parameters in a few different ways.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Sorting {
  public static void main(String[] argArr) {
    // Duplicate the command line parameters also into an ArrayList so we
    // can test sorting both arrays and lists.
    // List.of creates a list from values or an array given to it.
    ArrayList<String> argList = new ArrayList<>(List.of(argArr));

    System.out.println("Original order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("   list: " + argList);

    // The first sort without separate comparison function: ascending order.
    Arrays.sort(argArr);
    Collections.sort(argList);
    System.out.println("Default sorting (= increasing alphabetical) order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("   list: " + argList);

    // The second sort: descending case-insensitive alphabetical order.
    // We define the comparison function as a lambda function directly inside
    // the sorting function's parameter list. The function body is given as an
    // expression (which here calls String member function compareToIgnoreCase).
    // Both comparison functions below work identically. The first just gives
    // the String parameter types explicitly whereas the second omits them.
    Arrays.sort(argArr, (String a, String b) -> b.compareToIgnoreCase(a));
    Collections.sort(argList, (a, b) -> b.compareToIgnoreCase(a));
    System.out.println("Decreasing case-insensitive alphabetical order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("   list: " + argList);


    // The third sort: primarily length-based order and secondarily (to break ties
    // between equal lengths) in ascending case-insensitive alphabetical order.
    // Both lambda functions produce the same result, but the body of the first has
    // been defined as a normal code block whereas the second body is an expression.
    Arrays.sort(argArr, (a, b) -> {
      if(a.length() != b.length()) {
        return a.length() - b.length();
      }
      return a.compareToIgnoreCase(b);
    });
    argList.sort((a, b) -> (a.length() != b.length()) ? a.length() - b.length()
                                  : a.compareToIgnoreCase(b));
    System.out.println("Ordered by length, secondarily in alphabetical order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("   list: " + argList);
  }
}

Running this example program as java Sorting One two Three seven ten outputs:

Original order:
  array: [One, two, Three, seven, ten]
  list: [One, two, Three, seven, ten]
Default sorting (= increasing alphabetical) order:
  array: [One, Three, seven, ten, two]
  list: [One, Three, seven, ten, two]
Decreasing case-insensitive alphabetical order:
  array: [two, Three, ten, seven, One]
  list: [two, Three, ten, seven, One]
Ordered by length, secondarily in alphabetical order:
  array: [One, ten, two, seven, Three]
  list: [One, ten, two, seven, Three]

The preceding example did not take advantage of the fact that lambda functions can refer to variables that are visible at the code point where the lambda function is defined. This differs from C++ that requires a lambda function definition to explicitly state which external variables, if any, the lambda function uses.

If a comparison lambda function would have the form (a, b) -> x.f(a, b), where x is a class or an object, orthe form (a, b) -> a.f(b), one does not need to define a lambda function. In such cases we can directly pass the function f as such to the sorting function. This is possible by using Java’s function reference operator ::. When f is a member of the class C, it can be referenced in on of the three following ways:

If f is a class function, the function reference is always of form C::f and can be used instead of a lambda function of form (a, b) -> C.f(a, b).
If f is a non-static member function, the function reference syntax depends on whether a correspinding lambda function would have the form (a, b) -> o.f(a, b), where o is an object of some class C, or the form (a, b) -> a.f(b).
- The case (a, b) -> o.f(a, b) corresponds to function reference o::f.
- The case (a, b) -> a.f(b) corresponds to function reference C::f (that is, same as with a class function). But note that here f is a non-static member function that is called via the first parameter a, and only the second parameter b is passed to the funkction f.

It is important to note how Java interprets function references in different manner based on whether the reference is done via a class or an object.

The example code below performs the same sorts as the previous example but now using function references instead of lambda functions. The program output is identical.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class FuncRefs {

  // An inner helper class whose member function cmp compares strings in
  //  case-insensitive manner. The sorting order depends on the value given
  // as the constructor parameter reversed.
  private class StrCmp {
    // Do we compare according to a reversed (descending) order?
    private boolean reversed;

    StrCmp(boolean reversed) {
      this.reversed = reversed;
    }

    int cmp(String a, String b) {
      if(!reversed) {
        return a.compareToIgnoreCase(b);
      }
      return b.compareToIgnoreCase(a);
    }
  }

  // A member function that compares strings primarily based on lengths and
  // secondarily on case-insensitive ascending alphabetical order.
  private int lenCmp(String a, String b) {
    if(a.length() != b.length()) {
      return a.length() - b.length();
    }
    return a.compareToIgnoreCase(b);
  }

  // Like above, but now as a class function.
  private static int staticLenCmp(String a, String b) {
    if(a.length() != b.length()) {
      return a.length() - b.length();
    }
    return a.compareToIgnoreCase(b);
  }

  private void execute(String[] argArr) {
    ArrayList<String> argList = new ArrayList<>(List.of(argArr));
    System.out.println("Original order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("   list: " + argList);

    // Sorting to default ascending order would not require separate comparison
    // function. But we as an example provide a function reference to the member
    // function compareTo of the String class that does default comparison. It is
    // a non-static member function and hence the comparisons done during sorting
    // are of form a.compareTo(b). The correct rererence is thus String::compareTo.
    Arrays.sort(argArr, String::compareTo);
    Collections.sort(argList, String::compareTo);
    System.out.println("Default sorting (= increasing alphabetical) order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("   list: " + argList);

    // Create a StrCmp object that compares according to descending order.
    StrCmp descStrCmp = new StrCmp(true);

    // Sort both argArr and argList into descending case-insensitive order by
    // using the cmp member function of the object descStrcmp. Here the comparisons
    // done during sorting are of form descStrCmp.cmp(a, b), so we use a function
    // reference of form descStrCmp::cmp.
    Arrays.sort(argArr, descStrCmp::cmp);
    Collections.sort(argList, descStrCmp::cmp);
    System.out.println("Decreasing case-insensitive alphabetical order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("   list: " + argList);

    // Sort both argArr and argList primarily into ascending order primarily based
    // on length and secondarily on case-insensitive alphabetical order. The first
    // sort uses the non-static member function lenCmp that does the comparisons
    // as this.lenCmp(a, b), so the function reference is of form this::lenCmp.
    // The second sort uses the class function staticLenCmp and the function
    // reference this is of form FuncRefs::staticLenCmp.
    Arrays.sort(argArr, this::lenCmp);
    argList.sort(FuncRefs::staticLenCmp);
    System.out.println("Ordered by length, secondarily in alphabetical order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("   list: " + argList);
  }

  // This example uses non-static member functions StrCmp and lenCmp. To make these
  // available, we create a FuncRefs object dynamically and execute the actual program
  // logic by calling the above defined member function "execute".
  public static void main(String[] argArr) {
    new FuncRefs().execute(argArr);
  }
}

We will later discuss how to define a Java function that accepts a lambda function or a function reference as a parameter.