Entropic Thoughts

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

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.

success = null;
for (downloaded in downloads) {
    if (downloaded != null) {
        success = downloaded;
        break;
    }
}
success = asum(downloaded);

The asum loop, like foldMap, uses an interface – let's call it Alternative. Our downloads list contains a bunch of nullable values (which implement Alternative), and asum knows how to loop through a collection to find the first non-nullish value.

Closing Thoughts

As we've seen, there are very many different loops. Some of them are highly specialised to do just one thing, while most exist in a general version, which is specialised by passing functions to it that modify its behaviour. The idea in functional programming is that if you only have one or two loops to do every task (like you do in many procedural languages), your code will be harder to read and you will be writing a lot of boilerplate over and over.

Of course recursion appears in functional code, just like it does in procedural code. Generally though, recursion is considered by many a fairly low-level approach. If there exists a loop to do what you want, many people much rather use that because it increases readability of the code.

I'm expecting some criticism because the examples are very simple. Let me put it like this: complicated loops will be complicated loops. I can't promise you a magic function that will turn your 100-line monster into a single line of beauty. There's no secret sauce when it comes to complicated logic, which is why we programmers get paid as much as we do.

What I can promise you is that all of those simple boilerplate loops you read and write dozens of every day in a procedural language – those that you barely even notice anymore – those could be greatly simplified if more specialised loops existed in the language. All of the loops I've mentioned are of the kind where if you get used to them, you'll smack yourself in the forehead every time you can't use them because your language doesn't encourage it.