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

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 2

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 3

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.