Higher Order Functions

The Comparator Interface

Arrays.sort(array) sorts the given array...
...provided the elements implement the Comparable interface
What if you have a class that doesn't?
Or if you want to sort by another criterion?
Then supply an object of a class that implements the Comparator interface
```
public interface Comparator<T>
{
   int compare(T a, T b);
}
```
compare method returns
- a negative integer if a comes before b
- a positive integer if a comes after b
- zero if a and b are equal, or if their order doesn't matter

Comparator with Lambda Expressions

Before Java 8, using Comparator was cumbersome.
1. Come up with a class that implements Comparable
2. Implement compare method
3. Construct an object
It's a functional interface ⇒ Can use lambda expression

Sort strings by increasing length:

Arrays.sort(words, (a, b) -> a.length() - b.length());

Your Turn

Complete this program to sort an array of strings by decreasing length.

Comparator.comparing

Look again at

Arrays.sort(words, (a, b) -> a.length() - b.length());

How would we sort bank accounts by balance?

Arrays.sort(accounts, (a, b) -> v.getBalance() - w.getBalance());

Ok, not quite. Need to use Double.compare:

(a, b) -> Double.compare(v.getBalance(), w.getBalance())

That's a general principle—the comparator applies a measurement and compares the outputs.
The static method Comparator.comparing yields such a comparator:
```
Arrays.sort(words, Comparator.comparing(w -> w.length()));
```
Aside: As of Java 8, interfaces can have static methods. They work just like static methods in classes.

Your Turn

Complete this program to sort a collection of countries by population and by population density (people per square kilometer).

Use Comparator.comparing(...).

What Does Comparator.comparing Do?

It receives a “function”
- (really, an object of some class that implements a functional interface)
It returns a “function”
- (really, an object...)
It's a “higher-order function”

Like this:

public static <T> Comparator<T> comparing(Measurer<T> meas)
{
   return (a, b) -> Double.compare(
      meas.getMeasure(a), meas.getMeasure(b));
}

Actually, in the Java API, it doesn't use a Measurer but a Function
```
public interface Function<T, R>
{
   R apply(T arg)
}
```

Specifically,

static <T,U extends Comparable<? super U>>
   Comparator<T> comparing(Function<? super T,? extends U> measure)

Your Turn

Complete this program to provide a higher order function Comparators.reverse that reverses a comparator. For example, if comp sorts strings by increasing length, then Comparators.reverse(comp) should sort by decreasing length.

Higher-Order Functions

A “function” that consumes and/or produces “functions”

Example: filter consumes function

public static <T> List<T> filter(List<T> values, Predicate<T> p)
{
   List<T> result = new ArrayList<>();
   for (T value : values)
   {
      if (p.test(value)) { result.add(value); }
   }
   return result;
}

Here, Predicate is a standard functional interface:

public interface Predicate<T>
{
   boolean test(T arg);
}

Typical use:

List<String> longWords = filter(wordList, w -> w.length() > 10);

Higher-Order Functions 2

Suppose we want to find all strings that contain the word "and"

List<String> andWords = filter(wordList, w -> w.indexOf("and") >= 0);

What if we want to find another word?

Can write a method that yields the predicate for an arbitrary target:

public static Predicate<String> contains(String target)
{
   return s -> s.indexOf(target) >= 0;
}

Pass the result to a method expecting a Predicate:

List<String> andWords = filter(wordList, contains("and"));

contains is also a higher-order function

Your Turn

Complete this program to provide a higher order function Words.longerThan that yields a predicate testing whether a string has length > n.

Note the nifty methods and and negate of the Predicate interface. In Java 8, it is legal to have “default” methods in an interface. Check out their implementations here.

Method Expressions

Common to have lambda expressions that just invoke a method
Use method expression: ClassName::methodName
```
String::toUpperCase
```
Parameters are added “at the right places:”
```
(String w) -> w.toUpperCase()
```
If method has a parameter, the lambda expression gets two parameters:
```
String::compareTo
```
is the same as
```
(String s, String t) -> s.compareTo(t)
```

Also works with static methods:

Double::compare

is the same as

(double x, double y) -> Double.compare(x, y)

Can have an object to the left of :: symbol:
```
System.out::println
```
is the same as
```
x -> System.out.println(x)
```

Constructor Expressions

Like method expression, with special method name new
For example,
```
BankAccount::new
```
is equivalent to a lambda expression that invokes the BankAccount constructor.
Which constructor?

Depends on context—could be

() -> new BankAccount()

or

b -> new BankAccount(b)

Constructor expressions can construct arrays:
```
String[]::new
```
Same as
```
(n: int) -> new String[n]
```
Used to overcome limitation of Java generics—can't construct array of generic type.

Method Expressions and Comparators

Comparator.comparing makes a comparator from an extractor function:

Comparator<String> comp = Comparator.comparing(t -> t.length())

Same as

Comparator<String> comp = (v, w) -> v.length() - w.length();

Note that the extractor function makes a single method call
Write as method reference:
```
Comparator.comparing(String::length)
```
Reads nicely: the comparator that compares strings by their length.
Can add a secondary comparison with thenComparing:
```
Collections.sort(countries,
   Comparator.comparing(Country::getContinent)
      .thenComparing(Country::getName));
```
- Countries are compared first by continent.
- If the continents are the same, they are compared by name.
Easy to read, easy to write
Thanks to lambda expressions, method expressions, higher order functions

Exercises

Complete this program to sort the list of words first by the number of vowels, then in alphabetical order. Use Comparator.comparing and two method expressions.
The Collection<T> interface has two toArray methods:
```
Object[] 	toArray()
<T> T[] 	toArray(T[] a)
```
The first one returns an array of type Object, which is unsatisfactory. The second one requires the caller to provide an array and uses reflection to grow it if it was too short. Until the invention of constructor expressions, there was no better way.

In this program, there is a method that allows you to pass a constructor expression. Call that method to turn a List<String> into a String[].
In this program, reimplement filter so that it works with arrays.