Practical use of fold/reduce in functional languages

Question

Fold (aka reduce) is considered a very important higher order function. Map can be expressed in terms of fold (see here). But it sounds more academical than practical to me. A typical use could be to get the sum, or product, or maximum of numbers, but these functions usually accept any number of arguments. So why write (fold + 0 '(2 3 5)) when (+ 2 3 5) works fine. My question is, in what situation is it easiest or most natural to use fold?

Answer 1

The point of fold is that it's more abstract. It's not that you can do things that you couldn't before, it's that you can do them more easily.

Using a fold, you can generalize any function that is defined on two elements to apply to an arbitrary number of elements. This is a win because it's usually much easier to write, test, maintain and modify a single function that applies two arguments than to a list. And it's always easier to write, test, maintain, etc. one simple function instead of two with similar-but-not-quite functionality.

Since fold (and for that matter, map, filter, and friends) have well-defined behaviour, it's often much easier to understand code using these functions than explicit recursion.

Basically, once you have the one version, you get the other "for free". Ultimately, you end up doing less work to get the same result.

Answer 2

Here are a few simple examples where reduce works really well.

Find the sum of the maximum values of each sub-list

Clojure:

user=> (def x '((1 2 3) (4 5) (0 9 1)))
#'user/x
user=> (reduce #(+ %1 (apply max %2)) 0 x)
17

Racket:

> (define x '((1 2 3) (4 5) (0 9 1)))
> (foldl (lambda (a b) (+ b (apply max a))) 0 x)
17

Construct a map from a list

Clojure:

user=> (def y '(("dog" "bark") ("cat" "meow") ("pig" "oink")))
#'user/y
user=> (def z (reduce #(assoc %1 (first %2) (second %2)) {} y))
#'user/z
user=> (z "pig")
"oink"

For a more complicated clojure example featuring reduce, check out my solution to Project Euler problems 18 & 67.

See also: reduce vs. apply

Answer 3

In Common Lisp functions don't accept any number of arguments.

There is a constant defined in every Common Lisp implementation CALL-ARGUMENTS-LIMIT, which must be 50 or larger.

This means that any such portably written function should accept at least 50 arguments. But it could be just 50.

This limit exists to allow compilers to possibly use optimized calling schemes and to not provide the general case, where an unlimited number of arguments could be passed.

Thus to really process large (larger than 50 elements) lists or vectors in portable Common Lisp code, it is necessary to use iteration constructs, reduce, map, and similar. Thus it is also necessary to not use (apply '+ large-list) but use (reduce '+ large-list).

Answer 4

1. Your example (+ 2 3 4) only works because you know the number of arguments beforehand. Folds work on lists the size of which can vary.

2. fold/reduce is the general version of the "cdr-ing down a list" pattern. Each algorithm that's about processing every element of a sequence in order and computing some return value from that can be expressed with it. It's basically the functional version of the foreach loop.

Answer 5

Code using fold is usually awkward to read. That's why people prefer map, filter, exists, sum, and so on—when available. These days I'm primarily writing compilers and interpreters; here's some ways I use fold:

• Compute the set of free variables for a function, expression, or type
• Add a function's parameters to the symbol table, e.g., for type checking
• Accumulate the collection of all sensible error messages generated from a sequence of definitions
• Add all the predefined classes to a Smalltalk interpreter at boot time

What all these uses have in common is that they're accumulating information about a sequence into some kind of set or dictionary. Eminently practical.

Answer 6

Here's an example that nobody else mentioned yet.

By using a function with a small, well-defined interface like "fold", you can replace that implementation without breaking the programs that use it. You could, for example, make a distributed version that runs on thousands of PCs, so a sorting algorithm that used it would become a distributed sort, and so on. Your programs become more robust, simpler, and faster.

Your example is a trivial one: + already takes any number of arguments, runs quickly in little memory, and has already been written and debugged by whoever wrote your compiler. Those properties are not often true of algorithms I need to run.