4.12.2.1 - Higher-order functions, map, filter and fold (Java)

Functional programs and transformations

A functional program describes a result through function applications and transformations of values.

In an imperative solution, a loop might update a running total or overwrite elements of an array. In a functional solution, a transformation describes what each result should be, and another operation combines those results. Both can solve a problem; the functional account makes the passed rules and their input/output relationships explicit.

Haskell, Standard ML, Scheme and Lisp are examples of functional languages. Java supports functional programming alongside its other paradigms through features such as lambdas and streams. Using Java does not make every Java program functional: its behaviour and structure matter.

The rule n -> n * n is pure for these integer examples. A rule that increments a shared counter on every call has a side effect; a rule depending on a changing external counter may produce different results for the same argument. Functional transformations commonly use pure rules and avoid changing the input collection. Java still permits side effects, so the programmer must preserve these properties deliberately.

An immutable value cannot be changed after construction. Our pipelines leave their source lists unchanged and return new results. That does not mean every Java result list is immutable: Collectors.toList() does not promise an immutable list. A pipeline's non-mutating behaviour and a list's mutability are different questions.

Functions as arguments and results

A higher-order function accepts a function as an argument, returns a function, or does both.

First-class describes what the language allows a function value to do. Higher-order describes a particular function's input or output. A rule from integer to integer can be first-class without being higher-order; a function taking that rule as an argument is higher-order.

This complete program includes both cases. applyRule receives a function; makeOffset returns one. In mathematical notation their types are

import java.util.function.Function;

public class Main {
    static int applyRule(Function<Integer, Integer> rule, int value) {
        return rule.apply(value);
    }

    static Function<Integer, Integer> makeOffset(int offset) {
        return value -> value + offset;
    }

    public static void main(String[] args) {
        Function<Integer, Integer> addThree = makeOffset(3);
        System.out.println(applyRule(addThree, 8));
    }
}

The output is 11. The makeOffset(3) call returns a function retaining 3; the later call applies it to 8. The methods accept or return Function values, rather than accepting the numbers those functions would have produced already. This separation lets a single operation work with many different rules.

Map and transformed elements

Map applies a supplied function to every element and returns the corresponding results.

If $f:A\rightarrow B$, mapping $f$ over a list of $A$ values returns a list of $B$ values. For the rule $d(x)=2x$,

The output has one result per input, including repeated values. Map transforms values; it does not choose a subset. Mapping over an empty list produces an empty list without applying the rule to an element.

Java's stream map accepts a Function. A stream is a sequence processed by a pipeline, not a stored list you can index. An intermediate operation such as map describes a transformation; a terminal operation such as collect obtains the result. Collectors.toList() gathers the results into a list.

These statements belong inside main, with List, Arrays, Function and Collectors imported:

List<Integer> numbers = Arrays.asList(2, 5, 8);
Function<Integer, Integer> doubleValue = n -> n * 2;
List<Integer> doubled = numbers.stream()
    .map(doubleValue)
    .collect(Collectors.toList());
System.out.println(doubled);
System.out.println(numbers);