Myth of the Day: Functional Programmers Don’t Use Loops

An oft-repeated myth is that functional programmers don't use loops; they use recursion instead.

The origin of this myth is probably bad teaching material and/or bad teachers. Regular Joe attended a course in functional programming in university, where he was taught to re-implement filter using recursion. Since that introductory course just has to have made Joe an expert on functional programming, he will tell others that functional programming uses recursion, not loops. That's what the course taught him, so it has to be true, right?

Well, no. Sorry, Joe. Your experience does not reflect what real functional code looks like. But since you've arrived here, I'm happy to tell you that you'll learn something about real-world functional programming today!

In 10 minutes, I aim to convince you that Joe is wrong and the myth is false. In order to do this, I will present several procedural loops and show you their functional equivalents. Keep in mind that these are just some examples; there are plenty more.

Warning: to be able to do the side-by-side comparisons, this page is wide and will probably trigger horizontal scrolling on smaller devices.

What Is a Loop?

Before we do anything else, I want to establish a common ground. We need to agree on what a loop is. In this post, I will define a loop as a bit of code that executes several times to either compute a value or produce an effect. I will only show you loops that compute values, because as it turns out, they can be used to produce effects as well. *

Comparisons (part 1)

We start off with two easy ones, and one really cool one! These three are the classical examples Joe has probably already seen, but not paid too much attention to.

 filtered = []; for (elem in collection) { if (predicate(elem)) { filtered += elem; } } filtered = filter(predicate, elem); modified = []; for (elem in collection) { modified += transform(elem); } modified = map(transform, collection); result = start; for (elem in collection) { result = operation(result, elem); } result = foldLeft(operation, start, collection);

What you might not realise is that this third type of loop is really powerful. The fold can be used to do anything you can do with an ordinary foreach loop in a procedural setting. The difference is that instead of using mutable variables to implicitly store intermediary results, each iteration gets the intermediary results passed to it as an explicit function argument.

I'll repeat that emphasis: The fold is equal in power to a normal foreach loop. The two are basically the same thing, except one is pure and the other isn't. If this isn't proof enough that there are loops in functional programming, I don't know what is. But have some more comparisons anyway!

Comparisons (part 2)

Two of the following ones are obvious (and make you wonder why they aren't more common in procedural languages as well) while one is not as obvious, but on the other hand very convenient.

 adults = true; for (person in group) { if (minor(person)) { adults = false; break; } } adults = not(any(minor, group)); number = ""; for (digit in digits) { number += toString(digit); } number = foldMap(toString, digits); while (true) { compute(read_stdin()); } forever(read_stdin >> compute);

The only one that might need some explaining is foldMap. The reason it works is that there's a Concatenable interface, which strings implement. The foldMap loop works only when the mapping function (in this case toString) produces a Concatenable item which it will then concatenate. There are similar loops for other very common interfaces.

It might seem odd that I even mention forever, but I do because it shows something important – when you are allowed to create loops with ordinary functions, you can afford to make some aliases just for legibility. It's just a function anyway, so if someone is bothered by it, they don't have to use it.

Comparisons (part 3)

The final two examples are probably my favourites in this post.

 bestPaid = employees[0]; for (employee in employees[1:]) { if (salary(employee) > salary(bestPaid)) { bestPaid = employee; } } bestPaid = maximumBy(comparing(salary), employees);

What this does is probably obvious – it finds the employee with the highest salary. What makes the functional version of this so good is that it combines two very neat concepts – first, the comparing function, which modifies another function to produce Comparable return values. The second is the maximumBy loop which expects a function that yields Comparable values and then compares those values to find the highest.

By combining these two things, we've turned a pretty hairy loop into a single very readable function call.