# 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());`

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.

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?

• (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)```

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)
{
}
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

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

1. 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.

2. 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[]`.

3. In this program, reimplement `filter` so that it works with arrays.