程式扎記: [ FP with Java ] Ch2 - Using functions in Java : Part2

Source From Here
Advanced function features
You’ve seen how to create apply and compose functions. You’ve also learned that functions can be represented by methods or by objects. But you haven’t answered a fundamental question: why do you need function objects? Couldn’t you simply use methods? Before answering this question, you have to consider the problem of the functional representation of multiargument methods.

What about functions of several arguments?
In section 2.1.1, I said that there are no functions of several arguments. There are only functions of one tuple of arguments. The cardinality of a tuple may be whatever you need, and there are specific names for tuples with a few arguments: pair, triplet, quartet, and so on. Other possible names exist, and some prefer to call them tuple2, tuple3, tuple4, and so forth. But I also said that arguments can be applied one by one, each application of one argument returning a new function, except for the last one. Let’s try to define a function for adding two integers. You’ll apply a function to the first argument, and this will return a function. The type will be as follows:

view plaincopy to clipboardprint?
Function>  

This may seem a bit complicated, particularly if you think that it could have been written like this:

view plaincopy to clipboardprint?
Integer -> Integer -> Integer  

Note that because of associativity, this is equivalent to:

view plaincopy to clipboardprint?
Integer -> (Integer -> Integer)  

where the left Integer is the type of the argument, and the element between parentheses is the return type, which obviously is a function type. If you remove the word Function from Function>, you get this:

view plaincopy to clipboardprint?
>  

This is exactly the same. The Java way of writing function types is much more verbose but not more complex. Below is sample code for such ideas:

view plaincopy to clipboardprint?
import java.util.function.Function;  
  
public interface BinaryOperator extends Function>{}  
  
BinaryOperator add = x -> y -> x + y;  
BinaryOperator mult = x -> y -> x * y;  
  
System.out.printf("%d\n", add.apply(1).apply(2));  // 1 + 2 = 3  
System.out.printf("%d\n", mult.apply(2).apply(3)); // 2 * 3 = 6  

The number of arguments isn’t limited. You can define functions with as many arguments as you need. As I said in the first part of this chapter, functions such as the add function or the mult function you just defined are said to be the curried form of the equivalent functions of tuples.

Applying curried functions
You’ve seen how to write curried function types and how to implement them. But how do you apply them? Well, just like any function. You apply the function to the first argument, and then apply the result to the next argument, and so on until the last one. For example, you can apply the add function to 3 and 5:

view plaincopy to clipboardprint?
System.out.println(add.apply(3).apply(5));   // 3 + 5 = 8  

Here, you’re again missing some syntactic sugar. It would be great if you could apply a function just by writing its name followed by its argument. It would allow coding, as in Scala:

view plaincopy to clipboardprint?
add(3)(5)  

Or even better, as in Haskell:

view plaincopy to clipboardprint?
add 3 5  

Perhaps in a future version of Java?

Higher-order functions
In section 2.14, you wrote a method to compose functions. That method was a functional one, taking as its argument a tuple of two functions and returning a function. But instead of using a method, you could use a function! This special kind of function, taking functions as its arguments and returning functions, is called a higher-order function (HOF).

Let's write a function to compose the two functions square and triple (exercise 2.4). The first thing to do is to write the type. This function will work on two arguments, so it’ll be a curried function. The two arguments and the return type will be functions from Integer to Integer:

view plaincopy to clipboardprint?
Function  

You can call this T. You want to create a function taking an argument of type T (the first argument) and returning a function from T (the second argument) to T (the return value). The type of the function is then as follows:

view plaincopy to clipboardprint?
Function>  

If you replace T with its value, you obtain the real type:

view plaincopy to clipboardprint?
Function,  
         Function,  
                  Function>>  

The main problem here is the line length! Let’s now add the implementation, which is much easier than the type:

view plaincopy to clipboardprint?
x -> y -> z -> x.apply(y.apply(z));  

The complete code is shown here:

view plaincopy to clipboardprint?
Function,  
         Function,  
                  Function>> compose =  
                                      x -> y -> z -> x.apply(y.apply(z));  

You can write this code on a single line! Let’s test this code with the square and triple functions:

view plaincopy to clipboardprint?
Function triple = x -> x * 3;    
Function square = x -> x * x;   
Function f = compose.apply(square).apply(triple);  

In this code, you start by applying the first argument, which gives you a new function to apply to the second argument. The result is a function, which is the composition of the two function arguments. Applying this new function to (for example) 2 gives you the result of first applying triple to 2 and then applying square to the result (which corresponds to the definition of function composition):

view plaincopy to clipboardprint?
System.out.println(f.apply(2));  // (2*3)^2 = 36  

Pay attention to the order of the parameters: triple is applied first, and then square is applied to the result returned by triple.

Polymorphic higher-order functions
Our compose function is fine, but it can compose only functions from Integer to Integer. It would be much more interesting if you could compose any types of functions, such as String to Double or Boolean to Long. But that’s only the beginning. A fully polymorphic compose function would allow you to compose Function>, such as the add and mult you wrote in exercise 2.3. It should also allow you to compose functions of different types, provided that the return type of one is the same as the argument type of the other.

Now let's write a polymorphic version of the compose function (Exercise 2.5). The first step seems to be to “generify” the example of exercise 2.4:

view plaincopy to clipboardprint?
 Function,  
                   Function,  
                            Function>> higherCompose =  
                                      f -> g -> x -> f.apply(g.apply(x));  

But this isn’t possible, because Java doesn’t allow standalone generic properties. To be generic, a property must be created in a scope defining the type parameters. Only classes, interfaces, and methods can define type parameters, so you have to define your property inside one of these elements. The most practical is a static method.

Variance
Variance describes how parameterized types behave in relation to subtyping. Covariance means that Matcher<Red> is considered a subtype of Matcher<Color> if Red is a subtype of Color. In such case, Matcher<T> is said to be covariant on T. If, on the contrary, Matcher<Color> is considered a subtype of Matcher<Red>, then Matcher<T> is said to be contravariant on T. In Java, although an Integer is a subtype of Object, a List<Integer> is not a subtype of List<Object>. You may find this strange, but a List<Integer> is an Object, but it is not a List<Object>. And a Function is not a Function<Object, Object>. (This is much less surprising!)

In Java, all parameterized types are said to be invariant on their parameter.

view plaincopy to clipboardprint?
static  Function, Function, Function>> higherCompose() {  
    return f -> g -> x -> f.apply(g.apply(x));  
}  

Note that the method called HigherCompose() takes no parameter and always returns the same value. It’s a constant. The fact that it’s defined as a method is irrelevant from this point of view. It isn’t a method for composing functions. It’s only a method returning a function to compose functions. Beware of the order of the type parameters and how they correspond to the implementation lambda parameters, as shown in figure 2.3.

Figure 2.3. Pay attention to the order of type parameters.

You could give the lambda parameters more-meaningful names, such as uvFunction and tuFunction, or more simply uv and tu, but you should refrain from doing so. Names aren’t reliable. They show the intention (of the programmer) and nothing else. You could easily switch the names without noticing any change:

view plaincopy to clipboardprint?
static  Function, Function, Function>> higherCompose() {  
    return tuFunc -> uvFunc -> t -> tuFunc.apply(uvFunc.apply(t));  
}  

In this example, tuFunc is a function from U to V, and uvFunc is a function from T to U. If you need more information about the types, you can simply write them in front of each lambda parameter, enclosing the type and the parameter between parentheses:

view plaincopy to clipboardprint?
static <T, U, V&tl; Function<Function<U, V>,  
                          Function<Function<T, U>,  
                                   Function<T, V>>> higherCompose() {  
  return (Function f) -> (Function g) -> (T x)  
                                                   -> f.apply(g.apply(x));  
} 
 

Now you might want to use this function in the following way:

view plaincopy to clipboardprint?
Function triple = x -> x * 3;    
Function square = x -> x * x;   
Integer x = higherCompose().apply(square).apply(triple).apply(2);  

But this doesn’t compile, producing the following error:

Error:(39, 48) java: incompatible types: ...FunctionInteger,java.lang.Integer> cannot be converted to ....FunctionObject,java.lang.Object>

The compiler is saying that it couldn’t infer the real types for the T, U, and V type parameters, so it used Object for all three. But the square and triple functions have types Function<Integer, Integer>. If you think that this is enough information to infer the T, U, and V types, then you’re smarter than Java! Java tried to go the other way around, casting a Function<Integer, Integer> into a Function<Object, Object>. And although an Integer is an Object, a Function<Integer, Integer> isn’t a Function <Object, Object&tl;. These two types aren’t related because types are invariant in Java. For the cast to work, the types should have been covariant, but Java doesn’t know about variance. The solution is to revert to the original problem and help the compiler by telling it what real types T, U, and V are. This can be done by inserting the type information between the dot and the method name:

view plaincopy to clipboardprint?
Integer x = Function.higherCompose().apply(....)  

This is somewhat impractical, but that isn’t the main problem. More often, you’ll group functions such as higherCompose in a library class, and you may wish to use static import to simplify the code:

view plaincopy to clipboardprint?
import static com.fpinjava. ... .Function.*;  
...  
Integer x = higherCompose().apply(...;  

Unfortunately, this won’t compile!

Let's write the higherAndThen function that composes the functions the other way around, which means that higherCompose(f, g) is equivalent to higherAndThen(g, f) (Exercise 2.6).

view plaincopy to clipboardprint?
public static  Function, Function, Function>> higherAndThen() {  
    return f -> g -> x -> g.apply(f.apply(x));  
}  

Testing function parameters
If you have any doubt concerning the order of the parameters, you should test these higher-order functions with functions of different types. Testing with functions from Integer to Integer will be ambiguous, because you’ll be able to compose the functions in both orders, so an error will be difficult to detect. Here’s a test using functions of different types:

view plaincopy to clipboardprint?
package fp.compose;  
  
import java.util.function.Function;  
import static org.junit.Assert.*;  
import org.junit.Test;  
  
public class Ex2_6 {  
    public static  Function, Function, Function>> higherAndThen() {  
        return f -> g -> x -> g.apply(f.apply(x));  
    }  
      
    static  Function, Function, Function>> higherCompose() {  
        return tvFunc -> vuFunc -> t -> tvFunc.apply(vuFunc.apply(t));  
    }  
  
    @Test  
    public void testHigherCompose() {  
  
          Function f = a -> (int) (a * 3);  
          Function g = a -> a + 2.0;  
  
          assertEquals(Integer.valueOf(9), f.apply((g.apply(1L))));  
          assertEquals(Integer.valueOf(9),  
            Ex2_6.higherCompose().apply(f).apply(g).apply(1L));  
        }  
}  

Note that Java is unable to infer the types, so you have to provide them when calling the higherCompose function.

Using anonymous functions
Until now, you’ve been using named functions. These functions were implemented as anonymous classes, but the instances you created were named and had explicit types. Often you won’t define names for functions, and you’ll use them as anonymous instances. Let’s look at an example. Instead of writing:

view plaincopy to clipboardprint?
Function f = x -> Math.PI / 2 - x;    
Function sin = Math::sin;    
Double cos = f.compose(sin).apply(2.0);  

you can use anonymous functions:

view plaincopy to clipboardprint?
Double cos = JFun.Compose(x -> Math.PI / 2 - x, Math::sin).apply(2.0);  

Here, you use the Compose method statically defined in the JFun class.

view plaincopy to clipboardprint?
package fp.compose;  
  
import java.util.function.Function;  
  
public class JFun {  
    public static  Function Compose(Function f1, Function f2) {  
        return arg -> f1.apply(f2.apply(arg));  
    }  
      
    public static  Function, Function, Function>> HigherCompose() {  
        return tvFunc -> vuFunc -> t -> tvFunc.apply(vuFunc.apply(t));  
    }  
}  

But this also applies to higher-order functions:

view plaincopy to clipboardprint?
Double cos1 = JFun.Compose(x -> Math.PI / 2 - x, Math::sin).apply(2.0);  
Double cos2 = JFun.HigherCompose().apply(x -> Math.PI / 2 - x).apply(Math::sin).apply(2.0);  
assert(cos1==cos2);  

Method references
Beside lambdas, Java 8 also brings method references, which is a syntax that can be used to replace a lambda when the lambda implementation consists of a method call with a single argument. For example,

view plaincopy to clipboardprint?
Function sin = Math::sin;  

is equivalent to this:

view plaincopy to clipboardprint?
Function sin = x -> Math.sin(x);  

Here, sin is a static method in the Math class. If it was an instance method in the current class, you could have written the following:

view plaincopy to clipboardprint?
Function sin = this.sin(x);  

This kind of code will be often used in this book to make a function out of a method.

When to use anonymous and when to use named functions
Apart from special cases when anonymous functions can’t be used, it’s up to you to choose between anonymous and named functions. As a general rule, functions that are used only once are defined as anonymous instances. But used once means that you write the function once. It doesn’t mean that it’s instantiated only once. In the following example, you define a method to compute the cosine of a Double value. The method implementation uses two anonymous functions because you’re using a lambda expression and a method reference:

view plaincopy to clipboardprint?
Double cos(Double arg) {  
    return JFun.Compose(z -> Math.PI / 2 - z, Math::sin).apply(arg);  
}  

Don’t worry about the creation of anonymous instances. Java won’t always create new objects each time the function is called. And anyway, instantiating such objects is cheap. Instead, you should decide whether to use anonymous or named functions by considering only the clarity and maintainability of your code. If you’re concerned with performance and reusability, you should be using method references as often as possible.

Type inference
Type inference can also be an issue with anonymous functions. In the previous example, the types of the two anonymous functions can be inferred by the compiler because it knows that the compose methods take two functions as arguments:

view plaincopy to clipboardprint?
static  Function Compose(Function f, Function g)  

But this won’t always work. If you replace the second argument with a lambda instead of a method reference,

view plaincopy to clipboardprint?
Double cos2(Double arg) {  
    return JFun.Compose(z -> Math.PI / 2 - z, a -> Math.sin(a)).apply(arg);         
}  

the compiler is lost and displays the following error message:

Error:(64, 63) java: incompatible types: java.lang.Object cannot be converted to double
Error:(64, 44) java: bad operand types for binary operator '-'
first type: double
second type: java.lang.Object
Error:(64, 72) java: incompatible types: java.lang.Object cannot be converted to java.lang.Double

The compiler is so confused that it even finds a nonexistent error in column 44! But the error in column 63 is real. As strange as it may seem, Java is unable to guess the type of the second argument. To make this code compile, you have to add type annotations:

view plaincopy to clipboardprint?
Double cos2(Double arg) {  
    return JFun.Compose(z -> Math.PI / 2 - z,  (Function)a -> Math.sin(a)).apply(arg);        
}  

This is a good reason to prefer method references.

Local functions
You just saw that you can define functions locally in methods, but you can’t define methods within methods. On the other hand, functions can be defined inside functions without any problem through lambdas. The most frequent case you’ll encounter is embedded lambdas, shown here:

view plaincopy to clipboardprint?
public  Result ifElse(List conditions, List ifTrue) {  
    return conditions.zip(ifTrue)  
          .flatMap(x -> x.first(y -> y._1))  
          .map(x -> x._2);  
}  

Don’t worry if you don’t understand what this code does. You’ll learn about this kind of code in later chapters. Note, however, that the flatMap method takes a function as its argument (in the form of a lambda), and that the implementation of this function (the code after the ->) defines a new lambda, which corresponds to a locally embedded function.

Local functions aren’t always anonymous. They’re generally named when used as helper functions. In traditional Java, using helper methods is common practice. These methods allow you to simplify the code by abstracting portions of it. The same technique is used with functions, although you may not notice it because it’s made implicit when using anonymous lambdas. But using explicitly declared local functions is always possible, as in the following example, which is nearly equivalent to the previous one:

view plaincopy to clipboardprint?
public  Result ifElse_(List conditions, List ifTrue) {  
  Function, Boolean> f1 = y -> y._1;  
  Function>, Result>> f2 =  
                                                       x -> x.first(f1);  
  Function, T> f3 = x -> x._2;  
  return conditions.zip(ifTrue)  
      .flatMap(f2)  
      .map(f3);  
}  

As mentioned previously, these two forms (with or without local named functions) have a little difference that can sometimes become important. When it comes to type inference, using named functions implies writing types explicitly, which can be necessary when the compiler can’t infer types correctly. It’s not only useful to the compiler, but also a tremendous help to the programmer having trouble with types. Explicitly writing the expected types can help locate the exact place where expectations aren’t met.

Closures
You’ve seen that pure functions must not depend on anything other than their arguments to evaluate their return values. Java methods often access class members, either to read or even write them. Methods may even access static members of other classes. I’ve said that functional methods are methods that respect referential transparency, which means they have no observable effects besides returning a value. The same is true for functions. Functions are pure if they don’t have observable side effects.

But what about functions (and methods) with return values depending not only on their arguments, but on elements belonging to the enclosing scope? You’ve already seen this case, and these elements of the enclosing scope could be considered implicit parameters of the functions or methods using them. Lambdas carry an additional requirement: a lambda can access a local variable only if it’s final. This requirement isn’t new to lambdas. It was already a requirement for anonymous classes prior to Java 8, and lambdas must respect the same condition, although it has been made a little less strict. Starting with Java 8, elements accessed from anonymous classes or lambdas can be implicitly final; they don’t need to be declared final, provided they aren’t modified. Let’s look at an example:

view plaincopy to clipboardprint?
public void aMethod() {  
  
  double taxRate = 0.09;  
  Function addTax  = price -> price + price * taxRate;  
  ...  
}  

In this example, the addTax function “closes” over the taxRate local variable. This will compile successfully as long as the taxRate variable is not modified, and there’s no need to explicitly declare the variable final. The following example won’t compile because the taxRate variable is no longer implicitly final:

view plaincopy to clipboardprint?
public void aMethod() {  
  
  double taxRate = 0.09;  
  Function addTax  = price -> price + price * taxRate;  
  ...  
  taxRate = 0.13;  
  ...  
}  

Note that this requirement only applies to local variables. The following will compile without a problem:

view plaincopy to clipboardprint?
double taxRate = 0.09;  
  
public void aMethod() {  
  
  Function addTax  = price -> price + price * taxRate;  
  taxRate = 0.13;  
  ...  
}  

It’s important to note that, in this case, addTax is not a function of price, because it won’t always give the same result for the same argument. It may, however, be seen as a function of the tuple (price, taxRate).

Closures are compatible with pure functions if you consider them as additional implicit arguments. They can, however, cause problems when refactoring the code, and also when functions are passed as parameters to other functions. This can result in programs that are difficult to read and maintain. One way to make programs more modular is to use functions of tuples of arguments:

view plaincopy to clipboardprint?
double taxRate = 0.09;  
  
Function, Double> addTax   
  = tuple -> tuple._2 + tuple._2 * tuple._1;  
  
System.out.println(addTax.apply(new Tuple<>(taxRate, 12.0)));  

But using tuples is cumbersome, because Java doesn’t offer a simple syntax for this, except for function arguments, where the parentheses notation can be used. You’d have to define a special interface for a function of tuples, such as this:

view plaincopy to clipboardprint?
interface Function2 {  
  V apply(T t, U u);  
}  

This interface can be used in lambdas:

view plaincopy to clipboardprint?
Function2 addTax = (taxRate, price) -> price + price * taxRate;  
double priceIncludingTax = addTax.apply(0.09, 12.0);  

Note that the lambda is the only place where Java allows you to use the (x, y) notation for tuples. Unfortunately, it can’t be used in any other cases, such as returning a tuple from a function.

You could also use the class BiFunction defined in Java 8, which simulates a function of a tuple of two arguments, or even BinaryOperator, which corresponds to a function of a tuple of two arguments of the same type, or even DoubleBinaryOperator, which is a function of a tuple of two double primitives. All these possibilities are fine, but what if you need three arguments or more? You could define Function3, Function4, and so on. But currying is a much better solution. That’s why it’s absolutely necessary to learn to use currying, which, as you already saw, is extremely simple:

view plaincopy to clipboardprint?
double tax = 0.09;  
  
Function> addTax   
  = taxRate -> price -> price + price * taxRate;  
  
System.out.println(addTax.apply(tax).apply(12.00));  

Partial function application and automatic currying
The closure and curried versions in the previous example give the same results and may be seen as equivalent. In fact, they are “semantically” different. As I’ve already said, the two parameters play totally different roles. The tax rate isn’t supposed to change often, whereas the price is supposed to be different on each invocation. This appears clearly in the closure version. The function closes over a parameter that doesn’t change (because it’s final). In the curried version, both arguments may change on each invocation, although the tax rate won’t change more often than in the closure version.

It’s common to need a changing tax rate, such as when you have several tax rates for different categories of products or for different shipping destinations. In traditional Java, this could be accommodated by turning the class into a parameterized “tax computer”:

view plaincopy to clipboardprint?
public class TaxComputer {  
  
  private final double rate;  
  
  public TaxComputer(double rate) {  
    this.rate = rate;  
  }  
  
  public double compute(double price) {  
    return price * rate + price;  
  }  
}  

This class allows you to instantiate several TaxComputer instances for several tax rates, and these instances can be reused as often as needed:

view plaincopy to clipboardprint?
TaxComputer tc9 = new TaxComputer(0.09);  
double price = tc9.compute(12);  

The same thing can be achieved with a function by partially applying it:

view plaincopy to clipboardprint?
BinaryOperator addTax = rate -> price -> price * rate + price;  
Function tc9 = addTax.apply(0.09);    
System.out.printf("%.02f", tc9.apply(12.0));  // 13.08 = 12*0.09 + 12   

You can see that currying and partial application are closely related. Currying consists of replacing a function of a tuple with a new function that you can partially apply, one argument after the other. This is the main difference between a curried function and a function of a tuple. With a function of a tuple, all arguments are evaluated before the function is applied. With the curried version, all arguments must be known before the function is totally applied, but a single argument can be evaluated before the function is partially applied to it. You aren’t obliged to totally curry the function. A function of three arguments can be curried into a function of a tuple that produces a function of a single argument. In functional programming, currying and partially applying functions is done so often that it’s useful to abstract these operations in order to be able to do this automatically. In the preceding sections, you used only curried functions and not functions of tuples. This presents a great advantage: partially applying this kind of function is absolutely straightforward.

Write a functional method to partially apply a curried function of two arguments to its first argument (Exercise 2.7):

view plaincopy to clipboardprint?
public static  Function PartialA(A a, Function> f)  
{  
    return f.apply(a);  
}  

You may note that the original function was of type Function>, which means A → B → C. What if you want to partially apply this function to the second argument? Write a method to partially apply a curried function of two arguments to its second argument (Exercise 2.8).

view plaincopy to clipboardprint?
public static  Function partialB(B b, Function> f) {  
    return a -> f.apply(a).apply(b);  
}  

That’s it! In fact, you had nearly nothing to do but to follow the types. As I said, the most important thing is that you had a curried version of the function. You’ll probably learn quickly how to write curried functions directly. One task that comes back frequently when starting to write functional Java programs is converting methods with several arguments into curried functions. This is extremely simple.

Now let's convert the following method into a curried function (Exercise 2.9):

view plaincopy to clipboardprint?
 String func(A a, B b, C c, D d) {  
  return String.format("%s, %s, %s, %s", a, b, c, d);  
}  

The converted curried function as below:

view plaincopy to clipboardprint?
public  Function>>> f() {  
      return a -> b -> c -> d -> String.format("%s, %s, %s, %s", a, b, c, d);  
}  

Switching arguments of partially applied functions
If you have a function of two arguments, you might want to apply only the first argument to get a partially applied function. Let’s say you have the following function:

view plaincopy to clipboardprint?
Function> addTax = x -> y -> y + y / 100 * x;  

You might want to first apply the tax to get a new function of one argument that you can then apply to any price:

view plaincopy to clipboardprint?
Function add9percentTax = addTax.apply(9.0);  

Then, when you want to add tax to a price, you can do this:

view plaincopy to clipboardprint?
Double priceIncludingTax = add9percentTax.apply(price);  

This is fine, but what if the initial function was as follows?

view plaincopy to clipboardprint?
Function> addTax = x -> y -> x + x / 100 * y;  

In this case, the price is the first argument. Applying the price only is probably useless, but how can you apply the tax only? (You suppose you don’t have access to the implementation.)

Let write a method to swap the arguments of a curried function (Exercise 2.11). The following method returns a curried function with the arguments in reverse order. It could be generalized to any number of arguments and to any arrangement of them:

view plaincopy to clipboardprint?
public static  Function> reverseArgs(Function
Function> f) {  
  return u -> t -> f.apply(t).apply(u);  
}  

Given this method, you can partially apply any of the two arguments. For example, if you have a function computing the monthly payment for a loan from an interest rate and an amount:

view plaincopy to clipboardprint?
Function> payment = amount -> rate -> ...  

You can very easily create a function of one argument to compute the payment for a fixed amount and a varying rate, or a function computing the payment for a fixed rate and a varying amount.

Recursive functions
Recursive functions are a ubiquitous feature in most functional programming languages, although recursion and functional programming aren’t connected. Some functional programmers even say that recursion is the goto feature of functional programming, and thus should be avoided as much as possible. Nevertheless, as functional programmers, you must master recursion, even if eventually you decide to avoid it.

As you may know, Java is limited in terms of recursion. Methods can call themselves recursively, but this implies that the state of the computation is pushed on the stack for each recursive call, until a terminal condition is reached, at which time all preceding states of the computation are popped out of the stack, one after the other, and evaluated. The size of the stack can be configured, but all threads will use the same size. The default size varies according to the implementation of Java, from 320 KB for a 32-bit version to 1,064 KB for a 64-bit implementation, both of which are very small compared to the size of the heap, where objects are stored. The end result is that the number of recursive steps is limited.

Determining how many recursive steps Java can handle is difficult, because it depends on the size of the data that’s pushed on the stack, and also on the state of the stack when the recursive process starts. In general, Java can handle about 5,000 to 6,000 steps. Pushing this limit artificially is possible because Java uses memoization internally. This technique consists of storing the results of functions or methods in memory to speed up future access. Instead of reevaluating a result, Java can retrieve it from memory if it has previously been stored. Besides speeding access, this can allow you to partly avoid recursion by finding a terminal state much quicker. We’ll come back to this subject in chapter 4, where you’ll learn how to create heap-based recursion in Java. For the rest of this section, you’ll pretend Java’s standard recursion isn’t broken.

A recursive method is simple to define. The method factorial(int n) can be defined as returning 1 if its argument is 0, and n * factorial(n – 1) otherwise:

view plaincopy to clipboardprint?
public int factorial(int n) {  
  return n == 0 ? 1 : n * factorial(n - 1);  
}  

Recall that this will overflow the stack for n being somewhere between 5,000 and 6,000, so don’t use this kind of code in production. So writing recursive methods is easy. What about recursive functions?

Let's write a recursive factorial function (Exercise 2.12).
Hint.

You shouldn’t try to write an anonymous recursive function, because for the function to be able to call itself, it must have a name, and it must be defined under that name before calling itself. Because it should already be defined when it calls itself, that implies that it should be defined before you try to define it!

Put aside this chicken-and-egg problem for the moment. Converting a single argument method into a function is straightforward. The type is Function, and the implementation should be the same as for the method:

view plaincopy to clipboardprint?
Function factorial = n -> n <= 1 ? n : n * factorial.apply(n – 1);  

Now for the tricky part. This code won’t compile because the compiler will complain about an Illegal self reference. What does this mean? Simply that when the compiler reads this code, it’s in the process of defining the factorial function. During this process, it encounters a call to the factorial function, which isn’t yet defined. As a consequence, defining a local recursive function isn’t possible. But can you declare this function as a member variable or as a static variable? This wouldn’t solve the self-reference problem, because it would be equivalent to defining a numeric variable such as this:

view plaincopy to clipboardprint?
int x = x + 1;  

This problem can be solved by first declaring the variable, and then changing its value, which can be done in the constructor or in any method but is much more convenient in an initializer, such as the following:

view plaincopy to clipboardprint?
int x;  
{  
  x = x + 1;  
}  

This works because members are defined before initializers are executed, so the variable will first be initialized to the default value (0 for an int, null for a function). The fact that the variable is null for some time shouldn’t be a real problem because initializers are executed before the constructor, so unless some other initializer uses this variable, you’re safe. This trick can be used to define your function:

view plaincopy to clipboardprint?
public Function factorial;  
{  
  factorial = n -> n <= 1 ? n : n * factorial.apply(n - 1);  
}  

This can also be used for statically defined functions:

view plaincopy to clipboardprint?
public static Function factorial;  
  
static {  
  factorial = n -> n <= 1 ? n : n * factorial.apply(n - 1);  
}  

The only problem with this trick is that the field may not be declared final, which is annoying because functional programmers love immutability. Fortunately, another trick is available for this:

view plaincopy to clipboardprint?
public final Function factorial =  
                         n -> n <= 1 ? n : n * this.factorial.apply(n - 1);  

By adding this. before the variable name, it’s possible to self-reference it while making it final. For the static implementation, you just have to replace this with the name of the including class:

view plaincopy to clipboardprint?
public static final Function factorial =  
            n -> n <= 1 ? n : n * FunctionExamples.factorial.apply(n - 1);  

The identity function
You’ve seen that in functional programming, functions are treated as data. They can be passed as arguments to other functions, can be returned by functions, and can be used in operations, exactly like integers or doubles. In future programs, you’ll apply operations to functions, and you’ll need a neutral element, or identity element, for these operations. A neutral element will act as the 0 for addition, or 1 for multiplication, or the empty string for string concatenation.
The identity function can be added to the definition of our Function class in the form of a method named identity, returning the identity function:

view plaincopy to clipboardprint?
static  Function identity() {  
  return t -> t;  
}  

With this additional method, our Function interface is now complete, as shown in the following listing.

Listing 2.2. The complete Function interface

view plaincopy to clipboardprint?
package fp.utils;  
  
public interface Function {  
    U apply(T x);  
  
    default  Function compose(Function f) {    
        return x -> this.apply(f.apply(x));    
    }    
    
    default  Function andThen(Function f) {    
        return x -> f.apply(apply(x));    
    }    
      
    static  Function Identity() {  
        return t -> t;   
    }  
  
    static  Function Compose(Function f, Function g) {  
        return x -> f.apply(g.apply(x));  
    }  
  
    static  Function andThen(Function f, Function g) {  
        return x -> g.apply(f.apply(x));       
    }  
  
    static  Function, Function, Function>> compose() {  
        return x -> y -> y.compose(x);  
    }  
  
    static  Function, Function, Function>> andThen() {  
        return x -> y -> y.andThen(x);  
    }  
  
    static  Function, Function, Function>> higherAndThen() {  
        return x -> y -> z -> y.apply(x.apply(z));  
    }  
  
    static  Function, Function, Function>> higherCompose() {  
        return (Function x) -> (Function y) -> (T z) -> x.apply(y.apply(z));  
    }  
}  

Java 8 functional interfaces
Lambdas are used in places where a specific interface is expected. This is how Java can determine which method to call. Java doesn’t impose any constraints on naming, as may be the case in other languages. The only constraint is that the interface used must not be ambiguous, which generally means it should have only one abstract method. (In reality, it’s a bit more complex, because some methods don’t count.) Such interfaces are said to be SAM type, for single abstract method, and are called functional interfaces.

Note that lambdas aren’t used only for functions. In standard Java 8, many functional interfaces are available, although they aren’t all related to functions. The most important ones are listed here:

* java.util.function.Function is close to the Function developed in this chapter. It adds a wildcard to the method parameter types to make them more useful.
* java.util.function.Supplier is equivalent to a function with no argument. In functional programming, it’s a constant, so it might not look useful at first, but it has two specific uses: First, if it’s not referentially transparent (not a pure function), it can be used to supply variable data, such as time or random numbers. (We won’t use such nonfunctional things!) The second use, much more interesting, is to allow lazy evaluation. We’ll come back to this subject often in the next chapters.
* java.util.function.Consumer isn’t at all for functions, but for effects. (Here, it’s not a side effect, because the effect is the only result you get with a Consumer, since it doesn’t return anything.)
* java.lang.Runnable can also be used for effects that don’t take any parameters. It’s often preferable to create a special interface for this, because Runnable is supposed to be used with threads, and most syntax-checking tools will complain if it’s used in another context.

Java defines many other functional interfaces (43 in the java.util.function package) that are mostly useless for functional programming. Many of them deal with primitives and others with functions of two arguments, and there are special versions for operations (functions of two arguments of the same type).

In this book, I don’t talk much about standard Java 8 functions. This is intentional. This isn’t a book about Java 8. It’s a book about functional programming, and it happens to use Java for the examples. You’re learning how to construct things rather than to use provided components. After you master the concepts, it’ll be up to you to choose between your own functions or the standard Java 8 ones. Our Function is similar to the Java 8 Function. It doesn’t use a wildcard for its argument in order to simplify the code shown in the book. On the other hand, the Java 8 Function doesn’t define compose and andThen as higher-order functions, but only as methods. Other than these differences, these Function implementations are interchangeable.

Debugging with lambdas
Using lambdas promotes a new style of code writing. Code that was once written in several short lines is often replaced with one-liners such as this:

view plaincopy to clipboardprint?
public  T ifElse(List conditions, List ifTrue, T ifFalse) {  
  return conditions.zip(ifTrue).flatMap(x -> x.first(y -> y._1))  
                               .map(x -> x._2).getOrElse(ifFalse);  
}  

(Here, the implementation of the ifElse method is split over two lines because of the book margins, but in a code editor it could be on a single line.)
In Java 5 to 7, this code would be written without using lambdas, as shown in the following listing.
Listing 2.3. A one-liner lambda-based method converted to previous Java versions

view plaincopy to clipboardprint?
public  T ifElse(List conditions, List ifTrue, T ifFalse) {  
  
  Function, Boolean> f1 =  
      new Function, Boolean>() {  
        public Boolean apply(Tuple y) {  
          return y._1;  
        }  
      };  
  
  Function>, Result>> f2 =  
      new Function>, Result>>() {  
        public Result> apply(List> x) {  
          return x.first(f1);  
        }  
      };  
  
  Function, T> f3 =  
      new Function, T>() {  
        public T apply(Tuple x) {  
          return x._2;  
        }  
      };  
  
  Result>> temp1 = conditions.zip(ifTrue);  
  Result> temp2 = temp1.flatMap(f2);  
  Result temp3 = temp2.map(f3);  
  T result = temp3.getOrElse(ifFalse);  
  return result;  
}  

Obviously, reading and writing the lambda version is much easier. The pre-Java 8 versions were often considered too complicated to be acceptable. But when it comes to debugging, the lambda version is much more of a problem. If a single line is equivalent to 20 lines of traditional code, how can you put breakpoints in it to find potential errors? The problem is that not all debuggers are powerful enough to be used easily with lambdas. This will eventually change, but in the meantime you might have to find other solutions. One simple solution is to break the one-line version into several lines, such as this:

view plaincopy to clipboardprint?
public  T ifElse(List conditions, List ifTrue, T ifFalse) {  
  return conditions.zip(ifTrue)  
                   .flatMap(x -> x.first(y -> y._1))  
                   .map(x -> x._2)  
                   .getOrElse(ifFalse);  
}  

This allows you to set breakpoints on each physical line. It’s certainly useful and it makes the code easier to read (and easier to publish in books). But it doesn’t solve our problem because each line still contains many elements that can’t always be investigated through traditional debuggers.

To make this problem less crucial, it’s important to extensively unit test each component, which means each method and each function passed as an argument to each method. Here, it’s easy. The methods used are (in order of appearance) List.zip, Option.flatMap, List.first, Option.map, and Option.getOrElse. Whatever these methods are doing, they can be extensively tested. You don’t know about them yet, but you’ll build the Option and List components in the next chapters, and also write the implementations of the map, flatMap, first, zip, and getOrElse methods (as well as many others). As you’ll see, these methods are purely functional. They can’t throw any exceptions and they always return the intended result without doing anything else. So, after they’re fully tested, nothing bad can happen.

Regarding the functions, the preceding example uses three of them:

* x → x.first
* y → y._1
* x → x._2

The first one can’t throw any exceptions because x can’t be null (you’ll see why in chapter 5), and method first can’t throw an exception either. The second and third functions can’t throw a NullPointerException because you’ve ensured that a Tuple couldn’t be constructed with null arguments. (See chapter 1 for the code of the Tuple class.) Figure 2.4 shows these functions in their anonymous form.

Figure 2.4. Functions in their anonymous form

This is one area where functional programming shines: if no components can break, the whole program can’t either. In imperative programming, components might work fine in tests but break in production because of some nondeterministic behavior. If the behavior of a component depends on external conditions, you have no way to fully test it. And even if no component has any problem as a unit, the composition of several components could create conditions for the program to be ill-behaved. This can’t happen with functional programming. If the components have a deterministic behavior, the whole composition will be deterministic too.

Many spots remain open for errors. The program might not do what is expected, because the components may be composed the wrong way. But implementation errors can’t cause an unwanted crash. If this program crashes, it will be, for example, because a null reference has been passed to the Tuple constructor. You don’t need a debugger to catch this kind of error.

So, yes, debugging functional programs that use lambdas extensively is somewhat more difficult than debugging imperative programs, but debugging is much less necessary, provided all the components have been validated. Keep in mind that this is true only if a thrown exception crashes the program. We’ll come back to this in chapter 6. But for now, remember that by default, an exception or an error thrown will only crash the thread in which it happened, and not the whole application. Even an OutOfMemoryError might not crash the application, so you, as the programmer, have to handle this.

Supplement
* Wiki - Covariance and contravariance (computer science)
* Ch2 - Using functions in Java : Part1
* Ch2 - Using functions in Java : Part2

程式扎記

標籤

2018年6月7日星期四

[ FP with Java ] Ch2 - Using functions in Java : Part2

1 則留言:

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

檢舉濫用情形

學習筆記

標籤

2018年6月7日 星期四