At Coshx Labs, every week, we have a special 60 min slot on Wednesdays. This slot can be booked by anyone to organize what we call a techlunch. During that meeting, you can introduce your peers to either a new tool or the latest technologic crunch you had. A couple of weeks ago, I introduced my colleagues to functional programming. For mostly of them, it was a simple reminder. Nevertheless, for some of them, this concept was completely unknown.

Then, two weeks after, I decided to teach a class about the same topic at Rails School. None of my students was aware about this type of coding. They only knew the traditional imperative style of languages like C and Java.

Thanks to some new languages such as Clojure and Elixir, functional programming is making a comeback. Haskell and Lisp were the precursors. Nevertheless, in my opinion, it is still underestimated. That’s why I made the decision to write this article, and share with you, loved followers, an overview of that paradigm.

The basis

Functional programming relies on 3 key ideas:

  • First class citizenship
  • Pure functions
  • Partial application

Let’s start with first class citizenship, sometimes introduced as first class functions too. A coding language has first class citizens if every expression is a function. In other words, you can define functions, functions can be passed as argument and functions can be outcome of other functions. If you have ever passed a lambda/closure function as an argument, you have used that citizenship. This behaviour is present in languages such as C#, JavaScript, Swift…

A function is pure if and only if it has no side effect. A pure math function is a perfect example of pure function. Every time you apply that function with the same arguments, you are sure the result is going to be the same.

For instance, here is a pure function (in Swift):

func multiply(x: Int, y: Int) -> Int {
    return x * y
}

If you use the same arguments ever and ever, the result will not change.

The function below is not pure:

func customInit(myCustomObject: MyCustomClass) {
    if myCustomObject.hasBeenInit {
        return true
    } else {
        myCustomObject.hasBeenInit = true
        return false
    }
}

You are updating an existing object. Once you have applied that function, your object will not be the same when returning.

Finally, partial application is a very particular concept. It allows developers to partially apply a function. That sounds obvious, doesn’t it?

Do you see that multiply function above? A language supports partial application if you are able to call multiply with a single argument. Then, the system will return another function, expecting only one parameter (y in that case). That result function multiplies any provided y with the x value provided in first place.

Maybe the example below is more clear:

func multiply(x: Int) -> ((Int) -> Int) {
    return { y in
        return x * y
    }
}

Using that process, you can transform any function to its currying counterpart. I am not going to talk about that concept here, I invite you to read this very interesting Wikipedia article if you want to know more.

Time to exercise

Well, now you are in the loop. It is time to try coding as a functional way. As I said before, in a pure functional language, any expression is a function. Then, forget variable declarations and loops in your code. When programming, you can only either return a result or call another function. In some languages, such as Lisp, even an if statement is a function.

Then, recursivity is the key. Anytime you need to iterate over an array, you need to browse it as a recursive way.

For instance, this function sums the elements of an integer array:

func sumArray(a: [Int]) -> Int {
    return sumArrayAux(a, index: 0, size: a.count)
}

func sumArrayAux(a: [Int], index i: Int, size n: Int) -> Int {
    if i == n {
        return 0
    } else {
        return a[i] + sumArrayAux(a, index: i + 1, size: n)
    }
}

Let’s pay attention to that sample. There is no variable declaration (no let or var keywords around). If I browse each line of my code, it is only the result of another function (if we assume if and else are functions that return true or false for the provided condition) or a return statement. Thus, I match all my conditions.

As you may have seen, the most part of the time, you need to define a helper function (often named as auxiliary function). This function will have an internal purpose only and prettify your main function, here sumArray.

Well, you think you’re ready? Alright, so try to code a function that, instead of summing, multiplies all the elements of an integer array.


Done? Ok, time to check your solution:

func multiplyArray(a: [Int]) -> Int {
    return multiplyArrayAux(a, index: a.count - 1)
}

func multiplyArrayAux(a: [Int], index i: Int) -> Int {
    if i < 0 {
        return 1
    } else {
        return a[i] * multiplyArrayAux(a, index: i - 1)
    }
}

You have a similar solution? Great! Maybe your multiplyAux has 3 arguments, like sumArrayAux above. No worries, it is fine. My solution only shows you how you can reduce the number of arguments in an elegant way, by reversing the way you iterate over the array.

Let’s move to the next level

You cut your teeth at functional programming. Let’s try something harder now. What about writing a Fibonacci implementation?

Hold on. This code should work for big numbers such as 1000. If you run fibo(1000), your function should return instantly. Otherwise, you need to improve your model.

For example, this implementation:

func fibo(n: Int) -> Int {
    if n == 0 {
        return 0
    } else if n == 1 {
        return 1
    } else {
        return fibo(n - 1) + fibo(n - 2)
    }
}

is totally correct. However, your function has a 2**n complexity, which is pretty terrible. Following our paradigm, your function should have a n complexity.


Here is my solution:

func fibo(n: Int) -> Int64 {
    if n == 0 {
        return 0
    } else if n == 1 {
        return 1
    } else {
        return fiboAux(2, iteration: n, oldestPredecessor: fibo(0), predecessor: fibo(1))
    }
}

func fiboAux(i: Int, iteration n: Int, oldestPredecessor a: Int64, predecessor b: Int64) -> Int64 {
    if i == n {
        return a + b
    } else {
        return fiboAux(i + 1, iteration: n, oldestPredecessor: b, predecessor: a + b)
    }
}

Do not worry if you do not understand that solution instantly. It is a quite complex code. You may need to spend an extra time on it, in order to plenty get it.

Lazy programming

To end that article, I am going to show you one of the benefits of functional programming.

I have recently learnt Swift. Swift provides a lazy keyword (which can be found in other languages, it did not invent that concept). A lazy variable is initialized once you really need it. While there is no reason to use that variable, no memory allocation will be done.

Another example of lazy programming is the Active Record Object coming from Rails. Using it, you can perform different requests such as where, order_by etc. Actually, when using those methods, Rails does not compute anything instantly. It only stashes these requests somewhere, and flagged them as pending. When the developer really needs to use those data, Rails computes them.

This behavior could be really useful. Firstly, suppose you never use those data. It will save useless computations. Another one: imagine you sort your data first, then filter them. It would be smarter to apply this filter first and then sort it. Again, you will save extra computations.

This process is called lazy programming. It is super interesting when manipulating huge volumes of data. Nevertheless, if you are dealing with small amounts, you are less efficient. Indeed, lazy programming implies extra computations for tracking all the pending operations. It is a matter of compromises.

For instance, let’s use that multiplyArray we wrote before. Suppose you have a zero, somewhere, in that array. The final outcome is zero, of course. So if you do all the computations in a “dumb” way, you are not efficient. It would be clever to avoid these extra computations if there is any zero.

In order to be lazy, we need to delay the computations. For that, instead of multiply the elements right now, we are going to wrap them into functions which will be run later, when needed:

func multiplyArray(a: [Int]) -> Int {
    return multiplyArrayAux(a, index: 0, size: a.count)()
}

func multiplyArrayAux(a: [Int], index i: Int, size n: Int) -> (() -> Int) {
    if i == n {
        return { return 1 }
    } else {
        return { return a[i] * multiplyArrayAux(a, index: i + 1, size: n)() }
    }
}

Have you seen that? Until that statement in multiplyArray, no computation is performed within multiplyArrayAux. I only delay it, by wrapping my multiplication into a function. We call that mechanism, freezing. It is similar to a fridge: when you are back from the supermarket, you store your groceries into your fridge. You do not use them just after, only when you really need them.

As soon as I “unwrap” that function (by calling it), the system multiplies the elements.

Well, what about saving computations? Hold on folks, we are almost done. For saving computations we need to split our method into two behaviors: if we have encountered a zero while iterating (aka no operation), and the regular process (multiplying).

func multiplyArray(a: [Int]) -> Int {
    return multiplyArrayAux(a, index: 0, size: a.count).operation()
}

func multiplyArrayAux(a: [Int], index i: Int, size n: Int) -> (hasZero: Bool, operation: (() -> Int)) {
    if i == n { // We are done
        return (hasZero: false, operation: { return 1 })
    } else {
        if a[i] == 0 { // Oh, a zero!
            return (hasZero: true, operation: { return 0 })
        } else {
            let t = multiplyArrayAux(a, index: i + 1, size: n)

            if t.hasZero { // A zero has been seen somewhere
              return (hasZero: true, t.operation)
            } else { // Default behavior
              return (hasZero: false, { return a[i] * t.operation() })
            }
        }
    }
}

Here we go! If there is any zero in a huge array, my function will return very quickly, unlike the previous functions we wrote.

Here, I cheated a little bit as I have a let declaration. However, it could be removed and I would call multiplyArrayAux twice. This would be the pure functional way. However, I wanted to show you how you should mix different ways of coding. You should not only follow a single paradigm but use the best parts of them and produce an incredible code!

Conclusion

This post gives you a great overview of the functional paradigm. If you have any question, feel free to post a comment below.

To conclude, I listed the pros and cons of that way of coding:

Pros

  • With pure functions, you can speed compilation up. Indeed, as the result is always the same, the compiler can swap instructions. The execution order does not matter.
  • Pure functions help saving memory. The only memory allocation you have comes from the stack. It could you be really useful if you have memory constraints.
  • Lazy programming is easier using first class functions.

Cons

  • Coding as a pure functional way may be wearisome.
  • Functional code is often longer than imperative one, especially when iterating over collections. Also, the code tends to be less maintainable.