Functional Programming for Java Developers, Part 3

After defining (or simulating) the list with the concept of algebraic data types, let's get back to the final question left in the Functional Programming for Java Developers, Part 1. We're talking about Java, so we have to translate the following code to Java:

sum [] = 0
sum (x:xs) = x + sum xs

Java doesn't support pattern match, so we use if to check whether a list is Nil. We can define a sum method as follow:

public static Integer sum(List<Integer> lt) {
if(lt == Nil) return 0;
else return lt.head() + sum(lt.tail());
}

After defining the sum method, sum(list(1, 2, 3, 4, 5)) will return the result 15. Look Great. Then, how to define an addOne method to add 1 to each list element? A sub problem is what should be returned when the list is empty? Just return the empty list. The other sub problem is how to get the result from the head element x and the tail list xs. Add 1 to x, us xs to call the addOne method, and use the method cons to get the new list. Let's write these two sub problems in Java.

public static List<Integer> addOne(List<Integer> lt) {
if(lt == Nil) return nil();
else return cons(lt.head() + 1, addOne(lt.tail()));
}

Similarly, defining a method to subtract 2 from each list element just needs changing (+ 1) to (- 2) and renaming addOne to subtractTWO. Defining a method to multiply each list element by 3 just needs changing (+ 1) to (* 3) and renaming addOne to multiplyByThree. Can you see that? If (+ 1), (- 2) and (* 3) are first-class functions, we'll be able to reuse the code template. Hey! JDK8 Lambda will introduce first class functions, doesn't it? We can define a functional interface as follow:

public interface F1<P, R> {
R apply(P p);
}

Mapping a list of something to a list of others is a common pattern when dealing with a list. We can define a map method to do that.

public class AlgebraicType {
    ...
    public static <T, R> List<R> map(List<T> lt, F1<T, R> f) {
        if(lt == Nil) return nil();
        return cons(f.apply(lt.head()), map(lt.tail(), f));
    }
}

Then, adding 1 to each list element can be as follow:

map(list(1, 2, 3, 4, 5), x -> x + 1);

Subtracting 2 from each list element can be as follow:

map(list(1, 2, 3, 4, 5), x -> x - 2);

Multiplying each list element by 3 can be as follow:

map(list(1, 2, 3, 4, 5), x -> x * 3);

The map is a really versatile method that can be used in millions of different ways. Similarly, how to filter out list elements greater than 3? We can write code as follow:

public static List<Integer> greaterThanThree(List<Integer> lt) {
    if(lt == Nil) return nil();
    else {
        if(lt.head() > 3) {
            return cons(lt.head(), greaterThanThree(lt.tail()));
        }
        else {
            return greaterThanThree(lt.tail());
        }
    }
}

How to filter out list elements smaller than 10?

public static List<Integer> smallerThanTen(List<Integer> lt) {
    if(lt == Nil) return nil();
    else {
        if(lt.head() < 10) {
            return cons(lt.head(), smallerThanTen(lt.tail()));
        }
        else {
            return smallerThanTen(lt.tail());
        }
    }
}

Filtering a list of elements is a common pattern when dealing with a list. We can define a filter method to do the work.

public class AlgebraicType {
    ...
    public static <T> List<T> filter(List<T> lt, F1<T, Boolean> f) {
        if(lt == Nil) return nil();
        else {
            if(f.apply(lt.head())) {
                return cons(lt.head(), filter(lt.tail(), f));
            }
            else {
                return filter(lt.tail(), f);
            }
        }
    }
}

Then, filtering a list of elements greater than 3 is as follow:

filter(list(1, 2, 3, 4, 5), x -> x > 3);

filtering a list of elements smaller than 10 is as follow:

filter(list(10, 19, 3, 4, 5), x -> x < 10);

The filter is a really versatile method that can be used to filter elements in millions of different ways. Similarly, reducing a list of elements to a single value is a common pattern. Before that, we define a functional interface as follow:

public interface F2<P, R> {
R apply(R r, P p);
}

Then, we define a reduce method as follow:

public class AlgebraicType {
    ...
    public static <T, R> R reduce(List<T> lt, F2<T, R> f, R r) {
        if(lt == Nil) return r;
        else {
            return reduce(lt.tail(), f, f.apply(r, lt.head()));
        }
    }
}

Summing up a list of elements can be done as follow:

reduce(list(1, 2, 3, 4, 5), (sum, x) -> sum + x, 0);

Understanding the magic which the reduce method plays is not easy for a functional programming novice. The reduce method is also called as foldLeft. What it does is like folding a paper from the left. What the code reduce(list(1, 2, 3, 4, 5), (sum, x) -> sum + x, 0) does is like the animation shown below. Every time you fold the paper, you add the left number to the right number. After completing the work, you get the final result.

The reduce is a really versatile method. You have millions of different ways to reduce a list of elements to a single value. The point here is, however, If you code functionally, you can easily find the similar structure between functions, distill and reuse the high level abstraction. The map, filter and reduce methods shown here are good examples for that. Once you can think functionally, you'll find more high level abstractions.