Functional programming techniques - Beyond Java 8 - Java 8 in Action: Lambdas, streams, and functional-style programming (2015)

Java 8 in Action: Lambdas, streams, and functional-style programming (2015)

Part IV. Beyond Java 8

Chapter 14. Functional programming techniques

This chapter covers

· First-class citizens, higher-order functions, currying, and partial application

· Persistent data structures

· Lazy evaluation and lazy lists as generalizing Java streams

· Pattern matching and how to simulate it in Java

· Referential transparency and caching

In chapter 13 you saw how to think functionally; thinking in terms of side-effect-free methods can help you write more maintainable code. In this chapter, we introduce more advanced functional programming techniques. You can view this chapter as a mix of practical techniques to apply in your codebase as well as academic information that will make you a more knowledgeable programmer. We discuss higher-order functions, currying, persistent data structures, lazy lists, pattern matching, caching with referential transparency, and combinators.

14.1. Functions everywhere

In chapter 13 we used the phrase functional-style programming to mean that the behavior of functions and methods should be like that of mathematical-style functions—no side effects. Functional-language programmers often use the phrase with more generality to mean that functions may be used like other values: passed as arguments, returned as results, and stored in data structures. Such functions that may be used like other values are referred to as first-class functions. This is exactly what Java 8 adds over previous versions of Java: you may use any method as a function value, using the :: operator to create a method reference, and lambda expressions (for example, (int x) -> x + 1) to directly express function values. In Java 8 it’s perfectly valid to store the method Integer.parseInt in a variable by using a method reference as follows:

Function<String, Integer> strToInt = Integer::parseInt;

14.1.1. Higher-order functions

So far we’ve mainly used the fact that function values are first class only in order to pass them to Java 8 stream-processing operations (as in chapters 47) and to achieve the very similar effect of behavior parameterization when we passed Apple::isGreen-Apple as a function value tofilterApples in chapters 1 and 2. But this was just a start. Another interesting example was the use of the static method Comparator.comparing, which takes a function as parameter and returns another function (a Comparator), as illustrated in the following code and figure 14.1:

Figure 14.1. comparing takes a function as parameter and returns another function.

Comparator<Apple> c = comparing(Apple::getWeight);

We did something similar when we were composing functions in chapter 3 to create a pipeline of operations:

Function<String, String> transformationPipeline

= addHeader.andThen(Letter::checkSpelling)

.andThen(Letter::addFooter);

Functions (like Comparator.comparing) that can do at least one of the following are called higher-order functions within the functional programming community:

· Take one or more functions as parameter

· Return a function as result

This directly relates to Java 8 functions because they can not only be passed as arguments but also returned as results, assigned to local variables, or even inserted into structures. For example, a pocket calculator program might have a Map<String, Function<Double, Double>>, which maps the String “sin” to Function<Double, Double> to hold the method reference Math::sin. We did something similar when we introduced the factory design pattern in chapter 8.

For readers who liked the calculus example at the end of chapter 3, you can regard the type of differentiation as

Function<Function<Double,Double>, Function<Double,Double>>

because it takes a function as argument (for example, (Double x) -> x * x) and returns a function as result (in this example (Double x) -> 2 * x). We’ve written this as a function type (the leftmost Function) to explicitly affirm the fact that you could pass this differentiating function to yet another function. But it’s good to recall that the type for differentiating and the signature

Function<Double,Double> differentiate(Function<Double,Double> func)

say the same thing.

Side effects and higher-order functions

We noted in chapter 7 that functions passed to stream operations should generally be side-effect free, and we noted the problems that arise otherwise (such as incorrect results, perhaps even unpredictable results due to race conditions we hadn’t thought of). This principle also applies in general when you use higher-order functions. When writing a higher-order function or method, you don’t know in advance what arguments it will be passed—and if the arguments have side effects, then what these might do! It becomes far too complicated to reason about what your code does if it uses functions passed as arguments that make unpredictable changes to the state of your program; they might even interfere with your code in some hard-to-debug way. So it’s a good design principle to document what side effects you’re willing to accept from functions passed as parameters, and “none” is the best of all!

We now turn to currying: a technique that can help you modularize functions and reuse code.

14.1.2. Currying

Before we give the theoretical definition of currying, let’s look at an example. Applications almost always need to be internationalized, and so converting from one set of units to another set is a problem that comes up repeatedly.

Unit conversion always involves a conversion factor and from time to time a baseline adjustment factor. For example, the formula to convert Celsius to Fahrenheit is CtoF(x) = x*9/5 + 32.

The basic pattern of all unit conversion is as follows:

1. Multiply by the conversion factor.

2. Adjust the baseline if relevant.

You can express this pattern with the following general method:

static double converter(double x, double f, double b) {

return x * f + b;

}

Here x is the quantity you want to convert, f is the conversion factor, and b is the baseline. But this method is a bit too general. You’ll typically find you require a lot of conversions between the same pair of units, kilometers to miles, for example. You could obviously call the convertermethod with three arguments on each occasion, but supplying the factor and baseline each time would be tedious and you might accidentally mistype them.

You could write a completely new method for each application, but that would miss the reuse of the underlying logic.

Here’s an easy way to benefit from the existing logic while tailoring the converter for particular applications. You can define a “factory” that manufactures one-argument conversion functions to exemplify the idea of currying. Here it is:

static DoubleUnaryOperator curriedConverter(double f, double b){

return (double x) -> x * f + b;

}

Now all you have to do is pass it the conversion factor and baseline (f and b), and it will obligingly return a function (of x) to do exactly what you asked for. For example, you can now use the factory to produce any converter you require:

DoubleUnaryOperator convertCtoF = curriedConverter(9.0/5, 32);

DoubleUnaryOperator convertUSDtoGBP = curriedConverter(0.6, 0);

DoubleUnaryOperator convertKmtoMi = curriedConverter(0.6214, 0);

Because DoubleUnaryOperator defines a method applyAsDouble, you can use your converters as follows:

double gbp = convertUSDtoGBP.applyAsDouble(1000);

As a result, your code is more flexible and it reuses the existing conversion logic! Let’s reflect on what you’re doing here. Instead of passing all the arguments x, f, and b all at once to the converter method, you only ask for the arguments f and b and return another function, which when given an argument x returns x * f + b. This enables you to reuse the conversion logic and create different functions with different conversion factors.

Theoretical definition of currying

Currying is a technique where a function f of two arguments (x and y, say) is seen instead as a function g of one argument that returns a function also of one argument. The value returned by the latter function is the same as the value of the original function, that is, f(x,y) = (g(x))(y).

Of course, this generalizes: you can curry a six-argument function to first take arguments numbered 2, 4, and 6 returning a function taking argument 5, which returns a function taking the remaining arguments, 1 and 3.

When some but fewer than the full complement of arguments have been passed, we often say the function is partially applied.

Now we turn to another aspect of functional-style programming. Can you really program using data structures if you’re forbidden from modifying them?

14.2. Persistent data structures

In this section, we explore the use of data structures used in functional-style programs. These come under various names, such as functional data structures and immutable data structures, but perhaps most common is persistent data structures (unfortunately this terminology clashes with the notion of persistent in databases, meaning “outliving one run of the program”).

The first thing to note is that a functional-style method isn’t allowed to update any global data structure or any structure passed as a parameter. Why? Because calling it twice is likely to produce different answers—violating referential transparency and the ability to understand the method as a simple mapping from arguments to results.

14.2.1. Destructive updates vs. functional

Let’s consider the problems that can otherwise arise. Suppose you represent train journeys from A to B as a mutable TrainJourney class (a simple implementation of a singly linked list), with an int field modeling some detail of the journey such as the price of the current leg of the journey. Journeys requiring you to change trains will have several linked TrainJourney objects using the onward field; a direct train or final leg of a journey will have onward being null:

class TrainJourney {

public int price;

public TrainJourney onward;

public TrainJourney(int p, TrainJourney t) {

price = p;

onward = t;

}

}

Now suppose you have separate TrainJourney objects representing a journey from X to Y and from Y to Z. You may wish to create one journey that links the two TrainJourney objects (that is, X to Y to Z).

A simple traditional imperative method to link these train journeys is as follows:

static TrainJourney link(TrainJourney a, TrainJourney b){

if (a==null) return b;

TrainJourney t = a;

while(t.onward != null){

t = t.onward;

}

t.onward = b;

return a;

}

This works by finding the last leg in the TrainJourney for a and replacing the null marking the end of a’s list with list b (you need a special case if a has no elements).

Here’s the problem: suppose a variable firstJourney contains the route from X to Y and a variable secondJourney contains the route from Y to Z. If you call link(firstJourney, secondJourney), this code destructively updates firstJourney to also contain secondJourney, so in addition to the single user who requests a trip from X to Z seeing the combined journey as intended, the journey from X to Y has been destructively updated. Indeed, the firstJourney variable is no longer a route from X to Y but one from X to Z! This will break code that depends onfirstJourney not being modified! Suppose firstJourney represented the early morning London–Brussels train, which all subsequent users trying to get to Brussels will be surprised to see as requiring an onward leg, perhaps to Cologne. We’ve all fought battles with such bugs concerning how visible a change to a data structure should be.

The functional-style approach to this problem is to ban such side-effecting methods. If you need a data structure to represent the result of a computation, you should make a new one and not mutate an existing data structure as done previously. This is often best practice in standard object-oriented programming too. A common objection to the functional approach is that it causes excess copying and that the programmer says, “I’ll just remember” or “I’ll just document” that it has side effects. But this leaves traps for maintenance programmers who later will have to deal with your code. Thus the functional-style solution is as follows:

static TrainJourney append(TrainJourney a, TrainJourney b){

return a==null ? b : new TrainJourney(a.price, append(a.onward, b));

}

This code is clearly functional style (it uses no mutation at all, even locally) and doesn’t modify any existing data structures. Note, however, that the code does not create an entirely new TrainJourney—if a is a sequence of n elements and b a sequence of m elements, then it returns a sequence of n+m elements of which the first n elements are new nodes and the final m elements share with the TrainJourney b. Note that users are also required not to mutate the result of append because in doing so they may corrupt the trains passed as sequence b. Figures 14.2 and 14.3illustrate the difference between the destructive append and the functional-style append.

Figure 14.2. The data structure is destructively updated.

Figure 14.3. Functional style, no modifications to the data structure

14.2.2. Another example with Trees

Before leaving this topic, let’s consider another data structure—that of a binary search tree that might be used to implement a similar interface to a HashMap. The idea is that a Tree contains a String representing a key and an int representing its value, perhaps names and ages:

class Tree {

private String key;

private int val;

private Tree left, right;

public Tree(String k, int v, Tree l, Tree r) {

key = k; val = v; left = l; right = r;

}

}

class TreeProcessor {

public static int lookup(String k, int defaultval, Tree t) {

if (t == null) return defaultval;

if (k.equals(t.key)) return t.val;

return lookup(k, defaultval,

k.compareTo(t.key) < 0 ? t.left : t.right);

}

// other methods processing a Tree

}

You want to make use of the binary search tree for looking up String values to produce an int. Now consider how you might update the value associated with a given key (for simplicity you’ll start by assuming the key is already present in the tree):

public static void update(String k, int newval, Tree t) {

if (t == null) { /* should add a new node */ }

else if (k.equals(t.key)) t.val = newval;

else update(k, newval, k.compareTo(t.key) < 0 ? t.left : t.right);

}

Adding a new node is trickier; the easiest way is to make the method update return the Tree that has just been traversed (this will be unchanged unless you had to add a new node). This code is now slightly clumsier (because the user needs to remember that update tries to update the tree in place, returning the same tree as passed, but if the original tree was empty, then a new node is returned as result instead):

public static Tree update(String k, int newval, Tree t) {

if (t == null)

t = new Tree(k, newval, null, null);

else if (k.equals(t.key))

t.val = newval;

else if (k.compareTo(t.key) < 0)

t.left = update(k, newval, t.left);

else

t.right = update(k, newval, t.right);

return t;

}

Note that both versions of update once again mutate the existing Tree, meaning that all users of the map stored in the tree will see the mutation.

14.2.3. Using a functional approach

So how might you do this functionally? You need to create a new node for the new key-value pair, but you also need to create new nodes on the path from the root of the tree to the new node (in general this isn’t very expensive, if the tree is of depth d and reasonably well balanced, then it can have 2d entries, so you re-create only a small fraction of it):

public static Tree fupdate(String k, int newval, Tree t) {

return (t == null) ?

new Tree(k, newval, null, null) :

k.equals(t.key) ?

new Tree(k, newval, t.left, t.right) :

k.compareTo(t.key) < 0 ?

new Tree(t.key, t.val, fupdate(k,newval, t.left), t.right) :

new Tree(t.key, t.val, t.left, fupdate(k,newval, t.right));

}

We’ve written this as a single conditional expression instead of using if-then-else to emphasize the idea that the body is only a single expression with no side effects, but you may prefer to write an equivalent if-then-else chain, each containing a return.

So what’s the difference between update and fupdate? We noted previously that the method update assumes every user wants to share the identical data structure and see updates caused by any part of the program. Hence it’s vital (but often overlooked) in nonfunctional code that whenever you add some form of structured value to a tree, you copy it, because, who knows, someone may later assume they can update it. By contrast, fupdate is purely functional. It creates a new Tree as a result but sharing as much as it can with its argument. Figure 14.4 illustrates this idea. You have a tree consisting of nodes storing a name and an age of a person. Calling fupdate doesn’t modify the existing tree but creates new nodes “living at the side of” the tree without harming the existing data structure.

Figure 14.4. No existing data structure was harmed during the making of this update to the Tree.

Such functional data structures are often called persistent—their values persist and are isolated from changes happening elsewhere—so as a programmer you’re sure fupdate won’t mutate the data structures passed as its arguments. There’s just one proviso: the other side of the treaty is you require all users of persistent data structures to follow the do-not-mutate requirement. If not, a programmer who disregards this might mutate the result of fupdate (for example, changing Emily’s 20). This would then be visible as an (almost certainly unwanted) unexpected and delayed change to the data structure passed as argument to fupdate!

Seen in these terms, fupdate can often be more efficient: the “no mutation of existing structure” rule allows structures that differ only slightly from each other (for example, the Tree seen by user A and the modified version seen by user B) to share storage for common parts of their structure. You can get the compiler to help enforce this “no mutation of existing structure” rule by declaring fields key, val, left, and right of class Tree to be final; but remember that final protects only a field and not the object pointed to, which may need its own fields to befinal to protect it, and so on.

Ah, but you might say, “I want updates to the tree to be seen by some users (but admittedly not by some others).” Well, there are two choices: one is the classical Java solution (be very careful when updating something to check whether you need to copy it first). The other is the functional-style solution: you logically make a new data structure whenever you do an update (so nothing is ever mutated) and just arrange to pass the correct version of the data structure to users as appropriate. This idea could be enforced through an API. If certain clients of the data structure need to have updates visible, they should go through an API that returns the latest version. Clients who don’t want updates visible (such as for long-running statistical analysis) simply use whatever copy they retrieved, knowing that it can’t be mutated from under them.

One might remark that this technique is like “updating” a file on a CD-R, which allows a file to be written only once by burning with a laser; multiple versions of the file are all stored on the CD (smart CD authoring software might even share common parts of multiple versions), and you pass the appropriate block address of the start of file (or a filename encoding the version within its name) to select which version you want to use. In Java things are rather better than on a CD, in that old versions of the data structure that can no longer be used will be garbage collected.

14.3. Lazy evaluation with streams

You saw in previous chapters that streams are a great way to process a collection of data. But for various reasons, including efficient implementation, the Java 8 designers added streams to Java in a rather specific way. In particular, one limitation is that you can’t define a stream recursively because a stream can be consumed only once. We show in the coming section how this can sometimes be problematic.

14.3.1. Self-defining stream

Let’s revisit our example from chapter 6 of generating prime numbers to understand this idea of a recursive stream. You saw that, perhaps as part of the class MyMathUtils, you can compute a stream of prime numbers as follows:

public static Stream<Integer> primes(int n) {

return Stream.iterate(2, i -> i + 1)

.filter(MyMathUtils::isPrime)

.limit(n);

}

public static boolean isPrime(int candidate) {

int candidateRoot = (int) Math.sqrt((double) candidate);

return IntStream.rangeClosed(2, candidateRoot)

.noneMatch(i -> candidate % i == 0);

}

But this solution is somewhat awkward: you have to iterate through every number every time to see if it can be exactly divided by a candidate number. (Actually you need only test with numbers that have been already classified as prime.)

Ideally the stream should filter out numbers divisible by the prime it’s producing on the go! This sounds crazy, so we’ll try to sketch out how this might work:

1. You need a stream of numbers from which you’ll select prime numbers.

2. From that stream you take the first number (the head of the stream), which will be a prime number (at the initial step this will be 2).

3. You then filter all the numbers divisible by that number from the tail of the stream.

4. The resulting tail is the new stream of numbers that you can use to find prime numbers. Essentially you go back to step 1, so this algorithm is recursive.

Note that this algorithm is “poor” for a few reasons.[1] But it’s simple to reason about algorithms for the purpose of working with streams. Let’s try to write this algorithm using the Streams API.

1 More information about why the algorithm is poor can be found at www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf.

Step 1: Get a stream of numbers

You can get an infinite stream of numbers starting from 2 using the method IntStream.iterate, which we described in chapter 5 as follows:

static Intstream numbers(){

return IntStream.iterate(2, n -> n + 1);

}

Step 2: Take the head

An IntStream comes with the method findFirst, which can be used to return the first element:

static int head(IntStream numbers){

return numbers.findFirst().getAsInt();

}

Step 3: Filter the tail

Define a method to get the tail of a stream:

static IntStream tail(IntStream numbers){

return numbers.skip(1);

}

Given the head of the stream, you can filter the numbers as follows:

IntStream numbers = numbers();

int head = head(numbers);

IntStream filtered = tail(numbers).filter(n -> n % head != 0);

Step 4: Recursively create a stream of primes

Here comes the tricky part. You might be tempted to try passing back the resulting filtered stream so you can take its head and filter more numbers, like this:

static IntStream primes(IntStream numbers) {

int head = head(numbers);

return IntStream.concat(

IntStream.of(head),

primes(tail(numbers).filter(n -> n % head != 0))

);

}

Bad news

Unfortunately, if you run the code in step 4, you’ll get the following error: “java.lang.IllegalStateException: stream has already been operated upon or closed.” Indeed, you’re using two terminal operations to split the stream into its head and tail: findFirst and skip. Remember fromchapter 4 that once you call a terminal operation on a stream, it’s consumed forever!

Lazy evaluation

There’s an additional, more important problem: the static method IntStream.concat expects two instances of a stream. But its second argument is a direct recursive call to primes, resulting in an infinite recursion! For many Java purposes, restrictions on Java 8 streams such as “no recursive definitions” are unproblematic and give your database-like queries expressivity and the ability to parallelize. Thus, the Java 8 designers chose a sweet spot. Nonetheless, the more-general features and models of streams from functional languages such as Scala and Haskell can be a useful addition to your programming tool box. What you need is a way to lazily evaluate the call to the method primes in the second argument of concat. (In a more technical programming language vocabulary we refer to this as lazy evaluation, nonstrict evaluation, or even call by name.) Only when you need to process the prime numbers (for example, with the method limit) should the stream be evaluated. Scala (which we explore in the next chapter) provides support for this idea. In Scala you can write the previous algorithm as follows, where the operator #:: does lazy concatenation (the arguments are evaluated only when you need to actually consume the stream):

def numbers(n: Int): Stream[Int] = n #:: numbers(n+1)

def primes(numbers: Stream[Int]): Stream[Int] = {

numbers.head #:: primes(numbers.tail filter (n -> n % numbers.head != 0))

}

Don’t worry about this code. Its only purpose is to show you an area of difference between Java and other functional programming languages. It’s good to reflect just a moment about how the arguments are evaluated. In Java when you call a method, all its arguments are fully evaluated immediately. But in Scala using #::, the concatenation returns immediately and the elements are evaluated only when needed. Now we turn to implementing this idea of lazy lists directly in Java.

14.3.2. Your own lazy list

Java 8 streams are often described as lazy. They’re lazy in one particular aspect: a stream behaves like a black box that can generate values on request. When you apply a sequence of operations to a stream, these are merely saved up. Only when you apply a terminal operation to a stream is anything actually computed. This has the great advantage when you apply several operations (perhaps a filter and a map followed by a terminal operation reduce) to a stream; then the stream has to be traversed only once instead of for each operation.

In this section we consider the notion of lazy lists, which are a form of a more general stream (lazy lists form a similar concept to stream). Lazy lists also provide an excellent way of thinking about higher-order functions; you place a function value into a data structure so most of the time it can sit there unused, but when it’s called (that is, on demand) it can create more of the data structure. Figure 14.5 illustrates this idea.

Figure 14.5. Elements of a LinkedList exist (are spread out) in memory. But elements of a LazyList are created on demand by a Function—you can see them as spread out in time.

Enough talking—let’s see how this works. What you want to achieve is to generate an infinite list of prime numbers using the algorithm we described earlier.

A basic linked list

Recall that you can define a simple linked-list-style class called MyLinkedList in Java by writing it as follows (here we only consider a minimal MyList interface):

interface MyList<T> {

T head();

MyList<T> tail();

default boolean isEmpty() {

return true;

}

}

class MyLinkedList<T> implements MyList<T> {

private final T head;

private final MyList<T> tail;

public MyLinkedList(T head, MyList<T> tail) {

this.head = head;

this.tail = tail;

}

public T head() {

return head;

}

public MyList<T> tail() {

return tail;

}

public boolean isEmpty() {

return false;

}

}

class Empty<T> implements MyList<T> {

public T head() {

throw new UnsupportedOperationException();

}

public MyList<T> tail() {

throw new UnsupportedOperationException();

}

}

You can now construct a sample MyLinkedList value as follows:

MyList<Integer> l =

new MyLinkedList<>(5, new MyLinkedList<>(10, new Empty<>()));

A basic lazy list

An easy way to adapt this class to the concept of a lazy list is to cause the tail not to be present in memory all at once but to have a Supplier<T> that you saw in chapter 3 (you can also see it as a factory with a function descriptor void -> T), which produces the next node of the list. This leads to the following:

Calling the method get from the Supplier causes the creation of a node of the Lazy-List (as a factory would create a new object).

You can now create the infinite lazy list of numbers starting at n as follows by passing a Supplier as the tail argument of the LazyList constructor, which creates the next element in the series of numbers:

public static LazyList<Integer> from(int n) {

return new LazyList<Integer>(n, () -> from(n+1));

}

If you try the following code for yourself, you’ll see that the following calls will print “2 3 4.” Indeed, the numbers are generated on demand. You can check this by inserting System.out.println appropriately or just by noting that from(2)would run forever if it tried to eagerly calculate all the numbers starting from 2!

LazyList<Integer> numbers = from(2);

int two = numbers.head();

int three = numbers.tail().head();

int four = numbers.tail().tail().head();

System.out.println(two + " " + three + " " + four);

Back to generating primes

See if you can use what you’ve done so far to generate a self-defining lazy list of prime numbers (something you were unable to do with the Streams API). If you were to translate the code that was using the Streams API earlier using our new LazyList, it would look like something like this:

public static MyList<Integer> primes(MyList<Integer> numbers) {

return new LazyList<>(

numbers.head(),

() -> primes(

numbers.tail()

.filter(n -> n % numbers.head() != 0)

)

);

}

Implementing a lazy filter

Unfortunately, a LazyList (more accurately the List interface) doesn’t define a filter method, so the previous code won’t compile! Let’s fix this and declare one:

Your code now compiles and is ready for use! You can calculate the first three prime numbers by chaining calls to tail and head:

LazyList<Integer> numbers = from(2);

int two = primes(numbers).head();

int three = primes(numbers).tail().head();

int five = primes(numbers).tail().tail().head();

System.out.println(two + " " + three + " " + five);

This will print “2 3 5,” which are the first three prime numbers. You can now have some fun; for example, you could print all the prime numbers (the program will run infinitely by writing a printAll method, which iteratively prints the head and tail of a list:

static <T> void printAll(MyList<T> list){

while (!list.isEmpty()){

System.out.println(list.head());

list = list.tail();

}

}

printAll(primes(from(2)));

This being a functional programming chapter, we should explain that you could do this neatly recursively:

static <T> void printAll(MyList<T> list){

if (list.isEmpty())

return;

System.out.println(list.head());

printAll(list.tail());

}

But this program wouldn’t run infinitely; sadly it would eventually fail due to stack overflow because Java doesn’t support tail call elimination, as discussed in chapter 13.

Whew!

So you’ve built a whole lot of technology: lazy lists and functions using them just to define a data structure containing all the primes. Why? What’s the practical use? Well, you’ve seen how to place functions inside data structures (because Java 8 allows you to), and these functions can be used to create parts of the data structure on demand instead of when the structure is created. This might be useful if you’re writing a game-playing program, perhaps for chess; you can have a data structure that notionally represents the whole tree of possible moves (far too big to calculate eagerly) but that can be created on demand. This would be a lazy tree as opposed to a lazy list. We concentrated on lazy lists because they provide a link back to another Java 8 feature, streams, and we could then discuss the pros and cons of streams compared to lazy lists.

There remains the question of performance. It’s easy to assume that doing things lazily will be better than doing things eagerly—surely it’s better to calculate only the values and data structures needed by a program on demand than to create all those values (and perhaps some more) as done under traditional execution. Unfortunately, the real world isn’t so simple. The overhead of doing things lazily (for example, the additional Suppliers between each item in your LazyList) outweighs the notional benefit unless you explore, say, less than 10% of the data structure. Finally, there’s a subtle way in which your LazyList values aren’t truly lazy. If you traverse a LazyList value such as from(2), perhaps up to the 10th item, then it also creates all the nodes twice, thus creating 20 nodes rather than 10. This is hardly lazy. The issue is that the Supplier in tail is repeatedly called on each on-demand exploration of the Lazy-List; you can fix this by arranging that the Supplier in tail is called only on the first on-demand exploration—and its resulting value is cached—in effect solidifying the list at that point. This can be achieved by adding aprivate Optional<LazyList<T>> alreadyComputed field to your definition of LazyList and arranging for the method tail to consult and update it appropriately. The pure functional language Haskell arranges that all its data structures are properly lazy in this latter sense. Read one of the many articles on Haskell if you’re interested.

Our guideline is to remember that lazy data structures can be a useful weapon in your programming armory. Use them when they make an application easier to program. Rewrite them in more traditional style only if they cause unacceptable inefficiency.

Now let’s turn to another feature of almost all functional programming languages but one that’s lacking from Java: pattern matching.

14.4. Pattern matching

There’s one other important aspect to what’s generally regarded as functional programming, and that’s (structural) pattern matching (not to be confused with pattern matching and regex). Recall that chapter 1 ended by observing that mathematics can write definitions such as

f(0) = 1

f(n) = n*f(n-1) otherwise

whereas in Java, you have to write an if-then-else or a switch statement. As data types become more complex, the amount of code (and clutter) needed to process them increases. Using pattern matching can reduce this clutter.

To illustrate, let’s take a tree structure that you’d like to traverse. Consider a simple arithmetic language consisting of numbers and binary operations:

class Expr { ... }

class Number extends Expr { int val; ... }

class BinOp extends Expr { String opname; Expr left, right; ... }

Say you’re asked to write a method to simplify some expressions. For example, 5 + 0 can be simplified to 5. Using our domain, new BinOp("+", new Number(5), new Number(0)) could be simplified to Number(5). You might traverse an Expr structure as follows:

Expr simplifyExpression(Expr expr) {

if (expr instanceof BinOp

&& ((BinOp)expr).opname.equals("+"))

&& ((BinOp)expr).right instanceof Number

&& ... // it's all getting very clumsy

&& ... ) {

return (Binop)expr.left;

}

...

}

You can see that this rapidly gets very ugly!

14.4.1. Visitor design pattern

Another way to unwrap the data type in Java is to make use of the visitor design pattern. In essence, you can create a separate class that encapsulates an algorithm to “visit” a specific data type.

How does it work? The visitor class needs to take as input a specific instance of the data type. It can then access all its members. Here’s an example of how this works. First, you add the method accept to BinOp, which takes SimplifyExprVisitor as argument and passes itself to it (you also add a similar method for Number):

class BinOp extends Expr{

...

public Expr accept(SimplifyExprVisitor v){

return v.visit(this);

}

}

The SimplifyExprVisitor can now access a BinOp object and unwrap it:

public class SimplifyExprVisitor {

...

public Expr visit(BinOp e){

if("+".equals(e.opname) && e.right instanceof Number && ...){

return e.left;

}

return e;

}

}

14.4.2. Pattern matching to the rescue

There’s a simpler solution using a feature called pattern matching. It’s not available in Java, so we’re going to use small examples from the Scala programming language to exemplify pattern matching. It will give you an idea of what could be possible in Java if pattern matching were supported.

Given data type Expr representing arithmetic expressions, in the Scala programming language (we use it because its syntax is the closest to Java), you can write the following code to decompose an expression:

def simplifyExpression(expr: Expr): Expr = expr match {

case BinOp("+", e, Number(0)) => e // Adding zero

case BinOp("*", e, Number(1)) => e // Multiplying by one

case BinOp("/", e, Number(1)) => e // Dividing by one

case _ => expr // Can't simplify expr

}

This use of pattern matching gives an extremely concise and expressive way to manipulate many tree-like data structures. It’s typically useful when building compilers or engines for processing business rules. Note that the Scala syntax

Expression match { case Pattern => Expression ... }

is very similar to the Java syntax

switch (Expression) { case Constant : Statement ... }

with Scala’s wildcard case playing the role of default: in Java. The main visible syntactic difference is that Scala is expression-oriented whereas Java is more statement-oriented, but the main expressiveness difference for the programmer is that Java patterns in case labels are restricted to a couple of primitive types, enumerations, a few special classes that wrap certain primitive types, and Strings. One of the biggest practical advantages of using languages with pattern matching is that you can avoid using big chains of switch or if-then-else statements interleaved with field-selection operations.

Here it’s clear that Scala’s pattern matching wins on ease of expressiveness over Java, and you can only look forward to a future Java allowing more expressive switch statements. We make a concrete proposal for this in chapter 16.

In the meantime, let’s see how Java 8 lambdas can provide an alternative way of achieving pattern-matching-like code in Java. We describe this technique purely so you can see another interesting application of lambdas.

Faking pattern matching in Java

First, let’s consider just how rich Scala’s pattern-matching match expression form is. For example, the case

def simplifyExpression(expr: Expr): Expr = expr match {

case BinOp("+", e, Number(0)) => e

...

means “check that expr is a BinOp, extract its three components (opname, left, right), and then pattern-match these components—the first against the String +, the second against the variable e (which always matches), and then the third against the pattern Number(0).” In other words, the pattern matching in Scala (and many other functional languages) is multilevel. Our simulation of pattern matching using Java 8’s lambdas will give only single-level pattern matching; in the preceding example this would mean cases such as BinOp(op, l, r) or Number(n) but not BinOp("+", e, Number(0)).

First, we make a slightly surprising observation. Now that you have lambdas, you could in principle never use if-then-else in your code. You could replace code such as condition ? e1 : e2 with a method call:

myIf(condition, () -> e1, () -> e2);

Somewhere, perhaps in a library, you’d have a definition (generic in type T):

static <T> T myIf(boolean b, Supplier<T> truecase, Supplier<T> falsecase) {

return b ? truecase.get() : falsecase.get();

}

The type T plays the role of result type of the conditional expression. In principle, similar tricks can be done with if-then-else.

Of course, in normal code this would just make your code more obscure because if-then-else perfectly captures this idiom. But we’ve noted that Java’s switch and if-then-else don’t capture the idiom of pattern matching, and it turns out that lambdas can simply encode (single-level) pattern matching—and rather more neatly than the chains of if-then-else.

Returning to pattern-matching values of class Expr, which has two subclasses, BinOp and Number, you can define a method patternMatchExpr (again generic in T, the result type of the pattern match):

interface TriFunction<S, T, U, R>{

R apply(S s, T t, U u);

}

static <T> T patternMatchExpr(

Expr e,

TriFunction<String, Expr, Expr, T> binopcase,

Function<Integer, T> numcase,

Supplier<T> defaultcase) {

return

(e instanceof BinOp) ?

binopcase.apply(((BinOp)e).opname, ((BinOp)e).left,

((BinOp)e).right) :

(e instanceof Number) ?

numcase.apply(((Number)e).val) :

defaultcase.get();

}

The result is that the method call

patternMatchExpr(e, (op, l, r) -> {return binopcode;},

(n) -> {return numcode;},

() -> {return defaultcode;});

will determine whether e is a BinOp (and if so run binopcode, which has access to the fields of the BinOp via identifiers op, l, r), or whether it is a Number (and if so run numcode, which has access to the value n). The method even makes provision for defaultcode, which would be executed if someone later created a tree node that was neither a BinOp nor a Number.

The following listing shows how to start using patternMatchExpr by simplifying addition and multiplication expressions.

Listing 14.1. Implementing pattern matching to simplify an expression

You can now call the simplify method as follows:

You’ve seen a lot of information so far: higher-order functions, currying, persistent data structures, lazy lists, and pattern matching! We now look at certain subtleties, which we’ve deferred until the end to avoid overcomplicating the text.

14.5. Miscellany

In this section we explore two subtleties of being functional and of having referential transparency; one concerns efficiency and the other concerns returning the same result. These are interesting issues, but we place them here because they’re subtleties concerning side effects rather than conceptually central. We also explore the idea of combinators—methods or functions that take two or more functions and return another function; this idea has inspired many of the additions to the Java 8 API.

14.5.1. Caching or memoization

Suppose you have a side-effect-free method computeNumberOfNodes(Range) that calculates the number of nodes inside a given range in a network with a tree-like topology. Let’s assume the network never changes (that is, the structure is immutable), but calling the methodcomputeNumberOfNodes is expensive to calculate because the structure needs to be traversed recursively. You may want to calculate the results over and over again. If you have referential transparency, there’s a clever way of avoiding this additional overhead. One standard solution to this issue is memoization—adding a cache (for example, a HashMap) to the method as a wrapper—when the wrapper is called. It first consults the cache to see if the (argument, result) pair is already in the cache; if so, it can return the stored result immediately; otherwise, you callcomputeNumberOfNodes, but before returning from the wrapper you store the new (argument, result) pair in the cache. Strictly speaking, this is a nonpurely functional solution because it mutates a data structure shared by multiple callers, but the wrapped version of the code is referentially transparent.

In practice this would work as follows:

final Map<Range,Integer> numberOfNodes = new HashMap<>();

Integer computeNumberOfNodesUsingCache(Range range) {

Integer result = numberOfNodes.get(range);

if (result != null){

return result;

}

result = computeNumberOfNodes(range);

numberOfNodes.put(range, result);

return result;

}

Note

Java 8 enhances the Map interface with a method computeIfAbsent for such use cases. We mention it in appendix B. But for your information you could use the method computeIfAbsent as follows to write clearer code:

Integer computeNumberOfNodesUsingCache(Range range) {

return numberOfNodes.computeIfAbsent(range,

this::computeNumberOfNodes);

}

It’s clear that the method computeNumberOfNodesUsingCache is referentially transparent (assuming the method computeNumberOfNodes is also referentially transparent). But the fact that numberOfNodes is mutable shared state, and that HashMap isn’t synchronized,[2] means that this code isn’t thread-safe. Even using (lock-protected) Hashtable or (concurrent-without-locking) ConcurrentHashMap instead of HashMap may not give the expected performance if there are parallel calls to numberOfNodes from multiple cores, because there’s a race condition between your finding that range isn’t in the map and inserting the (argument, result) pair back into the map. This means multiple processes might compute the same value to add to the map.

2 This is one of those places where bugs breed. It’s so easy to use HashMap here and to forget the fact that the Java manual notes that it’s not thread-safe (or to simply not care because our program is currently single-threaded).

Perhaps the best thing to take away from this struggle is that mixing mutable state with concurrency is trickier than you’d imagine, and functional-style programming avoids it entirely, except for low-level performance hacks such as caching. A second thing is that apart from implementing tricks like caching, if you code in functional style, then you never need to care whether or not another functional-style method you call is synchronized, because you know it has no shared mutable state.

14.5.2. What does “return the same object” mean?

Let’s consider again the binary tree example from section 14.2.3. In figure 14.4, variable t points to an existing Tree, and the figure shows the effect of calling fupdate("Will", 26, t) to produce a new Tree, which we’ll assume is assigned to variable t2. The figure makes it clear thatt, and all the data structures reachable from it, is not mutated. Now suppose you perform a textually identical call in the additional assignment:

t3 = fupdate("Will", 26, t);

Now t3 will point to three more newly created nodes, containing the same data as those in t2. The question is this: “Is fupdate referentially transparent?” Referentially transparent means “equal arguments (the case here) imply equal results.” The problem is that t2 and t3 are different references and therefore (t2 == t3) is false, so it looks as if you’ll have to conclude that fupdate isn’t referentially transparent. But when using persistent data structures that aren’t to be modified, there’s logically no difference between t2 and t3.

We can debate this point at length, but the simplest adage is that functional-style programming generally uses equals to compare structured values rather than == (reference equality) because data isn’t modified, and under this model fupdate is referentially transparent.

14.5.3. Combinators

In functional programming it’s common and natural to write a higher-order function (perhaps written as a method) that accepts, say, two functions and produces another function somehow combining these functions. The term combinator is generally used for this idea. Much of the new Java 8 API is inspired by this idea; for example, thenCombine in the CompletableFuture class. This method takes two CompletableFutures and a BiFunction to produce another CompletableFuture.

Although a detailed discussion of combinators in functional programming is beyond the scope of this book, it’s worth looking at a couple of special cases to give the flavor of how operations that take and return functions are a very common and natural functional programming construct. The following method encodes the idea of function composition:

static <A,B,C> Function<A,C> compose(Function<B,C> g, Function<A,B> f) {

return x -> g.apply(f.apply(x));

}

It takes functions f and g as arguments and returns a function whose effect is to do f first and then g. You can then use this to define an operation, which captures internal iteration as a combinator. Let’s look at the case where you wish to take data and apply function f to it repeatedly, say ntimes, as in a loop. Your operation, let’s call it repeat, takes a function, f, saying what happens in one iteration and returning a function that says what happens in n iterations. A call such as

repeat(3, (Integer x) -> 2*x);

will give x ->(2*(2*(2*x))) or x -> 8*x.

You can test it by writing

System.out.println(repeat(3, (Integer x) -> 2*x).apply(10));

which prints 80.

The method repeat can be coded as follows (note the special case of a zero-trip loop):

Variants of this idea can model richer notions of iteration, including having a functional model of mutable state passed between iterations. But it’s now time to move on; this chapter’s role is to give a summary of functional programming as the basis behind Java 8. There are many excellent books exploring functional programming in greater depth.

14.6. Summary

Following are the key concepts you should take away from this chapter:

· First-class functions are functions that can be passed as arguments, returned as results, and stored in data structures.

· A higher-order function is a function that takes at least one or more functions as input or returns another function. Typical higher-order functions in Java include comparing, andThen, and compose.

· Currying is a technique that lets you modularize functions and reuse code.

· A persistent data structure preserves the previous version of itself when it’s modified. As a result, it can prevent unnecessary defensive copying.

· Streams in Java can’t be self-defined.

· A lazy list is a more expressive version of a Java stream. A lazy list lets you produce elements of the list on demand by using a supplier that can create more of the data structure.

· Pattern matching is a functional feature that lets you unwrap data types. It can be seen as generalizing Java’s switch statement.

· Referential transparency allows computations to be cached.

· Combinators are a functional idea that combines two or more functions or other data structures.