Functional Programming for Imperative Programmers

This article only covers basic characteristics which separate out Functional languages from Imperative languages. All of following concepts are applicable on all functional languages. After this, select one language and read related tutorial.

We are living in a Matrix, Matrix of Imperative world. e.g. if I ask you write a program to print 1 to 10, the program will be:

for (int i=1; i<=10 ;i++) {     printf("%d\n", i); }

In the Matrix of functional programming, there are no for/while loop. Then, how we shall print such numbers? Following is an example in ‘elixir’:

1	Enum.map(1..10, fn(x) -> IO.puts x end)

yes, that’s it. Few functional languages (like ocaml/F#) provide ‘for’ loop which is nothing but synthetic sugar to provide similar functionality, but they do not support complete functionality of a for loop like break, continue.

So, while reading this article, try to understand a completely different world from a completely different perspective. You are going from one Matrix to another Matrix. Remember, there is no real world.

Characteristics of Functional Programming

Purity

Pure code is something which is neither effected by external world nor effects external world. In other word, a function is pure if it provides same output for same set of inputs. e.g.

int sum(int a, int b) {     return (a+b); }

now, whatever happens in world, let USA attack Russia, let there be some earth quack, for  a=3 and b=4, the output of function sum will always remain 7. Now lets check another example:

int c = 0; int sum_avg(int a, int b) {     if(c == 0)         return (a + b);     return (a + b)/2; }   int main_func () {     int sum = sum_avg(3, 4);     c = 1;     int avg = sum_avg(3, 4); }

Can you predict output of sum_avg function? No. It depends on the value of ‘c’ variable, which is global and can be modified anytime. The function sum_avg will return different values for same set of inputs, so sum_avg function is not pure. If I write sum_avg again as

int sum_avg(int a, int b, int c) {     if(c == 0)         return (a + b);     return (a + b)/2; }   int main_func () {     int sum = sum_avg(3, 4, 0);     int avg = sum_avg(3, 4, 1); }

After this changes, function sum_avg is a pure function. For same set of input, output will always remain same.

The major advantage of Purity is better support for concurrency. Since a pure function does not have any dependency on any external data/function, it can be run in parallel.

Immutability

Now, imagine a function in which you can not modify any variable? Seems funny/impossible/useless? But this is the core of a functional programming language.

Functional programming languages do not support Mutable data structures and this sentence is pure lie. The correct sentence will be Functional programming languages do not encourage use of Mutable data structure.

How it is done? I have one list in which I need to add another element, but list is immutable. Lets see it in Haskell:

addElement a lst = a : lst   lst = [1,2,3,4,5] lst1 = addElement 0 lst   lst1 [0,1,2,3,4,5]

Function addElement is used to append a element to a list in beginning.  We have one list lst. It is not possible to mutate this list, but if you want to add a element, call addElement function and store the result in lst1. lst and lst1 represent two independent lists in memory, so no mutation of any variable and yet you have a list which you wanted.

Recursion

As we already discussed, functional languages do not support loops, then how do they perform repetitive task? Try to remember school days, where in initial classes teachers discussed about ‘Recursion’, and then we read somewhere ‘Recursion’ is not good and should not be used. Here Recursion is good and god.

e.g. create a list of 1 to 10 of even numbers.

generateList _ 0 = [] generateList i j = if even i then i : generateList (i+1) (j-1)                              else generateList (i+1) (j-1)

There are other simple way to do it, but for now lets stick to this version. We wrote a function generateList, which takes two parameters – i (start) and j (end);

Wait, variable with name i and j. This is really not a good practice, right? Not in imperative languages, where functions are lengthy and at some point, you might have to go back to definition to find out what i and j are taken for. In case of functional programming, functions are small and concise. So, taking variables with name i, j, x, y are pretty common.

If i is even, append i and call generateList function again with i+1 and j-1. If j becomes 0, return an empty list.

Output of above program:

generateList 1 10 [2,4,6,8,10]

Tail Call Optimization: TCO is the reason why recursion is not considered evil in functional programming. When a function recursively calls itself, and there is no need to wait for its return, the stack will be replaced. The above answer is not Tail Call optimized, because we are waiting for return value of generateList, so that we can append i.  Remember, just like imperative languages, function language will cause stack overflow with large iteration during recursion, if not TCO optimized.

Here is TCO version of same program.

generateList' _ 0 x = x generateList' i j x = if even i then generateList' (i+1) (j-1) (i:x)                                 else generateList' (i+1) (j-1) x

Higher Order Functions and Closure support

Higher-order functions are functions that take other functions as their arguments. Ok, so what?

We have some good functions provided by functional languages mainly map, fold, filter. These are your savior from recursion. How? Lets see.

map: map takes one function as a parameter and execute it on each member of list and returns a new list. e.g., lets double each element of a list.

a = [1,2,3,4,5] dblMe = map (doubleElement) a   doubleElement x = 2 * x

Output:

dblMe [2,4,6,8,10]

So, map is higher order function. Now, lets modify doubleElement and pass a closure instead a complete function.

a = [1,2,3,4,5] dblMe = map (\ x -> 2 * x) a

Normally all functional languages support Closures.

fold: Fold also takes a function as parameter, a initial value and executes it on each element of list and returns a folded value. e.g Sum of all elements of list.

foldMe = foldl (\ acc x -> acc + x) 0 a

Output:

a = [1,2,3,4,5] foldMe 15

Fold takes each element from list ‘a’ and pass it to closure. Closure add it to acc, which is initialized with 0. Finally sum of all elements is returned.

filter: Filter also takes a function as parameter (but this function returns Bool value) and executes it on each element of list. If passed function returns True, filter appends element in return list. e.g lets write previous program which generates a list of even numbers in Elixir.

1	1..10 |> Enum.filter(fn x -> rem(x, 2) == 0 end)

Comments and Bugs are invited.