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.

Lambda

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