Recursion, Tail-call Optimization & Currying
A hodgepodge of 3 functional programming concepts
(Edit: I initially began writing this post with the intention of compiling an exhaustive list of ‘methods of functional programming’ known to me. Since then, I’ve done some Real™ functional programming, and it’s become ever more evident to me that functional programming is a dense paradigm and its ‘methods’ are merely by-products of the core values it promotes. Nevertheless, this is probably a good introductory read for a beginner familiar with procedural programming.)
There are many methods derived from functional programming that could really add to the common programmer’s repertoire of tricks. These methods don’t reach a wide audience because they are often found in academic literature or among communities of less common languages like Lisp, Haskell etc. Here I explain a few of them using two popular languages: Python and JavaScript. We won’t discuss many of the technical aspects, but we’ll see how they come in handy.
In writing this article, it has become clear to me that there has to be a separate “Why functional programming?” article. I won’t be writing that. If you’re curious, Google’s your friend. I’d recommend the paper Out of the Tarpit — one of the classics.
A few notes before we start
We’re about to discuss ‘programming paradigms’, which is not ‘code’ — i.e. they’re not concrete implementations of a concept in a specific programming language. These methods are independent of any programming language. However, this means that some of the methods cannot be used in some languages due to the implementation details of that language.
Also, many of these methods are not exclusive to functional programming — infact, you might find that you use many of the methods regularly even though you’re not familiar with functional programming. However, there maybe methods which are necessary conditions for programs to be considered functional.
Recursion vs Iteration
You’re probably thinking: “Hey, that’s not a functional programming concept. This is basic stuff.”
It definitely is. But in the case of functional programming, you have to use recursion not because you can, but you because you have to. (At least, in the strictest definition of functional programming. It’s not technically disallowed, but it’s discouraged.)
As explained in another article, in functional programming we care about purity — i.e. lack of side-effects. What this means is, you try to structure your code as a function that takes in an input, and gives out an input. We don’t change state (put another way, we don’t declare global variables, wherever possible). There are many reasons for doing so, such as referential transparency, better parallelizability, avoiding non-obvious dependencies etc. (read about the reasons here).
You’re probably thinking: “But that’s impossible! How can you avoid declaring globally-scoped variables?”
Well, it seems there are tons of methods to do so. For example, recursion.
If you can’t declare a variable, then how do you implement a loop? Using a loop counter involves state — so how do you work around that? Recursion, of course.
Let’s take an example in Javascript [since the different is not as clear in Python]:
var n = 10;
var ans = 1;for (i = 1; i <= n; i++) {
ans = i * ans;
}console.log(ans);
Now, this is a simple bit of code that finds the value of n! (n-factorial, i.e. 3! = 3 x 2 x 1). How would you do this recursively, without declaring the counter variable i?
function factorial(n) {
if (n != 0) {
return n * factorial(n-1);
}
else {
return 1;
}
}factorial(10);
Clearly, we achieved the same result without declaring variables. Now, a word of caution— wait, we’ll take that up in the next section.
Tail-call Optimization
I deliberately picked the factorial example above to demonstrate tail-call optimization. When you use the recursive solution to find the factorial of a really large number n, you may find that your system runs out of memory. This is quite obvious from the function, because the actual multiplication is deferred until all values are obtained by the return clause. For example, for 10!: 10*factorial(9) is expanded to 10*9*factorial(8) and so on — all the numbers until 1 have to be obtained before this can be multiplied.
So, it seems like the iterative solution is the better one. But there’s a better way around! And that method is called tail-call optimization.
Here’s the tail-call optimized version of the above recursive solution [note that the language has to support this — JS ES2015+ does, but Python doesn’t]:
function factorial (n) {
function fact(num, acc) {
if (n < 2) {
return acc;
}
else {
return fact(n-1, n * acc);
}
}
return fact(n, 1);
}Now, this gives us the same result without the memory issues. We worked around the issue of delayed evaluation by using an accumulator. This example should convince you that there’s often a work-around even though some methods in FP may seem unreasonable or impossible in practice.
Currying
Now this is one of my favourite methods for its sheer practical use: if used properly, this method can reduce repetition in your code and enhance reusability, and also make your code easier to understand (if used judiciously though!).
Currying in it’s simplest form, is simply about replacing a function f(a,b,c) that takes 3 variables (a, b and c) with a function g(a)(b)(c). Say what? Here’s an example in Python:
> def f(a,b,c):
return a + b + c> f(1,2,3)
6
can be replaced with:
> def g(a):
def g1(b):
def g2(c):
return a + b + c
return g2
return g1> g(1)(2)(3)
6
Not clear how that happened? Maybe this will help:
> g(1)
<function g1 at 0x1007f7230>> g(1)(2)
<function g2 at 0x1007f7410>> g(1)(2)(3)
6
From the above code snippet, one thing should be clear: calling g(1) generates a function, and so does g(1)(2) which gives the final function g2 in the chain. When this function is called, we get the result 6.
So how is this useful, you ask?
Currying allows you to ‘customize’ functions by wrapping it in even more general functions — i.e. to get specialized functions from more generalized functions.
In languages like Python where functions are also first-class citizens, you should remember that functions can be arguments.
Let’s take an example:
> def g(function1):
def g1(list):
def g2(key):
return a(b[c])
return g2
return g1> g(round)(listofnumbers)(3)
Just look at how reusable that is: you’re applying the round function to the elements in a list called listofnumbers with key 3. You can change all of it — you can change the function, the list, and the key. This means you don’t have to code it again in case you want to use a different function, or a different list. If you use this with a map function, the possibilities are endless!
[This post is incomplete. I didn’t know where I was taking it, and I still don’t. I don’t agree with all of the content I wrote a while back — but I doubt that really matters. To steal a line from Zuckerberg: if you’re not embarrassed by your first product release, you’ve released it too late.]
