JavaScript: Reducing the use of the For Loop

no for loops

We have reached the tipping point. In many (if not a majority) of our modern JavaScript use cases (particularly the application code) there is no need for the for loop. The workhorse of our programming toolbox and our optimization technique for primitive recursion should have seen its last day years ago. With a minimal investment in learning new techniques (or just deferring to these techniques) we can increase the readability of our code. Readable code is easier to understand, has fewer bugs and is easier to maintain.

Programs must be written for people to read, and only incidentally for machines to execute. [1]

The problem is the for loop requires to us interpret the code (in our personal organic supercomputers: our brains) to understand its intent. Typically we see for loops used for:

  • aggregating a list objects into a single object
  • transforming a list of objects into a list of different objects
  • decreasing the size of a list

But there are other concerns

  • side effects, such as the mutation of the original list
  • potential multiple responsibilities in that bit of code

For loops are the workhorses of list processing. But there are other options and by transitioning to a more declarative syntax and leveraging either the power of the JavaScript array object or similar list library code can become simpler and easier to read (with fewer bugs and easier to maintain).

Reduce: The ‘new’ basis of list processing

Reduce is a function which aggregates (or consolidates) a list into a single object. Implied is its need for a list but it also requires an initial value and some method of combining two elements into an aggregate which I call the reducing function.

We write a function that produces the sum of a list by writing something like this:

const add2 = (a,b) => a + b// using the array method
const sumList = list => list.reduce(add2, 0)
// using a list processing library
const sumList = list => reduce(add2, 0, list)
// in usage
const total = sumList(list)

When compared against the loop method we might see something like this

let total = 0 ;for(let i = 0; i < list.length; i++) {
total = total + list[i] ;
}

While the former method requires an understanding of the reduce function but once it is understood it is impossible for the output to be anything other than a single object. The latter requires us to run the bit of code in our mind. In this interpreter we need to keep a handle on what the variable total is holding as well as where we are in the iteration. This sample is trivial but could happen in many places inside of a code base.

An exercise that I found important in developing my understanding of reduce was implementing it. It is a fairly trivial function to write.

// ::  [a] -> a
const head = xs => xs[0]

// :: [a] -> [a]
const tail = xs => xs.slice(1)

// :: ( ((b,a) -> b), b, [a] ) -> b
const reduce = (f, agg, list) =>
(list.length == 0) ?
agg :
reduce(f, f(agg, head(list)), tail(list)) ;

Simply stated if the list doesn’t have any remaining elements return the aggregate agg, otherwise recurse with a new value of the aggregate agg (determined by applying the reducer function f to the current aggregate agg and the head of the list) and the remainder of the list (tail(list)).

The technique above is a type of recursion called primitive recursion. The implication of primitive recursion is that the implementation could be translated to a for loop (general recursion implies a while loop). Written in a for loop reduce would look like this:

// :: ( ((b,a) -> b), b, [a] ) -> b
const reduce = (f, agg, xs) => {
for(let i =0; i < xs.length; i++) {
agg = f(agg, xs[i])
}
return agg
}

The important part is that reduce is a well known function that consolidates a list of some type a into an object of some type b. We could implement the function in a recursive manner or imperatively with a loop.

Hindley-Milner

It is impossible not to notice the odd looking comments preceding each of the function definitions in the implementation of reduce. They are examples of Hindley-Milner type signatures which are derived from their work on type systems.

The signature defines what the expected input and output types of the function. Parametric polymorphism is a feature of statically typed languages that allow functions to be defined across different types and is often implemented as generics. While JavaScript is dynamically typed (as opposed to statically typed) we can stretch the concept of parametric polymorphism (without the corresponding compile checks). When dealing with generics we often define placeholder types — which is what we have done in the type signatures of the reduce implementation.

Briefly the signature for head is [a] -> a, which indicates the input of is a list of some type a and the output (after the last arrow) is an object of type a. Tail inputs a list and returns a list with the first element removed, so the signature is [a] -> [a]. Reduce is a it trickier in that is takes three parameters all at once: the reducer function (b, a) -> a, the initial value of the aggregate b and the list [a]. The output has the same type as the initial value of the aggregate, b.

Fantasy Land [2] provides a good explanation of the Hindley-Milner signature (they call it notation). When considering reduce and related functions it is helpful to consider their signatures to visualize their behaviors.

Beyond Reduce

There are a handful of functions that perform specific jobs that one might otherwise leverage a loop for. They carry implicit meanings that don’t require us to interpret a for loop to understand:

Reduce: As mentioned this consolidates/aggregates a list of objects of type A into a single object of type B. Type A and type B might be the same type (such as the case of adding integers) or they might be different types (such as the case where we are summing the total order amount with a list of line-item objects).

Map: Transforms a list of type A into a list of type B. The input list is of equal length to the output list.

Filter: Filters out objects from a list based on the result of passing each object to a predicate function provided by the coder. In this case the input list and output list are of the same type.

Find: Finds the first object in a list that passes a predicate. Here the output is an object of the same type contained within the input list.

By leveraging these functions as opposed to writing a custom for loop indicates the intent without requiring having to run the custom for loop through your interpreter (your mind).

Map, Filter, Find is really just Reduce “Snazzed Up”

All of these functions are (or can be) built on top of reduce by providing specialized reducing functions. Here are two examples to help solidify the relationship between functions on lists and reduce. First map:

// :: ([a], a) -> [a]
const append = (xs, x) => xs.concat([x])
// :: (a -> b) -> ([b], a) -> [b]
const transformingAppender = f =>
(agg, x) =>
append(agg, f(x))
// :: (a -> b) -> [a] -> [b]
const map = f => reduce(transformingAppender(f), [])

The majority of the work here is performed by the function transformingAppender. It is takes a function (f) and returns a function that satisfies the signature of the reducer function. The first input to transformingAppender is a (transformation) function that converts an input of type a to an output of type b. With this transformation function applied transformingAppender returns the reducer function which takes a list of type b (xs) and an object of type a (x). As you might guess the transformation function (f) is applied to the input x converting it from type a to type b before appending it to the list xs.

The second example is filter:

// :: (a -> Boolean) -> ([a], a) -> [a]
const conditionalAppender = f =>
(agg, x) =>
f(x) ?
append(agg, x) :
agg
// :: (a -> Boolean) -> [a] -> [a]
const filter = f => reduce(conditionalAppender(f), [])

Similar to map, filter has a majority of its work accomplished via a helper function conditionalAppender. Just like the helper in the definition of map, it needs to be seeded with a function but in this case it is a predicate which challenges whether the object x should be appended to the list xs.

Favor Readability over for-loop comfort

Favor readability by using functions that have well known implicit meanings. I focused on list processing functions based on reduce, however there are other conditions where well known functions are not leveraged en lieu of custom implementations that require us to interpret the code in our minds to understand what it is doing.

There may be conditions where the performance of our applications needs to be considered and we may want to accomplish multiple things within a loop. Many applications and runtimes have sufficient computational power to focus on readability over performance. Studies show the impact of readability could lead to a dramatic reduction in software maintenance costs code. That savings might be better spent on scaling compute than code optimizations. Consider your use case and leverage low level language features, like loops, when it is the best choice.

Disclaimer: Please don’t implement your own versions of reduce. My code examples are provided just for insight. If you decide to implement versions of these functions or anything recursively be aware of its limitations in the languages and frameworks you leverage. Long before it was a Q&A website StackOverflow was a well established exception one might see when recursion runs awry.

  1. Abelson & Sussman, Structure and Interpretation of Computer Programs, ISBN-13: 978–0262510875
  2. https://github.com/fantasyland/fantasy-land

A 25 year software industry veteran with a passion for functional programming, architecture, mentoring / team development, xp/agile and doing the right thing.