程式扎記: [ FP with Java ] Ch3 - Making Java more functional

Abstracting iteration
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:

view plaincopy to clipboardprint?
for(String email : emailList) {  
  // Do something with email;  
}  

Each time you want to process a list, you use this construct, or other constructs such as while or do..while, which are no different. They’re only syntactic sugar over iteration. Even the preceding for loop is syntactic sugar for the following:

view plaincopy to clipboardprint?
for (int i = 0; i < emailList.size(); i++) {  
  // do something with emailList.get(i)  
}  

The while loop is different because it’s used to iterate as long as a condition is verified. It allows you to exit the loop on a condition that’s applied before the first iteration. The do..while loop does the same, but only after the first iteration. What’s important is what’s done inside the loop, so why should you have to write the loops again and again? Why can’t you just say what you want done and have it be done without messing with the control structures, the conditions, and the indexes?

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:

* Transform each element into something else
* Aggregate elements into a single result
* Remove some elements according to a condition on the elements
* Remove some elements according to an external condition
* Group elements according to certain criteria

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:

view plaincopy to clipboardprint?
List newList = new ArrayList<>();  
for (Integer value : integerList) {  
  newList.add(value * 1.2);  
}  

In this example, an operation is applied to each element of an Integer list (integerList) to increase it by 20%. The result of the operation is a double, so it’s put in a new list that’s created before the start of the loop. Although simple, this program raises some interesting questions. The first point is that you could separate the iteration from the calculation. The following example does this with a method:

view plaincopy to clipboardprint?
Double addTwentyPercent(Integer value) {  
  return value * 1.2;  
}  
  
List newList = new ArrayList<>();  
for (Integer value : integerList) {  
  newList.add(addTwentyPercent(value));  
}  

This allows you to reuse the calculation, but it doesn’t allow you to reuse the loop. To allow this, you can put the loop inside a method and pass it a function to apply the calculation:

view plaincopy to clipboardprint?
Function addTwentyPercent = x -> x * 1.2;  
List map(List list, Function f) {  
  List newList = new ArrayList<>();  
  for (Integer value : list) {  
    newList.add(f.apply(value));  
  }  
  return newList;  
}  

Now you can call the map method with an Integer list and a function from Integer to Double as arguments, and you’ll get a new Double list in return. Plus, you can freely reuse the function and can call the map method with a different function. You can greatly enhance reusability by using generics:

view plaincopy to clipboardprint?
 List map(List list, Function f) {  
  List newList = new ArrayList<>();  
  for (T value : list) {  
    newList.add(f.apply(value));  
  }  
  return newList;  
}  

You can include this method in a library where you’ll define several methods, allowing you to abstract many list-related operations. You’ll call this library Collection-Utilities.

Creating lists
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:

view plaincopy to clipboardprint?
package fp.utils;  
  
import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.Collections;  
import java.util.List;  
  
public class CollectionUtilities {  
    public static  List list() {  
        return Collections.emptyList();  
    }  
  
    public static  List list(T t) {  
        return Collections.singletonList(t);  
    }  
  
    public static  List list(List ts) {  
        return Collections.unmodifiableList(new ArrayList<>(ts));  
    }  
  
    @SafeVarargs  
    public static  List list(T... t) {  
        return Collections.unmodifiableList(Arrays.asList(Arrays.copyOf(t, t.length)));  
    }  
}  

Note that the list(List ts) method makes a copy of the argument list. This defensive copy is needed to ensure that the list won’t be modified afterward by the caller of the list method. Also note that the vararg version may be called with an array as its argument. In such a case, the resulting list is backed by the original array. As a consequence, changing an element of the array would change the corresponding element of the resulting list. This is why you make a copy of the array argument. Also note that the resulting lists aren’t really immutable. They’re immutable views of mutable lists, but this is sufficient because no one will have access to these mutable lists. They will only be mutable in the CollectionUtilities class.

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), which returns an immutable list. Also note that this example throws exceptions when calling head or tail on an empty list. This isn’t functional, because you should always catch exceptions but never throw them in order to be referentially transparent. It is, however, simpler at this stage. In chapter 5, when you look at functional lists, you’ll see that the head and tail methods will be declared protected. This way, they’ll be usable only inside the List class, and no exception will ever leak out of this class.

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:

view plaincopy to clipboardprint?
list.add(element);  

But this operation isn’t usable in functional programs because it mutates its argument and doesn’t return the modified list. If you think it’s functional because it doesn’t mutate its element argument, remember what you learned in chapter 2: this is object notation. The list itself is an implicit argument to the method add, so it’s equivalent to this:

view plaincopy to clipboardprint?
add(list, element);  

Transforming this method into a functional one is simple. You’ll call it append:

view plaincopy to clipboardprint?
public static  List append(List list, T t) {  
  List ts = copy(list);  
  ts.add(t);  
  return Collections.unmodifiableList(ts);  
}  

The append method makes a defensive copy of its first argument (through a call to the previously defined copy method), adds the second argument to it, and then returns the modified list wrapped in an immutable view. You’ll soon have occasion to use this append method in places where it would be impossible to use add.

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:

* If the operation is commutative, both ways of folding are equivalent.
* If the operation isn’t commutative, the two ways of folding give different results.

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:

view plaincopy to clipboardprint?
(((0 + 1) + 2) + 3) + 4 = 10  

You could also proceed from the other side:

view plaincopy to clipboardprint?
1 + (2 + (3 + (4 + 0))) = 10  

The results are identical. You could do the same thing with multiplication, but you’d have to use the identity element 1 as the starting value of the accumulator.

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:

view plaincopy to clipboardprint?
"x" + 'y' = "xy"  

First, let’s fold from the left:

view plaincopy to clipboardprint?
(("" + 'a') + 'b') + 'c' = "abc"  

Let’s now try the same thing from the right:

view plaincopy to clipboardprint?
'a' + ('b' + ('c' + "")) = "abc"  

Folding from the right doesn’t work because the left operand is a character, and the right one is a string. So you have to change the operation to the following:

view plaincopy to clipboardprint?
'x' + "y" = "xy"  

In this case, the character is prepended to the string instead of being appended. The first fold is called a left fold, which means that the accumulator is on the left side of the operation. When the accumulator is on the right side, it’s a right fold.

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:

view plaincopy to clipboardprint?
((0 + 3) + 2) + 1 = 6  

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:

view plaincopy to clipboardprint?
foldLeft(list, acc, x -> y -> operation1)  

is equivalent to

view plaincopy to clipboardprint?
foldRight(reverse(list), acc, y -> x -> operation2)  

If the operation is commutative, operation1 and operation2 are the same. Otherwise, if operation1 is x -> y -> compute(x, y), operation2 is x -> y -> compute(y, x).
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:

view plaincopy to clipboardprint?
public static Integer fold(List is, Integer identity,  
                           Function> f) {  
  int result = identity;  
  for (Integer i : is) {  
    result = f.apply(result).apply(i);  
  }  
  return result;  
}  

After statically importing CollectionUtilities.*, this method can be called as follows:

view plaincopy to clipboardprint?
package test.fp.utils;  
  
import static fp.utils.CollectionUtilities.*;  
import static org.junit.Assert.*;  
import java.util.List;  
import org.junit.Test;  
import fp.utils.Function;  
  
public class TestCollectionUtilities {  
    @Test  
    public void testFoldBySum() {  
        List list = list(1, 2, 3, 4, 5);  
        Function> f = x -> y -> x + y;  
        assertEquals((Integer)15, (Integer)fold(list, 0, f));  
    }  
}  

Here, result is equal to 15, which is the sum of 1, 2, 3, 4, and 5. Replacing + with * and 0 with 1 (the identity element for multiplication) gives the result of 1 x 2 x 3 x 4 x 5 = 120.

Left-folding example
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,

view plaincopy to clipboardprint?
@Test  
public void testLeftFold(){  
    List list = list(1, 2, 3, 4, 5);    
    String identity = "0";  
    Function> f = x -> y -> addSI(x, y);    
    assertEquals("(((((0 + 1) + 2) + 3) + 4) + 5)", foldLeft(list, identity, f));  
}  

where method addSI is defined as follows:

view plaincopy to clipboardprint?
String addSI(String s, Integer i) {  
  return "(" + s + " + " + i + ")";  
}  

Verify that you get the following output:

(((((0 + 1) + 2) + 3) + 4) + 5)

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:

view plaincopy to clipboardprint?
public static  U foldLeft(List ts, U identity, Function> f) {  
    U result = identity;  
    for (T t : ts) {  
        result = f.apply(result).apply(t);  
    }  
    return result;  
}  

Right-folding example
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,

view plaincopy to clipboardprint?
List list = list(1, 2, 3, 4, 5);  
String identity = "0";  
Function> f = x -> y -> addIS(x, y);  

where the method addIS is defined as

view plaincopy to clipboardprint?
private static String addIS(Integer i, String s) {  
  return "(" + i + " + " + s + ")";  
}  

Verify that the output is as follows:

(1 + (2 + (3 + (4 + (5 + 0)))))

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:

view plaincopy to clipboardprint?
public static  U foldRight(List ts, U identity, Function> f) {  
    U result = identity;  
    for (int i = ts.size(); i > 0; i--) {  
        result = f.apply(ts.get(i - 1)).apply(result);  
    }  
    return result;  
}  

Let's write a recursive version of foldRight. Beware that a naive recursive version won’t fully work in Java because it uses the stack to accumulate intermediate calculations. In chapter 4, you’ll learn how to make stack-safe recursion available (Exercise 3.8). You should apply the function to the head of the list and to the result of folding the tail. The naive version will work for at least 5,000 elements, which is enough for an exercise:

view plaincopy to clipboardprint?
public static  U rfoldRight(List ts, U identity,  
           Function> f) {  
    return ts.isEmpty()  
            ? identity  
            : f.apply(head(ts)).apply(foldRight(tail(ts), identity, f));  
}  

Solution 3.8 isn’t tail recursive, so it can’t be optimized to use the heap instead of the stack. We’ll look at a heap-based implementation in chapter 5.

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:

view plaincopy to clipboardprint?
public static  List reverse(List list) {  
  List result = new ArrayList();  
  for(int i = list.size() - 1; i >= 0; i--) {  
    result.add(list.get(i));  
  }  
  return Collections.unmodifiableList(result);  
}  

Let's define the reverse method without using a loop. Instead, use the methods you’ve developed to this point (Exercise 3.9).
Hint.

The methods to use are foldLeft and append. It might be useful to start defining a prepend method that adds an element in front of a list and is defined in terms of append.

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:

view plaincopy to clipboardprint?
public static  List prepend(T t, List list) {  
  return foldLeft(list, list(t), a -> b -> append(a, b));  
}  

Then you can define the reverse method as a left fold, starting with an empty list and using the prepend method as the operation:

view plaincopy to clipboardprint?
public static  List reverse(List list) {  
  return foldLeft(list, list(), x -> y -> prepend(y, x));  
}  

Warning

Don’t use the solution 3.9 implementations of reverse and prepend in production code. Both imply traversing the whole list several times, so they’re slow. In chapter 5, you’ll learn how to create functional immutable lists that perform well on all occasions.

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:

view plaincopy to clipboardprint?
public static  List mapViaFoldLeft(List list,   
                                        Function f) {  
  return foldLeft(list, list(), x -> y -> append(x, f.apply(y)));  
}  

The following implementation uses foldRight and prepend:

view plaincopy to clipboardprint?
public static  List mapViaFoldRight(List list,   
                                             Function f) {  
  return foldRight(list, list(), x -> y -> prepend(f.apply(x), y));  
}  

Part of the beauty of functional programming is in finding every small element that can be abstracted and reused. After you get used to this way of thinking, you’ll start seeing patterns everywhere and you’ll want to abstract them. You could define lots of other useful functions by composing the basic list functions you just wrote. But we’ll delay their study until chapter 5, when you’ll learn to replace the legacy Java lists with pure functional immutable lists that will offer many advantages, including much better performance for most of the functional operations.

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:

view plaincopy to clipboardprint?
Function addTax = x -> x * 1.09;  
Function addShipping = x -> x + 3.50;  
List prices = list(10.10, 23.45, 32.07, 9.23);  
List pricesIncludingTax = map(prices, addTax);  
List pricesIncludingShipping =  
                              map(pricesIncludingTax, addShipping);  
System.out.println(pricesIncludingShipping);  

This code prints the following:

[14.509, 29.0605, 38.456300000000006, 13.5607]

It works but it isn’t efficient, because mapping is applied twice. You could obtain the same result with this:

view plaincopy to clipboardprint?
System.out.println(map(map(prices,addTax),addShipping));  

But this is still mapping twice. A much better solution is to compose the functions instead of composing mappings, or, in other words, to map the composition instead of composing mappings:

view plaincopy to clipboardprint?
System.out.println(map(prices, addShipping.compose(addTax)));  

Or if you prefer a more “natural” writing order:

view plaincopy to clipboardprint?
System.out.println(map(prices, addTax.andThen(addShipping)));  

Applying effects to lists
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:

view plaincopy to clipboardprint?
for (Double price : pricesIncludingShipping) {  
  System.out.printf("%.2f", price);  
  System.out.println();  
}  

But once again, you’re mixing actions that could be abstracted. Iteration can be abstracted exactly as you did for mapping, and the effect applied to each element could be abstracted into something resembling a function, but with a side effect and no return value. This is exactly what the Effect interface you used in the solution to exercise 3.1 is for. So the example could be rewritten as follows:

view plaincopy to clipboardprint?
Effect printWith2decimals = x -> {  
  System.out.printf("%.2f", x);  
  System.out.println();  
};  
  
public static  void forEach(Collection ts, Effect e) {  
  for (T t : ts) e.apply(t);  
}  
  
forEach(pricesIncludingShipping, printWith2decimals);  

This seems to be much more code, but the Effect interface and the forEach method can be written once and reused, so you can test each of them in isolation. Your business code is reduced to only one line.

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:

view plaincopy to clipboardprint?
Function> compose =   
    x -> y -> () -> {  
        x.exec();  
        y.exec();  
    };  

Next you need a neutral element, or identity element, for the composition of Executables. This couldn’t be simpler than an executable doing nothing. Let’s call it ez:

view plaincopy to clipboardprint?
Executable ez = () -> {};  

The name ez stands for executable zero, which means the zero (or identity) element of the operation consisting of composing executables. You can now write your purely functional program as follows:

view plaincopy to clipboardprint?
Executable program = foldLeft(pricesIncludingShipping, ez,  
        e -> d -> compose.apply(e).apply(() -> printWith2decimals.apply(d)));  

It may seem a bit complicated, but it’s simple. It’s a foldLeft of the list pricesIncludingShipping, using ez as the initial value of the accumulator. The only part that’s slightly more complex is the function. If you forget about the curried form and think about it as a function of two arguments, it takes an Executable (e) as its first argument and a Double (d) as its second argument, and it composes the first one with a new Executable consisting of applying the printWith2decimalsmethod to the Double. As you see, it’s just a matter of composing abstractions!

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:

view plaincopy to clipboardprint?
program.exec();  

You get the following result:

14.51
29.06
38.46
13.56

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:

view plaincopy to clipboardprint?
for (int i = 0; i < limit; i++) {  
  some processing...  
}  

This code is a composition of two abstractions: a corecursive list and some processing. The corecursive list is a list of integers from 0 (included) to limit (excluded). As we’ve already noted, functional programming is, among other things, about pushing abstraction to the limit. So let’s abstract the construction of this corecursive list. As I mentioned earlier, corecursive means that each element can be constructed by applying a function to the previous element, starting from the first one. This is what distinguishes corecursive from recursive constructs. (In recursive constructs, each element is a function of the previous one, starting with the last one.) We’ll come back to this difference in chapter 4, but for now, this means that corecursive lists are easy to construct. Just start from the first element (int i = 0) and apply the chosen function (i > i++).

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:

view plaincopy to clipboardprint?
for (int i = 0; i < 5; i++) {  
  System.out.println(i);  
}  

This is nearly equivalent to the following:

view plaincopy to clipboardprint?
list(0, 1, 2, 3, 4).forEach(System.out::println);  

You’ve abstracted the list and the effect. But you can push abstraction further.

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):

view plaincopy to clipboardprint?
List range(int start, int end)  

You could use the for loop implementation to implement the range method. But you’ll use a while loop to prepare for the next exercise:

view plaincopy to clipboardprint?
public static List range(int start, int end) {  
    List result = new ArrayList<>();  
    int temp = start;  
    while (temp < end) {  
        result = CollectionUtilities.append(result, temp);  
        temp = temp + 1;  
    }  
    return result;  
}  

I chose a while loop because it translates more easily into a generic method that can be applied to any type, given a function from this type to itself and a second function (called a predicate) from this type to a Boolean.

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):

view plaincopy to clipboardprint?
List unfold(T seed, Function f, Function p)  

Starting from the range method implementation, all you have to do is replace the specific parts with generic ones:

view plaincopy to clipboardprint?
public static  List unfold(T seed,  
                                 Function f,  
                                 Function p) {  
  List result = new ArrayList<>();  
  T temp = seed;  
  while (p.apply(temp)) {  
    result = append(result, temp);  
    temp = f.apply(temp);  
  }  
  return result;  
}  

Let's implement the range method in terms of unfold (Exercise 3.13). There’s nothing difficult here. You have to provide the seed, which is the start parameter of range; the function f, which is x > x + 1; and the predicate p, which resolves to x > x < end:

view plaincopy to clipboardprint?
public static List range(int start, int end) {  
  return unfold(start, x -> x + 1, x -> x < end);  
}  

Corecursion and recursion have a dual relationship. One is the counterpart of the other, so it’s always possible to change a recursive process into a corecursive one, and vice versa. This is the main subject of the next chapter, where you’ll learn to change a recursive process into a corecursive one. For now, let’s do the inverse process.

Let's write a recursive version of range based on the functional method you’ve defined in previous sections (Exercise 3.14).
Hint

The only method you need is prepend, although you can choose other implementations using different methods.

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:

view plaincopy to clipboardprint?
public static List range(Integer start, Integer end) {  
    return end <= start  
        ? CollectionUtilities.list()  
        : CollectionUtilities.prepend(start, range(start + 1, end));  
  }  

Applying the range method to obtain the same result as the for loop you used earlier as an example is simple:

view plaincopy to clipboardprint?
for (int i = 0; i < 5; i++) {  
  System.out.println(i);  
}  

You can rewrite this as follows:

view plaincopy to clipboardprint?
range(0, 5).forEach(System.out::println);  

More interestingly, if the process applied inside the for loop is functional, the benefit is even more spectacular:

view plaincopy to clipboardprint?
List list = new ArrayList<>();  
for (int i = 0; i < 5; i++) {  
  list.add(i * i);  
}  

This can be replaced with the following (assuming the static import of Collection-Utilities.*):

view plaincopy to clipboardprint?
mapViaFoldLeft(range(0, 5), x -> x * x);  

Of course, in this example, mapViaFoldRight may also be used.

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:

view plaincopy to clipboardprint?
public class Product {  
  
  private final String name;  
  private final double price;  
  private final double weight;  
  
  public Product(String name, double price, double weight) {  
    this.name = name;  
    this.price = price;  
    this.weight = weight;  
  }  
  
  ... (getters)  
}  

Because properties are final, you need a constructor to initialize them and getters to read them, but we didn’t represent the getters. Next, you can use an OrderLine class to represent each line of an order. This class is shown in the following listing.
- Listing 3.10. The component representing one line of an order

view plaincopy to clipboardprint?
public class OrderLine {  
  
  private Product product;  
  private int count;  
  
  public OrderLine(Product product, int count) {  
    super();  
    this.product = product;  
    this.count = count;  
  }  
  
  public Product getProduct() {  
    return product;  
  }  
  
  public void setProduct(Product product) {  
    this.product = product;  
  }  
  
  public int getCount() {  
    return count;  
  }  
  
  public void setCount(int count) {  
    this.count = count;  
  }  
  
  public double getWeight() {  
    return this.product.getWeight() * this.count;  
  }  
  
  public double getAmount() {  
    return this.product.getPrice() * this.count;  
  }  
}  

This looks like a good old Java object, initialized with a Product and an int, and representing one line of an order. It also has methods for computing the total price and the total weight for the line. Continuing with the decision to use standard types, you’ll use List to represent an order. Listing 3.11 shows how you can handle orders. (If you aren’t yet comfortable with functional style, you can compare this code to the imperative equivalent, StoreImperative, which you’ll find on the book’s website at https://github.com/fpinjava/fpinjava.)

Listing 3.11. Handling orders

view plaincopy to clipboardprint?
import java.util.List;  
import static com.fpinjava.common.CollectionUtilities.*;  
  
public class Store {  
  
  public static void main(String[] args) {  
    Product toothPaste = new Product("Tooth paste", 1.5, 0.5);  
    Product toothBrush = new Product("Tooth brush", 3.5, 0.3);  
    List order = list(  
        new OrderLine(toothPaste, 2),  
        new OrderLine(toothBrush, 3));  
    double weight = foldLeft(order, 0.0, x -> y -> x + y.getAmount());  
    double price = foldLeft(order, 0.0, x -> y -> x + y.getWeight());  
    System.out.println(String.format("Total price: %s", price));  
    System.out.println(String.format("Total weight: %s", weight));  
  }  
}  

Running this program displays the following result on the console:

Total price: 1.9
Total weight: 13.5

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:

view plaincopy to clipboardprint?
double weight = foldLeft(order, 0.0, x -> y -> x + y.getAmount());  
double price = foldLeft(order, 0.0, x -> y -> x + y.getWeight());  

You’ve incorrectly mixed prices and weights, which the compiler couldn’t notice because they’re both doubles. By the way, if you’ve learned about modeling, you might recall an old rule: classes shouldn’t have several properties of the same type. Instead, they should have one property with a specific cardinality. Here, this would mean that a Product should have one property of type double, with cardinality 2. This is clearly not the right way to solve the problem, but it’s a good rule to remember. If you find yourself modeling objects with several properties of the same type, you’re probably doing it wrong. What can you do to avoid such problems? First, you have to realize that prices and weights aren’t numbers. They are quantities. Quantities may be numbers, but prices are quantities of money units, and weights are quantities of weight units. You should never be in the situation of adding pounds and dollars.

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:

view plaincopy to clipboardprint?
public class Price {  
  
  public final double value;  
  
  public Price(double value) {  
    this.value = value;  
  }  
}  

You could do the same for the weight:

view plaincopy to clipboardprint?
public class Weight {  
  
  public final double value;  
  
  public Weight(double value) {  
    this.value = value;  
  }  
}  

But this doesn’t solve your problem, because you could write this:

view plaincopy to clipboardprint?
weight += orderLine.getAmount().value;  
price += orderLine.getWeight().value;  

You need to define addition for Price and for Weight, and you could do that with a method:

view plaincopy to clipboardprint?
public class Price {  
  
  ...  
  
  public Price add(Price that) {  
    return new Price(this.value + that.value);  
  }  
...  

You also need multiplication, but multiplication is a bit different. Addition adds things of the same type, whereas multiplication multiplies things of one type by a number. So multiplication isn’t commutative when it isn’t applied just to numbers. Here’s an example of multiplication for Product:

view plaincopy to clipboardprint?
public Price mult(int count) {  
  return new Price(this.value * count);  
}  

In your program, you add prices and weights starting with zero. You can’t do this any longer, so you need a zero for Price and a zero for Weight. This can be a singleton, so you’ll use:

view plaincopy to clipboardprint?
public static final Price ZERO = new Price(0.0);  

in the Price class, and the same thing for the Weight class. The Product class needs to be modified as follows:

view plaincopy to clipboardprint?
public class Product {  
  
  public final String name;  
  public final Price price;  
  public final Weight weight;  
  
  public Product(String name, Price price, Weight weight) {  
    this.name = name;  
    this.price = price;  
    this.weight = weight;  
  }  
}  

OrderLine needs to be modified too:

view plaincopy to clipboardprint?
public Weight getWeight() {  
  return this.product.getWeight().mult(this.count);  
}  
  
public Price getAmount() {  
  return this.product.price.mult(this.count);  
}  

You can now rewrite your program using these types and operations:

view plaincopy to clipboardprint?
import static com.fpinjava.common.CollectionUtilities.*;  
import java.util.List;  
  
public class Store {  
  
  public static void main(String[] args) {  
  
    Product toothPaste = new Product("Tooth paste", new Price(1.5), new Weight(0.5));  
    Product toothBrush = new Product("Tooth brush", new Price(3.5), new Weight(0.3));  
  
    List order = list(  
        new OrderLine(toothPaste, 2),  
        new OrderLine(toothBrush, 3));  
  
    Price price = Price.ZERO;  
    Weight weight = Weight.ZERO;  
    for (OrderLine orderLine : order) {  
      price = price.add(orderLine.getAmount());  
      weight = weight.add(orderLine.getWeight());  
    }  
  }  
}  

You can’t mess with types anymore without the compiler warning you. But you can do far better than this. First, you can add validation to Price and Weight. Neither of them should be constructed with a zero value, except from inside the class itself, for the identity element. You can use a private constructor and a factory method. Here’s how it goes for Price:

view plaincopy to clipboardprint?
private Price(double value) {  
  this.value = value;  
}  
  
public static Price price(double value) {  
  if (value <= 0) {  
    throw new IllegalArgumentException("Price must be greater than 0");  
  } else {  
    return new Price(value);  
  }  
}  

But the main change you can make is to reuse the fold functions you developed in previous section. These functions take a function as their third parameter, so you first have to define a function for adding prices (in the Price class):

view plaincopy to clipboardprint?
public static Function> sum =  
                                           x -> y -> x.add(y.getAmount());  

You also need the same function in the Weight class in order to add weights:

view plaincopy to clipboardprint?
public static Function> sum =  
                                           x -> y -> x.add(y.getWeight());  

Finally, you’ll add a toString method to Price and Weight in order to simplify testing:

view plaincopy to clipboardprint?
public String toString() {  
  return Double.toString(this.value);  
}  

Now you can modify your Store class to use folds:

view plaincopy to clipboardprint?
package fp.compose.ch3;  
  
import java.util.List;  
import static fp.utils.CollectionUtilities.*;  
import static fp.compose.ch3.Price.*;  
import static fp.compose.ch3.Weight.*;  
  
public class Store {  
    public static void main(String[] args) {  
        Product toothPaste = new Product("Tooth paste", price(1.5), weight(0.5));  
        Product toothBrush = new Product("Tooth brush", price(3.5), weight(0.3));  
        List order =  
             list(new OrderLine(toothPaste, 2), new OrderLine(toothBrush, 3));  
        Price price = foldLeft(order, Price.ZERO, Price.sum);  
        Weight weight = foldLeft(order, Weight.ZERO, Weight.sum);  
        System.out.println(String.format("Total price: %s", price));  
        System.out.println(String.format("Total weight: %s", weight));  
    }  
}  

The future of value types in Java
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.

Summary

* Java control structures can be made more functional by ensuring that no state mutation is visible from outside of the structures.
* Control structures can be abstracted from the effects they control.
* The Result interface may be used to represent the result of operations that may fail.
* Control structures like if ... else and switch ... case can be replaced with functions.
* Iteration can be abstracted into functions that may be used as a replacement for loops.
* Lists can be folded in two directions (right and left) to reduce them to a single object (which, by the way, may be a new list).
* Lists can be processed by recursion or corecursion.
* Functions can be mapped to lists to change the value and/or the type of its elements.
* Mapping can be implemented using folds.
* Effects can be bound to lists in order to be applied to each of their elements.
* Recursion and corecursion can also be used to construct lists.
* Recursion is limited in depth by the size of the Java stack.
* Value types can be used to make programs safer by allowing the compiler to detect type problems.

Supplement
* Ch3 - Making Java more functional - Part1
* Ch3 - Making Java more functional - Part2

程式扎記

標籤

2017年11月20日星期一

[ FP with Java ] Ch3 - Making Java more functional - Part2

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

檢舉濫用情形

學習筆記

標籤

2017年11月20日 星期一