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.
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
This translates nearly word-for-word into Java code:
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
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:
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:
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
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
Here’s a trace of what’s happening at each step:
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:
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):
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:
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):
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.
* FP with Java - Ch5 - Data handling with lists - Part1
* FP with Java - Ch5 - Data handling with lists - Part2