A Functional Explanation: A Different Point of View on Reduce and Fold

Imagine you're trying to describe how skyscrapers are built to your friend. (Also imagine you have only a very limited idea about the actual process of building skyscrapers.) You tell him:

At the start you need to put down the foundations. And after that you just keep adding floors on top of each other. Simple!

Of course, the actual building process will change floor-by-floor depending on the purpose of the given floor. An office floor will be different to a floor with a restaurant. That is why the workers will come to you, the construction manager, when they're just about to start building another floor and ask whether it should be a restaurant, or an office, or a gym — and then they'll proceed accordingly. No big mirrors at the walls in the offices, please!

Unknowingly, you've just exactly described the way reduce works.¹

From the three staple higher-order functions — map, filter, and reduce— reduce is the most powerful, but often also the most misunderstood. Let's untangle the mystery in a way that's understandable by Javascript and Haskell programmers alike.

This is the first post in the series A functional explanation in which I aim to explain useful functional programming concepts from an unconventional point of view. I lead a functional programming class and many of the ideas came to me organically during teaching.

Reducing, or building?

The idea behind reduce is very simple. Some things, like skyscrapers in our example, can be built iteratively by repeating many simple steps that are similar to each other. A reduce allows you to build such things simply by providing the bare minimum that is needed for the construction:

1. What are you starting with. In our case, the foundations of the skyscraper.
2. How does the build step look like. For us it's “add a floor to the current intermediate skyscraper” — the exact process depending on which type of floor we should be building.
3. What is the building plan, or sometimes what are the building blocks. In the case of skyscrapers, the list of floors with their associated types, like “a restaurant” or “an office”.

That's it. Reduce iteratively executes our build step, using it to add floors to the intermediate skyscraper according to the building plan. The building process stops when there's nothing left in the building plan.

The legendary Tower Bloxx in which you build a skyscraper by dropping blocks on top of each other. The sole source of my skyscraper-building knowledge.

If you think about it, this concept is very general — a lot of things can be built iteratively in small steps.² This means that understanding reduce can come in handy in lots of real-world situations! Let's see some examples in the next section.

Once you see it…

Ever summed a list of numbers? Well, isn't that really just a way of building a number according to a list of instructions?

• Foundation = 0
• Building blocks = a list of numbers to sum
• Build step = add a number from the list of building blocks (the “current floor”) to the intermediate result we have (the skyscraper that is being built)

Repeat iteratively, and bam! you have yourself a sum. Ditto with a product, or a concatenation of a list of strings. This is where reduce got its name — you are reducing a list of elements to a single summarised value.

What about filtering an array of elements according to some predicate, keeping only those for which the predicate returns true?

• You're building an array, starting from an empty one
• The building blocks are the elements in the input array
• The build step consists of either adding the current element (the floor you're about to build) to the intermediate result (the skyscraper), or doing absolutely nothing (…and moving on to the next floor)

To move away from toy examples — a web server could be seen as one big reducing operation, too. Do you have some inner state that you change according to a stream of incoming requests? Sounds like a reduce to me! Sure, it seems weirdly esoteric to be talking about “building the inner state”, but from a certain point of view, you're doing exactly that. The building plan consists of the incoming requests. And the functions stating what exactly should happen to the inner state when you receive a certain request together describe the build step.

Hopefully reduce makes more sense now, as an operation used for iteratively building things by describing how one build step looks like. Before we tell you how you can use it in practice, let's look at the last missing piece of puzzle.

The implementation

Let's explore how reduce might be implemented; let's start with the type. It takes two to tango, and it takes three to build a skyscraper: the foundation, the build plan, and the build step. Thus, areduce specialised for skyscraper building would have a type like:

reduce(
   floorTypes: List of Floor Types,
   buildStep: 
     (currentFloor: Floor Type, intermediate: Skyscraper) 
      => bigger Skyscraper,
   foundation: a very very small Skyscraper, 
): Skyscraper

Of course, we have seen that reduce is much more general, so we probably shouldn't specialise the types for skyscrapers only. A more general type would look like more like the following:

reduce<Block, Thing>(
   buildingBlocks: List of Blocks,
   buildStep: (current: Block, intermediate: Thing) => next Thing,
   initialValue: some initial Thing, 
): Thing

That's very similar to its type in Typescript! And even in Haskell we can now see the similarities between our version of reduceand their foldr :

                        build step  foundation    result
                       vvvvvvvvvvvv     v           v
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
                                             ^^^
                                   a "list" of building blocks

Of course, Haskellers have gone the extra mile and allow us to provide the building blocks in any reasonable collection t — not only a list, but an array, a set, or more generally anything that implements the Foldable “interface”.

Anyway, now that we have the type, how would the implementation look like? You could probably piece it together yourself. In pseudocode:

function reduce(buildingBlocks, buildStep, initialValue):
  intermediateResult = initialValue
  for block in buildingBlocks:
    # Place one block on the current structure
    intermediateResult = buildStep(block, intermediateResult)
  # We ran out of building blocks, it's time to...
  return intermediateResult

One less functional concept to worry about.

Conclusion

As you've learned, a useful way to seereduce is to see it as a function that enables you to build things. You provide a set of building blocks, describe what one build step looks like, and what foundation are you building on, and reduce takes care of the rest. In particular, it goes through all the building blocks you provided, adding them to the intermediate building by using the provided build step function.

This concept is so general that it encompasses most things that we do in day-to-day programming, from summing numbers to building web servers. Does it mean that you should use reduce for everything? Please don't, especially if you're not writing Haskell. Most common use cases already have a dedicated function, like map or filter or sum, and most uncommon complex use-cases are better served with a for loop and helper functions.

In the in-between cases, you will get to use reduce, and you will definitely see it in a codebase, so it is nice you now have an intuitive understanding of how it works. Even more so in Haskell, wherefoldr and foldl are popular alternatives to writing the recursion explicitly and manually.

One less functional concept to worry about — and you have to admit, it doesn't look quite as complicated now. Wait until you learn it's like this will most of the other functional concepts, too. But more on that later; stay tuned for the next post in the series A Functional Explanation.

¹ A fold is just a different name for a reducing operation. This name can be seen in Haskell, Purescript, and other functional languages.

² Actually, if you try hard enough — not that you should try—most loops and recursive functions can be written using reduce.