Asymptotically Typeable

Home Blog RSS

A Case for For Loops

Sun, 20 Jun 2021

I do not like for loops. I think for loops should not be the first tool developers reach for when they wish to loop. If you have the chance to use map, filter, or reduce, and if your host language is capable of fusing them, then it's always[source?] more readable to sequence them.

But I think I found a case where for loops really are the most elegant solution.

To illustrate this scenario imagine we were asked to find the prime numbers in a list of the first n fibonacci numbers. Next, we were asked to find the square numbers in the same list of n fibonacci numbers. In fact we were asked by some fibonacci-obsessed mathematician; in other words we will be computing fibonacci numbers a lot. So it's sensible to imagine some function int[] firstNFibonacci(int n) defined somewhere.

However, this fibonacci-crazed odd-ball is of course interested in rare properties of fibonacci numbers; which means that, of the n numbers computed, hardly any will remain. So it's a waste of time (and mostly space) to construct a list of size n and to loop over it once to populate it with fibonacci numbers, then loop over it again to keep the interesting ones.

It's obviously better if firstNFibonacci can yield the number once it was computed to the filtering logic before carrying on computing the second. For the sake of generality I will assume your host language does not have a yield keyword (nor a synonym). So we'll have to simulate yielding. The way I choose to do it is to include the state of the computation as an argument (so the function can carry on where it left off), and to include the next state in the output of the function (so the caller can chain these next states and make progress).

Here is an example:
type state = (int, int, int);
 
(int, state) firstNFibonacci(int n, state s) {
    int found = s[0], a = s[1], b = s[2];
    return found < n
         ? (a+b, (found+1, b, a+b))
         : (-1, s); // -1 indicates end of computation
}

The question now is, how do we use this iterator correctly? Here are three ways of finding the prime fibonacci numbers. I will let you judge which is completely correct.

state s = (0, 0, 1); // (none found, first fib., second fib.)
int n = 1000;
var result = firstNFibonacci(n, s);
while (result[0] > -1) {
    if (is_prime(result[0])) print(result[0]);
    result = firstNFibonacci(n, result[1]);
}
state s = (0, 0, 1); // (none found, first fib., second fib.)
int n = 1000;
var result, value;
do {
    result = firstNFibonacci(n, s);
    value = result[0];
    s = result[1];
    if (is_prime(value)) print(value);
} while (value > -1);
state s = (0, 0, 1); // (none found, first fib., second fib.)
int n = 1000;
var result, value;
while (true) {
    result = firstNFibonacci(n, s);
    value = result[0];
    s = result[1];
    if (is_prime(value)) print(value);
    if (value > -1)      break;
}

What happens when n = 0? Will the first number always be considered? Will the last number always be considered? Will it halt? The (do)while loops above invite the reader to ask these questions. Questions whose answers are not obvious and therefore require a context switch in the head of the reader. (In fact the last two versions are not completely correct)

Now consider the for loop version
int n = 1000;
 
for ( var result = firstNFibonacci(n, (0, 0, 1))
    ; result[0] > -1
    ; result = firstNFibonacci(n, result[1]))
{    
    var value = result[0];
    if (is_prime(value)) print(value);
}

I consider this version elegant because it fits with the semantics of for loops perfectly. The first component is an initialization step, the second is a termination condition, and the third is the means of making progress.

In conclusion, like gotos, there seems to be sensible use cases for for loops. However I still believe that most of the time, for loops are not the tool for the job. This investigation made me wonder if this is the reason why languages like Java adopted the same for keyword for iterators instead of introducing a synonym. But that is a question for the historians.