[ FP with Java ] Ch5 - Data handling with lists - Part2

Using recursion to fold lists with higher-order functions 
In chapter 3, you learned how to fold lists, and folding applies to immutable lists as well. But with mutable lists, you had the choice to implement these operations through iteration or recursively. In chapter 3, you implemented folds iteratively because you were using mutable lists, where adding and removing elements was done in place by nonfunctional methods. The add method returned nothing, and the remove method returned only the removed element, while modifying the list argument. Because immutable lists are recursive data structures, you can very easily use recursion to implement folding operations. 
Let’s consider common folding operations on lists of numbers. 

Exercise 5.7 
Write a functional method to compute the sum of all elements of a list of integers using simple stack-based recursion. The recursive definition of the sum of all elements of a list is 

* For an empty list: 0
* For a non-empty list: head plus the sum of the tail

This translates nearly word-for-word into Java code: 

view plaincopy to clipboardprint?

1. public static Integer sum(List ints) {  
2.     return ints.isEmpty()  
3.             ? 0  
4.             : ints.head() + sum(ints.tail());  
5. }  

Don’t forget that this implementation will overflow the stack for long lists, so don’t use this kind of code in production. 

Exercise 5.8 
Write a functional method to compute the product of all elements of a list of doubles using simple stack-based recursion. The recursive definition of the product of all elements of a non-empty list is 

* For an empty list: 1.0
* For a non-empty list: head * product of tail

Consider what will happen when you’ve applied the recursive formula to all elements. You’ll end up with a result that will have to be multiplied by the product of all elements of an empty list. Because you want to eventually get this result, you have no choice but to say that the product of all elements of an empty list is 1. This is the same situation as with the sum example, when you use 0 as the sum of all elements of an empty list. The identity element, or neutral element, for the sum operation is 0, and the identity or neutral element for the product is 1. So your product method could be written as follows: 

view plaincopy to clipboardprint?

1. public static Double product(List ds) {  
2.     return ds.isEmpty()   
3.             ? 1.0   
4.             : ds.head() * product(ds.tail());  
5. }  

Note that the product operation is different from the sum operation in one important way. It has an absorbing element, which is an element that satisfies the following condition: 

a × absorbing element = absorbing element × a = absorbing element

The absorbing element for multiplication is 0. By analogy, the absorbing element of any operation (if it exists) is also called the zero element. The existence of a zero element allows you to escape the computation, also called short circuiting: 

view plaincopy to clipboardprint?

1. public static Double product(List ds) {  
2.     return ds.isEmpty()   
3.             ? 1.0   
4.             : ds.head() == 0.0   
5.                 ? 0.0   
6.                 : ds.head() * product(ds.tail());  
7. }  

But forget about this optimized version and look at the definitions for sum and product. Can you detect a pattern that could be abstracted? Let’s look at them side by side (after having changed the parameter name): 

view plaincopy to clipboardprint?

1. public static Integer sum(List list) {  
2.   return list.isEmpty()  
3.       ? 0  
4.       : list.head() + sum(list.tail());  
5. }  
6.   
7. public static Double product(List list) {  
8.   return list.isEmpty()  
9.       ? 1  
10.       : list.head() * product(list .tail());  
11. }  

Now let’s remove the differences and replace them with a common notation: 

view plaincopy to clipboardprint?

1. public static Type operation(List list) {  
2.   return list.isEmpty()  
3.       ? identity  
4.       : list.head() operator operation(list .tail());  
5. }  
6.   
7. public static Type operation(List list) {  
8.   return list.isEmpty()  
9.       ? identity  
10.       : list.head() operator operation(list .tail());  
11. }  

The two operations are nearly the same. If you can find a way to abstract the common parts, you’ll just have to provide the variable information (Type, operation, identity, and operator) to implement both operations without repeating yourself. This common operation is what we call a fold, which you studied in chapter 3. In that chapter, you learned that there are two kinds of folds—right fold and left fold—as well as a relation between these two operations. 

Listing 5.2 shows the common parts of the sum and product operations abstracted into a method called foldRight, taking as its parameters the list to fold, an identity element, and a higher-order function representing the operation used to fold the list. The identity element is obviously the identity for the given operation, and the function is in curried form. (See chapter 2 if you don’t remember what this means.) This function represents the operator portion of your code. 
Listing 5.2. Implementing foldRight and using it for sum and product 

view plaincopy to clipboardprint?

1. public static  B foldRight(List list, B n, Function> f)  
2. {  
3.     return list.isEmpty()  
4.             ? n  
5.             : f.apply(list.head()).apply(foldRight(list.tail(), n, f));  
6. }  
7.   
8. public static Integer sum(List list)  
9. {  
10.     return foldRight(list, 0, x -> y -> x + y);  
11. }  
12.   
13. public static Double product(List list)  
14. {  
15.     return foldRight(list, 1.0, x-> y-> x * y);  
16. }  

Note that the Type variable part has been replaced with two types here, A and B. This is because the result of folding isn’t always of the same type as the elements of the list. Here, it’s abstracted a bit more than is needed for the sum and product operations, but this will be useful soon. The operation variable part is, of course, the names of the two methods. 

The fold operation isn’t specific to arithmetic computations. You can use a fold to transform a list of characters into a string. In such a case, A and B are two different types: Char and String. But you can also use a fold to transform a list of strings into a single string. Can you see now how you could implement concat? By the way, foldRight is very similar to the singly linked list itself. If you think of the list 1, 2, 3 as 

view plaincopy to clipboardprint?

1. Cons(1, Cons(2, Cons(3, Nil)  

you can see immediately that it’s very similar to a right fold: 

view plaincopy to clipboardprint?

1. f(1, f(2, f(3, identity)  

But perhaps you’ve already realized that Nil is the identity for adding elements to lists. This make sense: if you want to transform a list of characters into a string, you have to start with an empty list. (By the way, Nil is also the identity for list concatenation, although you could do without it, provided the list of lists to be concatenated isn’t empty. In such a case, it’s called a reduce rather than a fold. But this is possible only because the result is of the same type as the elements.) This can be put in practice by passing Nil and cons to foldRight as the identity and the function that are used to fold: 

view plaincopy to clipboardprint?

1. List.foldRight(list(1, 2, 3), list(), x -> y -> y.cons(x))  

This simply produces a new list with the same elements in the same order, as you can see by running the following code: 

view plaincopy to clipboardprint?

1. System.out.println(List.foldRight(list(1, 2, 3), list(),  
2.                                                x -> y -> y.cons(x)));  

This code produces the following output: 

[1, 2, 3, NIL]

Here’s a trace of what’s happening at each step: 

foldRight(list(1, 2, 3), list(), x -> y -> y.cons(x));
foldRight(list(1, 2), list(3), x -> y -> y.cons(x));
foldRight(list(1), list(2, 3), x -> y -> y.cons(x));
foldRight(list(), list(1, 2, 3), x -> y -> y.cons(x));

Now let's write a method to compute the length of a list. This method will use the foldRight method (Exercise 5.9). The Nil implementation is obvious and returns 0. The Cons implementation may be written as: 

view plaincopy to clipboardprint?

1. public int length() {  
2.   return foldRight(this, 0, x -> y -> y + 1);  
3. }  

Note that this implementation, beside being stack-based recursive, has very poor performance. Even if transformed to heap-based, it’s still O(n), meaning the time needed to return the length is proportional to the length of the list. In following chapters, you’ll see how to get the length of a linked list in constant time. 

The foldRight method uses recursion, but it’s not tail recursive, so it will rapidly overflow the stack. How rapidly depends on several factors, the most important of which is the size of the stack. In Java, the size of the stack is configurable through the -Xss command-line parameter, but the major drawback is that the same size is used for all threads. Using a bigger stack would be a waste of memory for most threads. 

Instead of using foldRight, create a foldLeft method that’s tail recursive and can be made stack-safe. Here’s its signature (Exercise 5.10): 

view plaincopy to clipboardprint?

1. public abstract  B foldLeft(B identity, Function> f);  

The Nil implementation will obviously return identity. For the Cons implementation, start with defining a front-end method foldLeft calling a stack-based tail recursive helper method foldLeft_ with an accumulator acc initialized to identity and a reference to this: 

view plaincopy to clipboardprint?

1. public  B foldLeft(B identity, Function> f) {  
2.   return foldLeft_(identity, this, f);  
3. }  
4.   
5. private  B foldLeft_(B acc, List list,  
6.                                     Function> f) {  
7.   return list.isEmpty()  
8.       ? acc  
9.       : foldLeft_(f.apply(acc).apply(list.head()), list.tail(), f);  
10. }  

Then make the following changes so you can use the TailCall interface you defined in chapter 4 (the ret and sus methods are imported statically): 

view plaincopy to clipboardprint?

1. public  B foldLeft(B identity, Function> f) {  
2.     return foldLeft_(identity, this, f).eval();  
3. }  
4.   
5. private  TailCall foldLeft_(B acc, List list, Function> f) {  
6.     return list.isEmpty()  
7.               ? ret(acc)  
8.               : sus(() -> foldLeft_(f.apply(acc).apply(list.head()),  
9.                                                        list.tail(), f));  
10. }  

Use your new foldLeft method to create new stack-safe versions of sum, product, and length (Exercise 5.11). 

view plaincopy to clipboardprint?

1. public static Integer sumViaFoldLeft(List list) {  
2.     return list.foldLeft(0, x -> y -> x + y);  
3. }  
4.   
5. public static Double productViaFoldLeft(List list) {  
6.     return list.foldLeft(1.0, x -> y -> x * y);  
7. }  
8.   
9. public static  Integer lengthViaFoldLeft(List list) {  
10.     return list.foldLeft(0, x -> ignore -> x + 1);  
11. }  

Note that once again, the second parameter of method length (representing each element of the list on each recursive call of the method) is ignored. This method is as inefficient as the previous one and shouldn’t be used in production code. 

Let's use foldLeft to write a static functional method for reversing a list (Exercise 5.12). Reversing a list via a left fold is very simple, starting from an empty list as the accumulator and cons-ing each element of the first list to this accumulator: 

view plaincopy to clipboardprint?

1. public static  List reverseViaFoldLeft(List list) {  
2.   return list.foldLeft(list(), x -> x::cons);  
3. }  

This example uses a method reference instead of a lambda, as explained in chapter 2. If you prefer to use a lambda, it’s equivalent to the following: 

view plaincopy to clipboardprint?

1. public static  List reverseViaFoldLeft(List list) {  
2.   return list.foldLeft(list(), x -> a -> x.cons(a));  
3. }  

Let's write foldRight in terms of foldLeft (Exercise 5.13). This implementation can be useful for getting a stack-safe version of foldRight: 

view plaincopy to clipboardprint?

1. public static  B foldRightViaFoldLeft(List list,  
2.                               B identity, Function> f) {  
3.   return list.reverse().foldLeft(identity, x -> y -> f.apply(y).apply(x));  
4. }  

Note that you can also define foldLeft in terms of foldRight, although this is much less useful: 

view plaincopy to clipboardprint?

1. public static  B foldLeftViaFoldRight(List list,  
2.                               B identity, Function> f) {  
3.   return List.foldRight(list.reverse(),identity, x -> y ->  
4.                                                     f.apply(y).apply(x));  
5. }  

Again, note that the foldLeft method you use is an instance method of List. In contrast, foldRight is a static method. (We’ll define an instance foldRight method soon.) 

Heap-based recursive version of foldRight 
As I said, the recursive foldRight implementation is only for demonstrating these concepts, because it’s stack-based and thus shouldn’t be used in production code. Also note that this is a static implementation. An instance implementation would be much easier to use, allowing you to chain method calls with the object notation. 

Let's use what you learned in chapter 4 to write a heap-based recursive instance version of the foldRight method (Exercise 5.14). The method can be defined in the parent List class. Write a tail recursive stack-based version of the foldRightmethod (using a helper method). Then change the helper method to a heap-based recursive implementation using the TailCall interface you developed in chapter 4. 

First, let’s write the stack-based tail recursive helper method. All you have to do is write a helper method that takes an accumulator as an additional parameter. The accumulator has the same type as the function return type, and its initial value is equal to the identity element (which, by the way, is used twice): 

view plaincopy to clipboardprint?

1. public  B foldRight(B identity, Function> f) {  
2.     return foldRight_(identity, this.reverse(), identity, f);  
3. }  
4.   
5. public  B foldRight_(B acc, List ts, B identity, Function> f) {  
6.     return ts.isEmpty()  
7.             ? acc  
8.             : foldRight_(f.apply(ts.head()).apply(acc), ts.tail(), identity, f);  
9. }  

Now change both methods to use TailCall heap-based recursion: 

view plaincopy to clipboardprint?

1. public  B foldRight(B identity, Function> f) {  
2.     return foldRight_(identity, this.reverse(), identity, f).eval();  
3. }  
4.   
5. private  TailCall foldRight_(B acc, List ts, B identity, Function> f) {  
6.     return ts.isEmpty()   
7.             ? ret(acc)   
8.             : sus(() -> foldRight_(f.apply(ts.head()).apply(acc), ts.tail(), identity, f));  
9. }  

Now we can implement concat in terms of either foldLeft or foldRight (Exercise 5.15). The concat method can be implemented easily using a right fold: 

view plaincopy to clipboardprint?

1. public static  List concat(List list1, List list2) {  
2.     return foldRight(list1, list2, x -> y -> new Cons<>(x, y));  
3. }  

Another solution is to use a left fold. In this case, the implementation will be the same as reverseViaFoldLeft applied to the reversed first list, using the second list as the accumulator: 

view plaincopy to clipboardprint?

1. public static  List concat(List list1, List list2) {  
2.   return list1.reverse().foldLeft(list2, x -> x::cons);  
3. }  

Now let's write a method for flattening a list of lists into a list containing all elements of each contained list (Exercise 5.16). This operation consists of a series of concatenations. In other words, it’s similar to adding all elements of a list of integers, although integers are replaced with lists, and addition is replaced with concatenation. Other than this, it’s exactly the same as the sum method. 

view plaincopy to clipboardprint?

1. public static  List flatten(List> list) {  
2.   return foldRight(list, List.list(), x -> y -> concat(x,y));  
3. }  

Mapping and filtering lists 
You can define many useful abstractions for working on lists. One abstraction consists of changing all the elements of a list by applying a common function to them. 

Write a functional method that takes a list of integers and multiplies each of them by 3 (Exercise 5.17). Try using the methods you’ve defined up to now. Don’t use recursion explicitly. The goal is to abstract stack-safe recursion once and for all so you can put it to work without having to reimplement it each time. 

view plaincopy to clipboardprint?

1. public static List triple(List list) {  
2.       return List.foldRight(list, List.list(), h -> t ->  
3.                                                         t.cons(h * 3));  
4. }  

Write a function that turns each value in a List into a String (Exercise 5.18). This operation can be seen as concatenating an empty list of the expected type (List) with the original list, with each element being transformed before being cons-ed to the accumulator. As a result, the implementation is very similar to what you did in the concat method: 

view plaincopy to clipboardprint?

1. public static List double2String(List list) {  
2.     return List.foldRight(list, List.list(), h -> t -> t.cons(Double.toString(h)));  
3. }  

Finally, let's Write a general functional method map that allows you to modify each element of a list by applying a specified function to it. This time, make it an instance method of List. Add the following declaration in the Listclass (Exercise 5.19): 

view plaincopy to clipboardprint?

1. public abstract  List map(Function f);  

Use the stack-safe instance version of the foldRight method. The map method may be implemented in the parent List class: 

view plaincopy to clipboardprint?

1. public  List map(Function f) {  
2.   return foldRight(list(), h -> t -> new Cons<>(f.apply(h),t));  
3. }  

Then let's write a filter method that removes from a list the elements that don’t satisfy a given predicate. Once again, implement this as an instance method with the following signature (Exercise 5.20): 

view plaincopy to clipboardprint?

1. public List filter(Function f)  

Here’s an implementation in the parent List class, using foldRight. Don’t forget to use the stack-safe version of this method 

view plaincopy to clipboardprint?

1. public List filter(Function f){  
2.      return foldRight(list(), h -> t -> f.apply(h) ? new Cons<>(h,t) : t);  
3. }  

Write a flatMap method that applies to each element of List a function from A to List, and returns a List. Its signature will be (Exercise 5.21): 

view plaincopy to clipboardprint?

1. public  List flatMap(Function> f);  

For example, List.list(1,2,3).flatMap(i -> List.list(i, -i)) should return list(1,-1,2,-2,3,-3). Once again, it can be implemented in the parent List class, using foldRight: 

view plaincopy to clipboardprint?

1. public  List flatMap(Function> f) {  
2.     return foldRight(list(), h -> t -> concat(f.apply(h), t));  
3. }  

Create a new version of filter based on flatMap (Exercise 5.22). Here’s a static implementation: 

view plaincopy to clipboardprint?

1. public static  List filterViaFlatMap(List list, Function p) {  
2.     return list.flatMap(a -> p.apply(a) ? List.list(a) : List.list());  
3. }  

Notice that there’s a strong relation between map, flatten, and flatMap. If you map a function returning a list to a list, you get a list of lists. You can then apply flatten to get a single list containing all the elements of the enclosed lists. You’d get exactly the same result by directly applying flatMap. One consequence of this relation is that you can redefine flatten in terms of flatMap: 

view plaincopy to clipboardprint?

1. public static  List flatten(List> list) {  
2.   return list.flatMap(x -> x);  
3. }  

This isn’t surprising, because the call to concat has been abstracted into flatMap. 

Supplement 
* FP with Java - Ch5 - Data handling with lists - Part1 
* FP with Java - Ch5 - Data handling with lists - Part2