Among the essential higher-order functions in functional programming (we have already seen `map`

and `filter`

) `reduce`

(aka. `fold`

) is probably the most amazing and powerful. It is the Swiss-Army-knife in functional programmers' hands, sort of. I highly recommend this excellent exposition, about the power and flexibility of `fold`

:

http://www.cs.nott.ac.uk/~pszgmh/fold.pdf

### What is `fold`

?

Although `fold`

deserves and probably requires several blog posts, I'll try an elementary presentation suitable to our purposes.

`fold`

is essentially the functional abstraction that corresponds to the very structure of lists.

A list of whatever kind of values, say, type `X`

, is either the empty list or a list constructed from an `X`

and a list of `X`

s, where by construction I mean the operation of `cons`

ing `X`

and a list of `X`

s. For instance (in Lisp):

```
[1]> (cons 1 (list 2 3))
(1 2 3)
```

or in Haskell, where `:`

is the Haskell equivalent to the Lispier `cons`

:

```
Prelude> 1 : [2, 3]
[1,2,3]
```

Note the self-referential nature of the type description for lists. Any function over lists relies on this self-referential structure, and it will have a natural form, where the recursive call emanates naturally from the type description. So the sketch or template of a function for list of `X`

looks like this [written now in Racket]:

```
(define (f-for-lox lox)
(cond [(empty? lox) (...)]
[else
(... (first lox)
(f-for-lox (rest lox)))]))
```

On the other hand, and by stack space efficiency reasons, functions over lists can be written in such a way that the recursive call is in tail position (in a position that ensures that is the last call in the procedure). Observe that `f-for-lox`

, the recursive call in the template above, is not in tail position; instead, the function ending up in place of the last three dots in that template will be in tail position.

I heartily recommend to watch these excellent videos, on which this exposition is mostly based, for a better understanding:

- https://www.youtube.com/watch?v=Z7qXdkt7yOE
- https://www.youtube.com/watch?v=nx8BALSH3nY
- https://www.youtube.com/watch?v=fMqbMiGuQ9c
- https://www.youtube.com/watch?v=6NyPb8jQROs

Such functions where the recursive call is in tail positions are known as tail-recursive functions and normally written with the aid of a local function that supplies an accumulator. A tail-recursive template for lists has this form:

```
(define (f-for-lox lox0)
(local [(define (f-for-lox-acc acc lox)
(cond [(empty? lox) (... acc)]
[else
(f-for-lox-acc (... acc (first lox))
(rest lox))]))]
(f-for-lox-acc ... lox0)))
```

Or this one, if we change the order of components in the recursive call:

```
(define (f-for-lox lox0)
(local [(define (f-for-lox-acc acc lox)
(cond [(empty? lox) (... acc)]
[else
(f-for-lox-acc (... (first lox) acc)
(rest lox))]))]
(f-for-lox-acc ... lox0)))
```

`fold`

is the function that capture these two abstractions. Accordingly, there are two possible `fold`

functions (the last one with two variants), `fold-right`

that captures the structural recursive procedure, and `fold-left`

that captures the tail-recursive one.

Let's see this. If we fill those templates with more meaningful placeholders, `i`

standing for the initial value, and `f`

standing for a function to combine the contribution of the first element and the contribution of the recursion, and we add them as parameters to the functions, we have this function for the natural recursive template:

```
(define (fold-right f i lox)
(cond [(empty? lox) i]
[else
(f (first lox)
(f-for-lox (rest lox)))]))
```

and this two variants for the two tail-recursive templates:

```
(define (fold-left-1 f i lox0)
(local [(define (f-for-lox-acc acc lox)
(cond [(empty? lox) acc]
[else
(f-for-lox-acc (f acc (first lox))
(rest lox))]))]
(f-for-lox-acc i lox0)))
(define (fold-left-2 f i lox0)
(local [(define (f-for-lox-acc acc lox)
(cond [(empty? lox) acc]
[else
(f-for-lox-acc (f (first lox) acc)
(rest lox))]))]
(f-for-lox-acc i lox0)))
```

that are precisely `fold-right`

and `fold-left`

, with two variants, respectively.

A careful analysis of those functions enable us to infer their respective signatures.

```
;; fold-right :: (X Y -> Y) Y (listof X) -> Y
;; fold-left-1 (1st variant) :: (Y X -> Y) Y (listof X) -> Y
;; fold-left-2 (2nd variant) :: (X Y -> Y) Y (listof X) -> Y
```

Note, in particular, that `fold-right`

and the second variant of `fold-left`

share the same signature, while the signature for the first variant of `fold-left`

differs due to the different order of arguments in the call to `f`

.

`fold-right`

is basically the same in all functional programming languages, while different languages pick the first version of `fold-left`

(Lisp, Haskell, OCaml, ...) or the second one (SML, Racket, ...) for its implementation of this function.

The difference between the two variants of `fold-left`

have an impact in many cases. Just choose as `f`

a function for which the order of operands matters (a non-commutative function). For instance if `f`

is `+`

the order doesn't matter but if it is `-`

it absolutely matters. Let's consider this for `-`

in all the languages we have mentioned:

```
# Lisp [reduce is fold-left by default]
[1]> (reduce #'- '(1 2 3 4) :initial-value 0)
-10
# Haskell
Prelude> foldl (-) 0 [1, 2, 3, 4]
-10
# OCaml
# List.fold_left (-) 0 [1; 2; 3; 4] ;;
- : int = -10
```

While:

```
# Racket
> (foldl - 0 '(1 2 3 4))
2
# SML
- List.foldl op- 0 [1, 2, 3, 4] ;
val it = 2 : int
```

[The R's `Reduce`

will be the subject of the next post.]