Practical use of fold / reduce in functional languages

Question

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

Answer 1

The fold point is that it is more abstract. This does not mean that you can do what you could not do before, so that you can make them easier.

Using fold , you can generalize any function that is defined for two elements applicable to an arbitrary number of elements. This is a win, because it is usually easier to write, test, maintain and modify a single function that uses two arguments rather than a list. And it's always easier to write, test, maintain, etc. One simple function instead of two with a similar, but not quite functional.

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

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

Answer 2

Here are some simple examples where reduce works very 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 (ab) (+ b (apply max a))) 0 x) 17 

Build a map from the 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 complex clojure example with reduce , my solution for Project Euler 18 and 67 tasks.

See also: reduce and apply

Answer 3

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

• fold / reduce is a generic version of the cdr-ing down the list template. Each algorithm that processes each element of the sequence in order and calculates some return value can be expressed with it. This is basically a functional version of the foreach loop.

Answer 4

In Common Lisp, functions do not take any number of arguments.

Each Common Lisp implementation defines a CALL-ARGUMENTS-LIMIT constant, which must be 50 or more.

This means that any such portable written function must take at least 50 arguments. But it can be only 50.

This limit exists to allow compilers to use optimized call patterns and not provide a general case where an unlimited number of arguments could be passed.

Thus, in order to actually process lists (or more than 50 elements) in portable generic Lisp code, iterative constructs, reduction, mapping, etc. must be used. Thus, it is also necessary not to use (apply '+ large-list) , but to use (reduce '+ large-list) .

Answer 5

Code using crease is usually inconvenient to read. That is why people prefer a card, filter, exists, amount, etc., when it is available. These days I mainly write compilers and translators; here are some ways to use fold:

• Compute a set of free variables for a function, expression, or type
• Add function parameters to the symbol table, for example, for type checking
• Gather a collection of all reasonable error messages generated from a sequence of definitions
• Add all predefined classes to the Smalltalk interpreter at boot time

What is common to all of these applications is that they accumulate sequence information into a collection or dictionary. Extremely practical.

Answer 6

Here is an example that no one has mentioned yet.

Using a function with a small, well-defined interface, such as "fold", you can replace this implementation without breaking the programs that use it. For example, you can make a distributed version that runs on thousands of computers , so the sorting algorithm used has become distributed sorting , etc. Your programs are becoming more reliable, simpler and faster .

Your example is trivial: + already takes any number of arguments, runs quickly in small memory, and has already been written and debugged by those who wrote your compiler. These properties do not always correspond to the algorithms that I need to execute.