Why `xs.each(f)` should not be considered a "loop".

loops-are-evil.md

First and foremost, let's take a look at the following pieces of code. The first one is something you should be rather familiar with, and the second one is also a somewhat familiar idiom these days (at least in languages with higher-order functions):

// Example 1:
30 + 12

// Example 2:
xs.map(f)

Without knowing anything about the implementation of the + operator or the map method, besides that the first sums two numbers, and the latter provides a collection where every element is transformed by the given function, which one do you think is a loop? Think about why you think it's a loop and don't answer anything for now. Let's first look at the implementations of both functions:

// Example 1:
function successor(a) {
  return function() {
    return a;
  }
}
function predecessor(a) {
  return a();
}
var zero = function(){ };
operator +(a :: Number, b :: Number) {
  var result = a;
  while (b != zero) {
    result = successor(result);
    b = predecessor(b);
  }
  return result;
}


// Example 2:
function map(xs, f) {
  return xs.length === 0?  []
  :      /* otherwise */   [f(xs[0])].concat(map(xs.slice(1), f))
}

Now that we know how they are implemented, which of those examples are a loop? Did you change your mind? Did you maintain your reasoning? Before we answer which of those operations are a loop, let's review the concept of looping in computer science. With pictures. The following image describes a loop:

    +---->[ a ]-----+
    ^               |
    |               v
  [ d ]           [ b ]
    ^               |
    +-----[ c ]<----+

In this case, the computer performs the operations a, then b, then c, then d, then back to a. Effectively, the computer "loops" through the given set of operations. Possibly the observable effects in such a construct differ depending on the current state of the program — this is a common idiom in languages that have mutable state.

The most primitive form of constructing this "loop" is with the go to operator:

repeat:
  add %eax, 1
  sub %ecx, 1
  cmp %ecx, 0
  jne repeat

Imperative languages provide higher-level constructions for achieving these same effects, usually in the form of repeat, while, for, etc. What they all have in common is that they effectively perform a set of instructions, then go back and perform the same set of instructions. Over and over again, until an exit condition is met.

Now let's get back to our original example. I've asked whether 30 + 12 was a loop, and whether xs.map(f) was a loop. Then provided two implementations for them and asked the same question. The answer should be obvious now: none of those operations is a loop — although they might be implemented in terms of one.

Loops are a general purpose form of computation that tells you how the computation is performed. For our two examples, there is no such information, unless you pry on the internals and assume those will hold for every case — a bad thing to do. Thus, we do not reason about the computation 30 + 12 as a loop, nor do we reason about xs.map(f) as a loop. They have better mental models for us, poor humans, to understand. And an understanding of the computations is more important than the knowledge of how such computations are performed by a computer.

For example, you don't need a computer to be able to tell what the result of 30 + 12 is at a glance. Likewise, you don't need a computer to know that [1, 2, 3, 4].map(function(a){ return a * a }) is strictly equivalent to [1, 4, 9, 16]. It does not matter which order you perform these operations — in fact, you could perform them at the same time, and you would still achieve the same results. The same is not true for imperative loop constructs.

Furthermore, the strict ordering of operations in a program makes many clever compiler and library optimisations impossible. One can't just parallelise the construct xs.map(f), even though the conceptual model of the operation does not involve any ordering, if it is implemented as a loop construct. On the other hand, by leaving the details unspecified, not only our reasoning about the operation is improved, but the amount of optimisations that might be performed increase. A compiler would be able to automatically parallelise the whole operation, delay computations until they are absolutely necessary (which is a blessing for expensive computations), partially execute expensive operations at compile time, not perform unnecessary computations altogether, and many more.

So, let us ask once more the question: "should xs.each(f) be considered a loop"? No. This is an operation that applies a side-effect to every item in a collection. We don't have any exit condition, we just know that a side-effect will be applied to every item in the collection. We also do not know in which order such side-effects will be applied, we can't just assume that it will be applied from "left to right", since xs might be a collection with no concept of ordering (e.g.: Maps, Sets). For all we know, the side-effects could be applied in parallel — although here there could be major implications on the concurrent application of side-effects, which is not a problem when you have controlled effects and purity.

Sounds to me like the message is

Loops put a burden on the reader for determining whether order of execution is important, and whether and how data in one iteration of the loop depends on the actions of a previous iteration.
Strive to make these information more apparent by encapsulating the iteration in a function with a clearly defined interface, and using a higher-order function to describe the interaction between iterations.

Is that what you meant? Did I miss something?