In Understanding Lambda/Closure, I talked about what lambda/closure is, how different languages support it, and why JDK8 adopts the current lambda syntax. Using lambda wisely may be learned from languages already featured first-class functions. In those languages, however, most ideas of first-class functions come from functional programming directly or indirectly. Furthermore, the model of functional programming is based on lambda calculus. When moving yourself through these concepts one by one, you'll gradually know where the playground of lambda/closure is.
In Understanding Lambda/Closure, Part 6 - First Class Functions and Lambda Calculus, we've introduced basic ideas about lambda calculus. From this article, we’ll look at what functional programming is and how to do that in Java. But, why should programmers learn about functional programming?
In the article Can Your Programming Language Do This?, Joel Spolsky said that...
...programming languages with first-class functions let you find more opportunities for abstraction.
In the book Coders at Work, Simon Peyton Jones mentioned that...
...the perspectives you learn over here in the purely functional world can inform and illuminate the mainstream.
In the book Functional Programming for Java Developers, Dean Wampler listed five points in the first chapter "Why Function Programming?":
- I Have to Be Good at Writing Concurrent Programs
- Most Programs Are Just Data Management Problems
- Functional Programming Is More Modular
- I Have to Work Faster and Faster
- Functional Programming Is a Return to Simplicity
The best way to know what these quotes mean is doing functional programming directly. First, let's see how to get a Fibonacci number. According to the Fibonacci number page of Wikipedia…
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation Fn = Fn-1 + Fn-2 with seed values F0 = 0, F1 = 1.
In imperative programming, we have to provide computers with steps about how to solve the problem. For example, we may use Java to implement a static method as follow:
static int fib(int n) {
if(n == 0 || n == 1) {
return n;
}
int a = 0;
int b = 1;
for(int i = 2; i <= n; i++) {
int tmp = b;
b = a + b;
a = tmp;
}
return b;
}
if(n == 0 || n == 1) {
return n;
}
int a = 0;
int b = 1;
for(int i = 2; i <= n; i++) {
int tmp = b;
b = a + b;
a = tmp;
}
return b;
}
In functional programming, we just have to define the problem. That is, declare the problem with your programing language. For example, using Java to declare the problem may be as follow:
static int fib(int n) {
if(n == 0 || n == 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
if(n == 0 || n == 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
The code looks better when considering readability. Using a language which directly supports functional programming may further the readability. For example, the following Haskell implementation looks just like the mathematical definition of Fibonacci numbers.
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)fib 0 = 0
fib 1 = 1
fib n = addPrevsRecusivelyUntilCounterIsN (fib 1) (fib 0) 2 n
addPrevsRecusivelyUntilCounterIsN prev1 prev2 counter n
| counter == n = result
| otherwise = addPrevsRecusivelyUntilCounterIsN result prev1 (counter + 1) n
where result = prev1 + prev2Well, tail recursion may come with some added complexity. There are almost conflicts between performance and readability. Even that, we still don't lose the basic principle of functional programming. Though the definition becomes more verbose, we still just define what the problem is. Using functional languages gives you more opportunities to find the balance between performance and readability. You may use tail recursion to write the previous Java function. The code, however, will be more complex, and Java doesn't support tail recursion elimination.
The point here is that, you cannot just apply all concepts directly without any thinking if your language is not a functional language. Or, you may get half the result with twice the effort; your code may have bad readability and even poor performance. If you want to do purely functional programming, using functional languages is a good idea, such as Scala, Haskell, etc.
How can we write code functionally with those not functional languages? Understanding the essence of functional programming can bring us knowing how to suitably adopt ideas of that.
One apparent form in functional programming is recursion. But, the point is not recursion. The point is how to divide a problem into sub problems. Recursion is just and often a natural form after dividing a problem. Let's take an example about summing up a number list. Solving the problem imperatively requires commanding computers to initialize a variable sum to zero, get the next element of the list, add the element to sum until all elements are iterated, and then return sum.
static int sum(int... nums) {
int sum = 0;
for(int num : nums) {
sum += num;
}
return sum;
}
int sum = 0;
for(int num : nums) {
sum += num;
}
return sum;
}
How to solve the problem functionally? Let's rethink the problem of summing up a number list. A sub problem is what's the sum of an empty list. It's zero. The other sub problem is what's the sum of the head element x and the tail list xs. It's the sum of x and the sum of xs. Let's write these two sub problems in Haskell.
sum [] = 0
sum (x:xs) = x + sum xs How to solve these two sub problems? You don't have to do that; Haskell will do that for you. You just have to define problems.
"Wait! Wait! Wait! We're talking about Java...Please don't list those Haskell codes again...XD" Yes! But, object-oriented programming is the main paradigm of Java. Before using Java to solve this problem functionally, we should talk something about algebraic data types, common patterns when processing lists, and immutability. All of these will be covered in later articles...