Loops are structures that iterate over lists. In Java, loops can also iterate over sets, or might even seem to iterate on nothing, such as indexed loops, but they always iterate on lists. Loops that seem to iterate on sets won’t produce different results if executed twice, because an order is applied to the sets while iterating. And even if the order isn’t the same on each iteration, it won’t change during the course of one iteration. So iterating on a set turns it into a list from the iteration point of view. An indexed loop isn’t any different—it iterates over a list of the evaluated indexes. The loop could exit before evaluating all the arguments because index loops are lazy regarding their indexes. Loops are always lazy regarding their bodies, which means that if a loop exits, the remaining elements won’t be processed. The if..else construct behaves similarly. The condition is always evaluated, so it’s strict regarding the condition, but only one of the if and else parts is evaluated, depending on the condition, so if..else is lazy regarding its body too. Maybe you thought Java was a strict language, but this isn’t true. Java is strict regarding method arguments, but fortunately it’s also sometimes lazy.
Getting back to loops, their main use is to iterate over all elements of a list, as follows:
Take a simple example. Let’s say you have a list of names, and you want to return comma-separated strings. Could you write the program on paper correctly the first time? If you’re a good programmer, I guess you could. But many programmers have to write the code, run it, fix the bugs in the general case, run it again, fix the bugs in the marginal cases, and then run the program again until it’s correct. The problem isn’t difficult, but it’s so boring that you often don’t get it right on the first try. If you always write your programs correctly the first time, congratulations. You’re a good programmer, and the remainder of this section might not be for you. But if you’re an average programmer, keep reading.
Inside a loop, you might want to do several things:
Various operations for which looping is needed can be applied to collections, such as concatenating, zipping, or unzipping. (Zipping means taking elements from two lists and creating a list of tuples. Unzipping is the inverse operation.) All these operations could be abstracted. In chapter 5, you’ll create functional data structures implementing all these abstractions. For now, you’ll develop a library of these abstractions that you can apply to legacy Java collections.
Abstracting an operation on lists with mapping
Mapping, when applied to collections, means applying a transformation to each element of the collection. Here’s how it’s generally done in traditional imperative programming:
Besides iterating, programmers need to repeat other basic operations again and again when working on lists. The most basic operation is creating lists. Java supports many ways to create lists, but they aren’t consistent. Let's write methods that create an empty list, a list with one element, and a list from a collection of elements, as well as a vararg method that creates a list from a list of arguments. All these lists will be immutable (Exercise 3.3). This is straightforward, as you can see in the following code:
Using head and tail operations
Functional operations on lists often access the head (or first element) of the list, as well as the tail (the list with its first element removed). Let's create two methods that return the head and the tail of a list, respectively. The list passed as an argument must not be modified. Because you’ll need to make a copy of the list, also define a copy method. The list returned by tail should be immutable (Exercise 3.4).
The head() method is simple. If the list is empty, you throw an exception. Otherwise, you read the element at index 0 and return it. The copy method is also basic. It’s the same as the list-creation method, taking a list as its argument. The tail method is slightly more complex. It must make a copy of its argument, remove the first element, and return the result:
Note that copy is private. It returns a mutable list. To make a copy from the outside, you can call list(List
Functionally appending to a list
Appending an element to a Java list in an imperative program is a basic operation that’s used again and again:
Reducing and folding lists
List folding transforms a list into a single value by using a specific operation. The resulting value may be of any type—it doesn’t have to be of the same type as the elements of the list. Folding to a result that’s the same type as the list elements is a specific case called reducing. Computing the sum of the elements of a list of integers is a simple case of reducing. You can fold a list in two directions, from left to right or from right to left, depending on the operation used:
Folding needs a starting value, which is the neutral element, or identity element, for the operation. This element is used as the starting value of the accumulator. When the computation is complete, the accumulator contains the result. Reducing, on the other hand, can be done without a starting element, with the condition that the list isn’t empty, because the first (or last) element will be used as the starting element.
Reducing lists of numbers with addition
Suppose you have a list, (1, 2, 3, 4), and you want to compute the sum of the elements. The first way to do it is to put the accumulator on the left side of the operand:
Folding lists of characters into strings
Let’s now do the same thing with a different operation applied to a list of characters, ('a', 'b', 'c'). The operation used here is as follows:
Understanding the relationship between left and right folds
You might say that folding right can be defined in terms of folding left. Let’s rewrite the right-folding operation by using a different form, called corecursion:
In recursion as well as corecursion, evaluation of one step is dependent on the previous step. But a recursive definition starts with the last step and defines its relationship with the preceding one. In order to be able to conclude, it also has to define the base step. Corecursion, on the other hand, starts from the first step and defines its relationship to the next one. There’s no need for a base step, because it’s also the first step. From this, it seems that right-folding a list is equivalent to left-folding the list after having reversed the order of the elements.
But wait. Addition is a commutative operation. If you use a noncommutative operation, you must change the operation as well. If you don’t, you could end up with two different situations, depending on the types. If the operation has operands of different types, if won’t compile. On the other hand, if the operation has operands of the same types but it isn’t commutative, you’ll get a wrong result with no error. So foldLeft and foldRight have the following relationship, where operation1 and operation2 give the same results with the same operands in reverse order:
Think about the reverse function used to reverse a list. Can you see how it could be expressed in terms of leftFold? This is part of the beauty of functional programming. Abstraction can be found everywhere. Now let’s look at how you can apply this to legacy Java lists.
Let's create a method to fold a list of integers that can be used, for example, to sum the elements of a list. This method will take a list of integers, an integer starting value, and a function as its parameters (Exercise 3.5). The starting value is dependent on the operation applied. The value has to be the neutral, or identity, element of the operation. The operation is represented as a curried function, as you learned in the previous chapter:
The operation you just defined was named fold because folding left or right for integer addition or multiplication gives the same result. But if you want to use other functions, or if you want to make the folding method generic, you must distinguish between right and left folds. Let's generalize the fold method to foldLeft so that it can be used to apply a left fold to a list of elements of arbitrary types (Exercise 3.6). To test that the method is correct, apply it to the following parameters,
Note that the addSI method allows you to verify that the arguments are in the correct order. Using the "(" + s + " + " + i + ")" expression directly wouldn’t allow this verification because inverting the argument would change only the meaning of the + signs without changing the result.
The imperative implementation is quite simple:
As you saw previously, folding left is a corecursive operation, so implementing it through an imperative loop is easy. On the other hand, folding right is a recursive operation. To test your tentative implementation, you can use the approach you used for folding left. You’ll test the implementation against the following parameters,
Let's write an imperative version of the foldRight method (Exercise 3.7). A right fold is a recursive operation. To implement it with an imperative loop, you have to process the list in reverse order:
Reversing a list
Reversing a list is sometimes useful, although this operation is generally not optimal in terms of performance. Finding other solutions that don’t require reversing a list is preferable, but not always possible. Defining a reverse method with an imperative implementation is easy by iterating backward over the list. You must be careful, though, not to mess with the indexes:
You can first define a prepend functional method that allows you to add an element in front of a list. This can be done by left-folding the list, using an accumulator containing the element to add instead of the empty list:
Then you can define the reverse method as a left fold, starting with an empty list and using the prepend method as the operation:
From previous section, you defined a method to map a list by applying an operation to each element. This operation, as it was implemented, included a fold. Let's rewrite the map method in terms of foldLeft or foldRight (Exercise 3.10).
To understand the problem, you have to consider that map consists of two operations: applying a function to each element, and then gathering all elements into a new list. This second operation is a fold, where the identity is the empty list (written as list() after a static import CollectionUtilities.*) and the operation is the addition of an element to a list. Here’s an implementation using the append and foldLeft methods:
Composing mappings and mapping compositions
It isn’t unusual to apply several transformations to list elements. Imagine you have a list of prices, and you want to apply a 9% tax to all, and then add a fixed charge of $3.50 for shipping. You can do this by composing two mappings:
It works but it isn’t efficient, because mapping is applied twice. You could obtain the same result with this:
In the previous example, you printed the list in order to verify the result. In a real situation, you’d probably apply more-sophisticated effects to each element of the list. You could, for example, print each price after formatting it to display only two decimal digits. This could be done through iteration:
Approaching functional output
With the forEach method, you can somewhat abstract side effects. You abstracted effect application so it can be isolated, but you could go much further. With the forEach method, one single effect is applied to each element of the list. It would be nice to be able to compose these effects into a single one. Think about it as a fold resulting in a single effect. If you could do this, your program could be a fully functional one with absolutely no side effects. It would produce a new program, with no control structures but a single list of effects that would be applied one after the other. Let’s do this!
To represent the instructions of your program, you’ll use the Executable interface you used in listing 3.5. Then you’ll need a way to compose Executable instances, which can be done by a functional method or by a function. You’re in a functional mood, so let’s use a function:
Note that you haven’t applied any side effects. What you get is a new program (or rather a script) written in a new language. You can execute this program by calling exec() on it:
This gives you a taste of how functional programming can produce output without using side effects. Deciding whether you should use this kind of technique in production is up to you. True functional languages give you no choice, but Java is in no way a functional language, so you have a choice. If you decide to program functionally, you may miss some facilities to help you in this domain, but it’s important to know that everything remains possible.
Building corecursive lists
One thing programmers do again and again is build corecursive lists, and most of these are lists of integers. If you think you, as a Java programmer, don’t do this too often, consider the following example:
You could have constructed the list first and then mapped it to a function corresponding to some processing ... or to a composition of functions, or an effect. Let’s do this with a concrete limit:
Let's write a method to produce a list using a starting value, a limit, and the function x > x + 1. You’ll call this method range, and it will have the following signature (Exercise 3.11):
Let's write a generic range method that will work for any type and any condition. Because the notion of range works mainly for numbers, let’s call this method unfold and give it the following signature (Exercise 3.12):
Let's write a recursive version of range based on the functional method you’ve defined in previous sections (Exercise 3.14).
Defining a recursive implementation is quite simple. You just have to prepend the start parameter to the same method, using the same end parameter and replacing the start parameter with the result of applying the f function to it. It’s much easier to do than to verbalize:
The danger of stack-based recursion
Recursive implementations as developed in the previous examples shouldn’t be used in production, because it’s limited to somewhere between 6,000 and 7,000 steps. If you try to go further, the stack will overflow. Chapter 4 provides more information on this subject.
The danger of strictness
None of these versions (recursive and corecursive) are equivalent to the for loop. This is because, although Java is mostly a strict language (it’s strict regarding method arguments), the for loop, like all Java control structures and some operators, is lazy. This means that in the for loop you used as an example, the order of evaluation will be index, computation, index, computation ..., although using the range method will first compute the complete list before mapping the function. This problem arises because you shouldn’t be using lists for this: lists are strict data structures. But you have to start somewhere. In chapter 9, you’ll learn how to build lazy collections that will solve this problem.
In this section, you’ve learned how to abstract and encapsulate imperative operations that are unavoidable when using imperative data structures such as lists. In chapter 5, you’ll learn how to completely replace these legacy data structures with purely functional ones, which will offer more freedom and better performance. In the meantime, you must look more closely at types.
Using the right types
In the previous examples, you’ve used standard types such as integers, doubles, and strings to represent business entities such as prices and email addresses. Although this is common practice in imperative programming, it causes problems that should be avoided. As I said, you should trust types more than names.
Problems with standard types
Let’s examine a simplified problem and see how solving it by using standard types leads to problems. Imagine you have products with a name, a price, and a weight, and you have to create invoices representing product sales. These invoices have to mention the products, the quantities, the total price, and the total weight. You could represent a Product with the following class:
- Listing 3.10. The component representing one line of an order
Listing 3.11. Handling orders
This is fine, but wrong! The problem is that the compiler didn’t tell you anything about the error. The only way to catch this error is to test the program, but tests can’t prove a program to be correct. They can only prove that you haven’t been able to prove it incorrect through writing another program (which, by the way, could be incorrect too).
In case you didn’t notice it (which is unlikely), the problem is in the following lines:
Defining value types
To avoid this problem, you should use value types. Value types are types representing values. You could define a value type to represent a price:
Value types can be used for all business types to bring type safety to your programs. But value types as I’ve described them aren’t real value types. Real value types are manipulated as if they were objects, but perform as if they were primitives. Other languages have built-in value types, but Java doesn’t, although this might change; a proposal has been made to include value types in a future version of Java. If you’re interested in the subject, you can read the proposal at http://cr.openjdk.java.net/~jrose/values/values-0.html.
* Ch3 - Making Java more functional - Part1
* Ch3 - Making Java more functional - Part2