# fold and stream-fold pass arguments to proc in different orders

Published by Arun Isaac on

Tags: lisp, scheme, functionalprogramming, software

*SRFI-1 fold* and *SRFI-41 stream-fold* pass arguments to *proc* in different orders. Violating the principle of least astonishment, this comes as a rather inconvenient surprise to the programmer.

Figure 1: Lambda

*SRFI-1 fold* and *SRFI-41 stream-fold* pass arguments to *proc* in different orders. This difference manifests itself when *proc* is non-commutative making similar looking *fold* and *stream-fold* calls return different results. While the documentation mentions this clearly, this comes as an inconvenient surprise to the programmer – thus, a violation of the principle of least astonishment.

Consider folding the minus (-) function over a list.

```
(fold - 0 (list 1 2 3 4))
=> (- 4 (- 3 (- 2 (- 1 0)))) => 2
(stream-fold - 0 (list->stream (list 1 2 3 4)))
=> (- (- (- (- 0 1) 2) 3) 4) => -10
```

As you can see, *fold* applies *proc* as (proc element base), whereas *stream-fold* applies *proc* as (proc base element). Note that this difference in the order of arguments passed to *proc* is not a matter of folding from the left (*SRFI-1 fold* and *SRFI-41 stream-fold*) versus folding from the right (*SRFI-1 fold-right*). The only way to make the *stream-fold* call above equivalent to the *fold* call is to pass a *proc* such that the arguments are flipped before applying the function. For example, the above call to *stream-fold* can be modified as follows.

```
(stream-fold (lambda (x y) (- y x))
0 (list->stream (list 1 2 3 4))) => 2
```

If the minus function is not clear, consider another set of examples with the *cons* function.

```
(fold cons 0 (list 1 2 3 4))
=> (cons 4 (cons 3 (cons 2 (cons 1 0))))
(stream-fold cons 0 (list->stream (list 1 2 3 4)))
=> (cons (cons (cons (cons 0 1) 2) 3) 4)
(stream-fold (lambda (x y) (cons y x))
0 (list->stream (list 1 2 3 4)))
=> (cons 4 (cons 3 (cons 2 (cons 1 0))))
```

I spent considerable time wrestling with why a perfectly fine implementation of Horner's method using *fold* broke when ported to *stream-fold* before finally going through the manual carefully and realizing the difference in the order of arguments. Two equivalent implementations of Horner's method – one expecting a *list* of polynomial coefficients and the other expecting a *stream* of polynomial coefficients – are shown below. Notice the change in the order of the arguments *an-1* and *bn* in the lambda function.

```
(define (horner x coeffs)
(fold (lambda (an-1 bn) (+ an-1 (* x bn)))
0 coeffs))
(define (stream-horner x stream-coeffs)
(fold (lambda (bn an-1) (+ an-1 (* x bn)))
0 coeffs))
```

## Image Credits

Lambda -- by Luks, released into the public domain