Don’t pay the for-loop tax

Note: this post was originally published on my Medium profile

Once, when doing code review on a TypeScript project at my work, I came across several instances when a colleague of mine used a for loop, even though it wasn’t necessary (i.e. a more readable declarative equivalent was available). In a joke I stated that we should impose a “for-loop tax for every loop used unnecessarily.
It made me think however, why so many people tend to go for the longer and more error prone solution with the loop and I got to the following conclusion: Nearly every (mainly) imperative programming language course/book I ever took/read (be it Pascal and C# in high school or C/C++ and Wolfram Mathematica in college) contained a section like

“These are the loops available, this is how you write them and this is how you use them to solve these basic problems”.

There is an important point to note here: they only teach how to write a loop but scarcely explain why you would need one (or sometimes even worse they state that loop based solutions are the best ones). For future reference, I decided to write this “cookbook of the main types of situations where loops are often used and how they can be replaced. All the examples will be written using JavaScript as it is very popular, but the rationales behind the examples can be used in many other languages as well.

#1: I need to go over an array and get a single value as a result

We start with the simplest of problems:

Given an array of numbers, return the sum of its elements.

const sum = (array) => {
    let result = 0;
    for (let i = 0; i < array.length; i++) {
        result += array[i];
    }
    return result;
}

const numbers = [5, 25, 8, 18];
console.log(sum(numbers)); // logs 56

If you attended similar courses as me, you surely recognise this code. Create a temporary variable, initialise it with zero and using a for loop iterate over the array returning the final value of the variable. There are some problems though:
For something as simple as a sum of an array, 7 lines of code seem quite a lot.
You must handle the bounds of the iteration yourself. In other words you must know to start at zero (in JavaScript, many other languages have 1-based arrays – Wolfram Mathematica for example) and end at i that is strictly less than the length of the array (not less than or equal). This is prone to errors especially if your work in many languages at the same time.

const sum = (array) => array.reduce(
  (total, current) => total + current,
  0);

const numbers = [5, 25, 8, 18];
console.log(sum(numbers)); // logs 56

The solution that remedies both those problems is to use the reduce function (in other languages also called fold or aggregate). In a single expression we iterate over each of the array elements adding them together (stating the sum’s default and initial value is zero). Notice there is no mention of the iteration bounds, it just guarantees that it will go over all the elements from first to last.

#2: I need to create a new array from a given one and transform all the elements

This is another common problem, let’s illustrate it with this example:

Given the array of prices, return a new array with the prices n % lower.

const discount = (originalPrices, discountAmount) => {
    const multiplier = 1 - discountAmount;
    // we must clone the array
    let result = new Array(originalPrices);
    for (let i = 0; i < originalPrices.length; i++) {
        result[i] = originalPrices[i] * multiplier;
    }
    return result;
}

const prices = [5, 25, 8, 18];
console.log(discount(prices, 0.2)); //logs [ 4, 20, 6.4, 14.4 ]

The loop-based way to do this is pretty similar to the sum code. There is one additional problem though: in order to not destroy the input array, we must clone it first and then transform the values in the new array. This can easily be forgotten introducing a potentially unwanted side effect in the application.

const discount = (originalPrices, discountAmount) => {
    const multiplier = 1 - discountAmount;
    return originalPrices.map(price => price * multiplier);
}

const prices = [5, 25, 8, 18];
console.log(discount(prices, 0.2)); // logs [ 4, 20, 6.4, 14.4 ]

The cloning problem can be avoided altogether using the map function. For a given array it returns a new array where each element is the corresponding element in the original array transformed using the provided function (in our case multiplied by the discount multiplier).

#3: I need the numbers from m to n

Another common situation where loops are used is when generating linear ranges as an input for further transformations. A classic example is:

Return an array of the first n squares

const squaresBad = (n) => {
    let result = [];
    for (let i = 1; i <= n; i++) {
        result.push(i * i);
    }
    return result;
}

const squares = (n) => {
    let result = new Array(n);
    for (let i = 1; i <= n; i++) {
        result[i - 1] = i * i;
    }
    return result;
}

console.log(squaresBad(5)); // logs [ 1, 4, 9, 16, 25 ]
console.log(squares(5)); // logs [ 1, 4, 9, 16, 25 ]

This is a problem that can be solved very badly when using loops. The first naïve solution suffers from the problem that it pushes a new element to an array every iteration. This expands the array and may cause it to reallocate in memory being slow (benchmark).
The second approach instantiates the array of correct size beforehand avoiding this problem, but we can easily make a mistake when assigning the current value (see the result[i – 1] expression in the second for-loop).

const range = require("lodash.range")
const squaresLodash = (n) => range(1, n + 1).map(
    (n) => n * n);

const squares = (n) => [...Array(n).keys()].map(
    (n) => (n + 1) * (n + 1));

console.log(squaresLodash(5)); // logs [ 1, 4, 9, 16, 25 ]
console.log(squares(5)); // logs [ 1, 4, 9, 16, 25 ]

While there is no native way to generate a range of integers in JavaScript there are two ways to tackle this problem in a more declarative ways with map: using the lodash.range function, or a clever ES2015 syntax trick (source).

#4: I need to do something with side effects n times

The final use case of loop I want to discus here is invoking a method with side effects more than once. As Edsger Dijkstra famously said:

Two or more, use a for

The simplest example to illustrate this case is:

Console.log the string “Hello world n times

This is in my opinion the only justifiable use case for loops in JavaScript (not counting infinite loops) as it is the most concise and performant way (at least until Tail Call Optimisation arrives to most environments).
However, I would strongly recommend to abstract this into a helper function to restrict the loop to a single place.

const doNTimesLoop = (n, f) => {
    for (let i = 1; i <= n; i++) {
        f(i);
    }
}

const doNTimesRec = (n, f) => {
    const body = (m) => {
        if (m > n) return;
        f(m);
        return body(m + 1);
    }

    return body(1);
}

//both log "Hello world" five times
doNTimesLoop(5, x => console.log("Hello world"));
doNTimesRec(5, x => console.log("Hello world"));

As we can see in the examples (both calling the provided function with numbers from 1 to n), the iterative version is shorter and simpler to write. Also the “loop-free version would cause a stack overflow on environments without Tail Call Optimisation.

Conclusion

On four elementary situations, we described how to use declarative style to replace loops and therefore make our code shorter and less error-prone.
Do you use loops? Do you disagree with any of the solutions? Comment please!

Comments

[pew pew rainbows an shit fuck yea]

A wise man once said "never do the talking when jsperf exists and can do the talking for you"

The abstraction is pretty, but the for loop is orders-of-magnitude faster.

jsperf.com/old-man-yells-at-clouds...

[Adrian B.G.]

Basically the advice is learn some Functional Programming 😎.

[Dan Homola]

Many people are afraid of the term, but you are absolutely right 😁

[Martin G. Brown]

While i generally agree with this article's advice, far too often I've seen code like this:

const numbers = [5, 25, 8, 18];
console.log(sum(numbers));
console.log(avg(numbers));
console.log(min(numbers));
console.log(max(numbers));

With loops the fact the code is parsing the array four times would be more obvious. And to my mind easier to fix.

PS: Interesting fact, it is quicker to loop from a large number to zero than zero to the large number. This is because CPUs have a jump if not zero (JNZ) command that eliminates the comparison each iteration of the loop.

[Lluís Josep Martínez]

Let's say you have to build a nightly batch process to process milions of entities (orders, invoices, bank transactions ... whatever). A typical approach would be to open a result set (or the equivalent structure in JS) to process the entities one by one and do partial commits. With a functional approach, will you read the milions of entities into an array just to use map/filter/reduce ? I hope your server has some Gigabytes of contiguous memory free, otherwise it wil fail miserably. The optimal solution will use a loop.

[Dan Homola]

Well, I would use streams and their on method which IMO resembles the functional approach...

[Lluís Josep Martínez]

Do you mean in JS or Java? Because in Java doing it the functional way is extremely complex according to stackoverflow.com/questions/322092...

Do you have a JS example that reads rows from a relational DB without using loops?

[Dan Homola]

I meant JavaScript. An example could be Google Lovefield (haven't tried it though).

[Lluís Josep Martínez]

By looking at the Readme, it seems like this API returns an array of rows. Which obviously is not acceptable when dealing with huge result sets.

}).then(function(results) {
// The SELECT query's Promise will return array of rows selected.
// If there were no rows, the array will be empty.

results.forEach(function(row) {
// Use column name to directly dereference the columns from a row.
console.log(row['description'], 'before', row['deadline']);
});
});

[Eduardo]

That is what a Java developer said 5 years ago about scala and clojure. There is a wave of functional languages. You eaven have lambdas now in c++, c# and java.
I don't think we will be throwing our macs and start using lisp machines, but with webassembly just around the corner, who knows in what kind of language we will be programming in five years.
I never expected to be programming a backend in javascript, but it turns out to be very eficient and stable.
All I say is keep your mind open and learn the best practices for each language and paradigm. And what is old today, might be new next year. Server side javascript was the new new in the 90, it hit the mainstream with node.

[Florido Paganelli]

Three things, probably motivated by the fact that I am old:
1) readability is important, since I am old school I can't quite read this code even though I understand the functional approach (but not much the declarative)
2) The benchmark shows the problem seems to be the for implementation in JavaScript. But somebody else said the for loop is just pushed somewhere else in the libs. The point is that this is language dependent, JavaScript is what it is, there's no optimization of you use old-school coding. I mean, it's not for loops per se, it's the way these are implemented by the interpreter
3) relying on an interpreter feature like tail call "optimisation" (why would you call it like that?) It's to mess bad as relying on the C++ preprocessor that makes code ubdebuggable. But ok we're talking optimization here. Practical optimization is ugly and for a restricted group of people, let's face it.
In other words, I don't consider this nice coding.

Thanks for the article anyway, might come handy :) if you can give pointers to why the benchmarks show up like that it would be cool!

[Dan Homola]

Thank you for your comment. To your points:

Ad 1)
I think it is only a question of getting used to it, as you say :)

Ad 2)
I'm no JavaScript engines expert, but people seem to argue, that calling a function is expensive (I'm not so sure about this argument, however I can't disprove it) and for cycles can be optimised better (for example unrolled).

Ad 3)
It does not rely on Tail Calls, my argument was merely that map & co. do not necessarily need to be implemented using cycles but for example using recursion (that would indeed need proper tail calls to avoid stack overflow).

The reason I call it optimisation is my college professor in the Runtime systems course called it that. We implemented a garbage-collected byte code language there, in my case it was a subset of Scheme, and one of the requirements (if you chose functional language) was "infinite" recursion. You can handle tail calls naïvely and overflow the stack or properly recycle the stack frames and be able to run "forever". That's why even the compat-table calls it "proper tail calls (tail call optimisation)".

The important point here is that this is an optimisation of the runtime itself, not an optimisation of the program being run.

I hope this helps to clarify things :)

[Matt]

Have to say I disagree. I think this is a matter of style.

• The whole purpose of a function (typically) is to 'abstract out' a collection of logic into a more general, broad operation. Like your first example, if you want a function to sum elements in an array but the language doesn't have that function, you write it. Whether you use a loop at that point or use a function that abstracts out the logic of a loop is your choice, at the end of the day your abstracting the entire job of computing the sum or elements into a single function anyway.
• I like working with C and thinking about a program closer to the way that it is actually being run on a lower level. When I see the iterative sum function in your first example, I tend to actually conceptualize a block of memory and think of the need to iterate over that memory in order to make use of each piece of memory. Seeing something like "array.reduce" means I need to go off to consult an api and figure out what this function is and how to use it, and there could be nuances of the function that I want to know about - like if I had wanted something that iterates over an array but can also increase the size of the array in the process of iteration or something like that. With a loop, the possibilities and limitations are more obvious.
• that said there can be something nice about not using iterators. I remember this from working with matlab, where you can write computations in terms of matrices, which naively looked like they would be really inefficient computations, but which matlab could somehow work with to compute quickly.

[Sami Pietikäinen]

To think that manual for-loops are always faster than functional approach is a misconception. For instance in Rust using iterators and functions like map and filter are in fact as fast or even faster than manually implemented loops: doc.rust-lang.org/book/second-edit...

It's called zero-cost abstraction: you can write high level functional code and still get similar performance as manually implemented low level code.

I wouldn't be surprised if this is the case with other languages as well since modern compilers and interpreters are really good at optimizing.

[Lluís Josep Martínez]

For something as simple as a sum of an array, 7 lines of code seem quite a lot.

In your example it's 7 lines vs 4 lines (a gain of 3 lines, impressive). In a real work example the function could easily be 50 lines of code vs 47 lines of the functional approach, being gain still 3.

You must handle the bounds of the iteration yourself

In JS yes, not in Python:

for number in array :
...

[Alan Languirand]

I 100% agree with mantra here, but I'd like to add to the examples. For me, the functional style/indirection in these examples IS the value, and once you're doing things in a functional way you've already captured most of the technique's purpose. For me, whether you continue to use a declarative iterator or a for loop inside your abstraction is less important.

Here's an admittedly naive example of the price discounting that I think very clearly shows the difference between a for loop and an Array.forEach.

let prices = [5, 25, 8, 18];
let discount = 1 - 0.2;

// more imperative
for (let i = 0; i < prices.length; i++) {
    console.log(prices[i] * discount)
};

// more declarative
prices.forEach((price) => {
  console.log(price * discount);
});

Just reading these aloud to yourself shows the difference in clarity:

"For when i equals zero and i is less than the length of prices while incrementing i, console log prices at position i times discount."

vs.

"Prices: for each price, console log price times discount".

When moving from an imperative to declarative style, the code turns from near gibberish to an honestly comprehensible English sentence. I think that's a win for the whole team at every skill level, and the value this style is attempting to capture.

[Kasey Speakman]

I could not agree more with this article. A map, filter, or reduce tells me what is going on without looking too deeply at the code. A for loop requires a careful eye to make sure you don't miss a side effect when you refactor something. The performance difference for most cases hardly compares to the maintenance benefits.

[rrackiewicz]

Anyone using a for loop instead of a functional programming construct is not being daft. The issue is that they haven't gone through the process of fully learning FP. I dare say that you will find other issue related to this in ALL of their code.

[Asim Mittal]

Its funny that JS devs should talk about "tax" on something as basic and primitive as a for loop.

Almost anyone working in the JS ecosystem is transpiling code. Its one of the only systems in which the resulting code has a larger footprint than the original. If you picked up a compiled language, the resulting byte code is leaner.

So of all things you pay a "tax" on, the loops are the last thing you should worry about.

Secondly, reduce, map and such others only give you an impression that you're writing lesser code. Internally these constructs also implement themselves as loops.

Most of JS is now about programmers perceived convenience. A lot of things you end up doing is actually more complex when you look under the hood

[Adam Brandizzi]

The for(;;) construct is error-prone but I feel "going functional" in JavaScript is hardly a good solution.

Take for example the sum() function from the post. In Haskell, it would be defined this way:

sum' l = foldl (+) 0 l

Or here it is in Scheme:

(use-modules (srfi srfi-1))
(define (sum l)
    (fold + 0 l))

The sum' function is quite concise because the (+) operator is already a function. Even Python (where such a function would be frowned upon) could make it clearer:

import operator
from functools import reduce

def sum(l):
    return reduce(operator.add, l)

So, when we go to JavaScript, we got this very weird line (total, current) => total + current, where there is a total, and a current, and they are added up. Now I have a bit more to understand here. The for(;;) loop is brittle, but why not this?

const sum = (array) => {
    let result = 0;
    for (let i in array) {
        result += array[i];
    }
    return result;
}

Or, better, this?

const sum = (array) => {
    let result = 0;
    for (let v of array) {
        result += v;
    }
    return result;
}

There is a mutable variable but it is clearer what is going on. The JavaScript syntax is helping me here. Do you disagree?

I find trying to optimize for sum() functions problematic. sum() is a solved problem, whatever the solution you choose. But get another code where one calls, let us say, map() inside the function given to reduce(). It is surprising confusing. Given the trend to avoid naming functions in JS, it will become a mess.

Also, many functional patterns are helpful in functional languages, or specific situations, but not in all places. Many JS programmers write apply(compose(fn1, fn2.bind(arg)), value) because they think it is as good as f1 . (f2 arg) $ value. But is it? I don't think so. JavaScript didn't make this construction clear, as Haskell did.

Functional patterns make sense a lot of times. If you have an algorithm which can be reused except for one part, it will be great to pass the function (instead of, let us say, a Strategy pattern house-of-cards). Functions as values are a cornerstone for asynchronous code. I even like the each()/forEach() methods, so I do not have to discover if it uses a[0], a.get(0), a.item(0).

However, in general, a "more functional" JavaScript code will not be better than one that uses some loops. Trying to get better code by being "more functional" is very much like improving by being "more OO." And we know the result: how many Command pattern instances we found that should have been a function?

Now I wonder the same about lambdas that could be a for(of) block.

[Dan Homola]

Thanks for the reply, it is an interesting view. While I understand that the for..of cycles remedy some of the problems I have with cycles, I still prefer the reduce.

I admit that for something so simple as a sum there is a little advantage, but this was chosen as an illustration for the problem exactly for the simplicity of the problem.

What I wholeheartedly agree with you on is that the all the operators (including the function call operator) in JavaScript should be functions as well.

[Tomas Rehak]

Yeah but for instance in Java, for-loop is considerably faster than any other approach.