Introduction to Functional Programming

• Eh, wao I could write a function nested inside another function.
• Oh, look, I could pass a function as an argument to another function.
• Oh, wao, look at this, my function returned another function, keeewl.
• What, what is this lambda? awesome, with this I could one-lineize most of my code.
• Closure ?, eh, ao, I can use this to create a function that "magically" return a different value each time it's called?
• ParallelMap!!, a powerful function that eats away my CPU resource to boost computation time!

Damn, I'm such a functional-programmer by abusing all these cool stuff. Screw "def", eat this lambda, and while I'm on it, let's add more magic called "map" and "reduce" to the code to confuse anyone who cared enough to read it.

Well, that little sinful flashback is probably what I have in mind during my Recognition System project, and my definition of Functional Programming.

But, it all changed upon following this course in the coursera. And here, on this post, I'll write an introduction to functional programming.

Q:
So, what is this functional programming?

A:
Apparently, It's not about how you write code, or how you pass a function, or how you write a function that return another function.
It's a paradigm, about how to think of a solution to a problem.

This straight-forward definition of wikipedia, might give you an insight. (though for me it doesn't, until I actually do an exercise myself)

functional programming is a programming paradigm, a style of building the structure and elements of computer programs, that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

http://en.wikipedia.org/wiki/Functional_programming

If you still doesn't get the gist of it, don't worry, I don't get it either just by reading it the first time.

But now, let's consider the following fibonnaci bottom-up solution, with imperative style written in python.

1. def fib(n):  
2.         a = 0  
3.         b = 1  
4.         for i in xrange(0, n):  
5.                 c = a + b  
6.                 a = b  
7.                 b = c  
8.         return a

Now, if we translate that code, into a more human friendly instruction:

• To get the n-th fibonnaci
• first, prepare two container let's call it a and b, and fill it with 0 and 1 respectively.
• repeat the following process up to n-time
• prepare another container called c, and fill it with the sum of a and b
• store the value of b to a
• store the value of c to b
• at the end of the process, the answer is the value stored at container a

That's it, in imperative programming, we literally think a solution to a problem as an instruction to the computer, about how to store a value to a memory, what to be stored, when to be changed, how long an instruction should be repeated, when should it be terminated, and so on.

With that being said, consider the following code, written in scala doing the exact similar thing, except that it's written in recursive.

1. def fib(n: Int): Int    
2.         @tailrec
3.         def fibloop(counter: Int, ans1: Int, ans2: Int): Int
4.                 if(counter == 0) ans2
5.                 else fibloop(counter - 1, target, ans1 + ans2, ans1)
6.         fibloop(n, 1, 0)

Now, if we translate it, into something more human friendly instruction, it becomes:

• The n-th fibonacci is: 
• The result of fibloop(n, 1, 0)
• But, what is fibloop?
• fibloop is a function that take 3 parameter counter, ans1, and ans2
• it'll return ans2  if counter = 0
• or otherwise, it return the result of fibloop(counter - 1, ans1 + ans2, ans1)

That's it.

In functional programming, we don't write a program that mutate a variable, an instruction that repeated several times, a condition to break out of the loop, or anything along that line, but we write a mathematical expression to a solution of a problem.

You might think, that merely converting an iterative solution, to a recursive one isn't really that much different, and if anything, it might be even worse on performance. However, there's a huge paradigm different between the two.

In the recursive version, A solution to a problem, isn't represented by what instruction should be done, and how many-time it should be repeated.

It's represented, as a simple expression that, once evaluated, answer the given question.

Additionally, the cerebration of recursive, is that:

Instead of going straight ahead solving a difficult problem, we're loooking for a solution of similar problem, but this problem in one-step-easier than that.
Can you solve it now? No? then, consider another problem that's one-step-easier, and so on, until you can solve it :)

To summarize, unlike the imperative-programming, in functional-programming, we didn't write a solution as a computer instruction, but we write it as a mathematical expression. Which means:

• There's no variable assignment.
  There's no mutable variable.
  There's no law-breaking mathematical expression like x = x + 1.
  #But there's a substitution to simplify a long expression like a = e ^ (b + c * d ).
  #An immutable variable isn't a constant, mind you, it's a variable that doesn't change on the scope it's defined.
• There's no loop, break, assignment,  and other computational-instructions,
  #Don't even ask about jump.
• A function, could very well become a parameter, or even return value.
  #Remember Integral? yeah that's one example about a function taking an argument of a function, and returned another function).

Okay, that's about everything I want to write in this article, sorry that, there's no higher-order-function, closure, and other functional concept, because what I'm trying to write here is the paradigm itself, instead of the "how-to-code"-tutorial.

Notice the lack of Madoka in this post? Here have this gem.

p.s: yes, this is also another preaching to madokaism.