Fold

Fold is a common higher-order function. You might also see it called “reduce” or “aggregate” or “accumulate”.

Fold is kind of like map, in that it takes a function and a list and applies the function to all the elements in the list. The difference is the output. Fold returns a single value, built up as the elements of the list are processed.

Here’s a simple example in Elm (try it!):

import Graphics.Element exposing (show)
import List exposing (foldl, foldr)

add x y =
    x + y

list = [1, 2, 3, 4, 5]

sum = foldr add 0 list

main =
    show sum

The printed output is 15.

Like map, fold is often used in declarative code where a loop might be used in imperative code. And when you get used to fold, you’ll often be able to write code that’s a little simpler than it might be with a loop.

Fold has another interesting property that map does not: Its result might depend on the order in which the elements of the list are processed.

With the addition function, the order doesn’t matter. Addition is associative. If we want to sum the list [1, 2, 3], we might add 1+2 first, and then that result + 3. We get the same end result that we’d get if we added 2+3 and then 1 + that result.

Parentheses might make this easier to see: (1+2)+3 produces the same result as 1+(2+3).

In plenty of other situations, though, the order in which we process the list elements may matter.

Imagine we have an array of characters and want to fold that list to produce a string. Here’s that example in Elm:

import Graphics.Element exposing (show)
import List exposing (foldl, foldr)

concat x y =
    x ++ y

list = ["a", "b", "c"]

result = foldr concat "" list

main =
    show result

The printed output is "abc".

Now try changing foldr to foldl in this example. This changes the order in which the elements are processed from left-to-right to right-to-left. The printed output will be "cba".

(You can also go back to the first example and change foldr to foldl, and see that this change does not affect the result.)

Your language or library may or may not include fold functions that go in each direction. It’s more important just to understand that the direction can matter for fold operations.

Share