Saturday, April 30, 2011

SICP 2.38 & 2.39: Folding Left and Right

From SICP section 2.2.3 Sequences as Conventional Interfaces

Exercise 2.38 informs us that another name for the accumulate procedure we've been using is fold-right, because it combines the elements of a sequence starting on the left and moving to the right. There's also a fold-left procedure that combines elements working in the opposite direction.
; fold-right is another name for accumulate
(define (fold-right op initial sequence)
(if (null? sequence)
(op (car sequence)
(fold-right op initial (cdr sequence)))))

; fold-left is given in exercise 2.38
(define (fold-left op initial sequence)
(define (iter result rest)
(if (null? rest)
(iter (op result (car rest))
(cdr rest))))
(iter initial sequence))

We're given a few expressions that illustrate how these two procedures behave differently.
> (fold-right / 1 (list 1 2 3))
1 1/2
> (fold-left / 1 (list 1 2 3))
> (fold-right list null (list 1 2 3))
(1 (2 (3 ())))
> (fold-left list null (list 1 2 3))
(((() 1) 2) 3)

We're asked what property the op parameter needs to satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

The property that will guarantee that fold-right and fold-left will produce the same values for any sequence is commutativity. You may remember the commutative property of both addition and multiplication from algebra. It's the law that says that:

A + B = B + A
A x B = B x A

Subtraction and division are not commutative operations. The AND and OR operations in Boolean algebra are commutative.

Exercise 2.39 asks us to complete the following definitions of reverse (from exercise 2.18) in terms of fold-right and fold-left:
(define (reverse sequence)
(fold-right (lambda (x y) <??>) null sequence))

(define (reverse sequence)
(fold-left (lambda (x y) <??>) null sequence))

Since we only need to define the operator used in each implementation, the key to this exercise lies in how the operator is applied in each folding procedure. Pay close attention to the order of the arguments of the op procedure.

In fold-right the operator is applied to the car of the sequence and the result of a recursive call to fold-right. Just as we did in exercise 2.18, we can reverse the sequence using fold-right by appending the car of the sequence to the reverse of its cdr.
(define (reverse sequence)
(fold-right (lambda (x y) (append y (list x))) null sequence))

In fold-left the operator is applied to the result sequence and the car of the unused elements in the initial sequence. Since the result sequence starts with an initial value of null, and we're starting at the end of the sequence and working backwards anyway, we can just cons each element to the end of the result.
(define (reverse sequence)
(fold-left (lambda (x y) (cons y x)) null sequence))

As expected, we get the same test results for either of the two reverse implementations above.
> (reverse (list 1 2 3 4))
(4 3 2 1)
> (reverse (list 1 4 9 16 25))
(25 16 9 4 1)
> (reverse (list 1 3 5 7))
(7 5 3 1)
> (reverse (list 23 72 149 34))
(34 149 72 23)


For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.


Tim Kington said...

I found the earlier accumulate examples very tough going. I find fold-left much more intuitive, and kept being surprised that accumulate didn't work that way.

Bill the Lizard said...


Do you mean the implementation or this exercise was more intuitive? I find the implementation of fold-right a bit easier to grasp, but the way fold-left works definitely made the solution to this particular exercise simpler.

Alex Marandon said...

A note for those of us testing their code with Racket. The foldl function of Racket doesn't behave the same way as what is described in SICP. There's a discussion about this on SO [1]. Make sure you use the implementations of fold-left presented in the book otherwise you'll get different results. If you load neil/sicp [2] you won't have Racket's foldl and foldr available but if you do exercise 2.38 without loading it (as I initially did) and try to use foldl from Racket, you might get confused.


Bill the Lizard said...

Thanks Alex. I only upgraded to Racket about a month ago, so I don't know the inconsistencies between its implementations and the earlier exercises. Thanks for pointing that out.

Anonymous said...

Hi Bill,
The algebraic property you're after is not commutativity -- it's associativity. (I.e. need (op A (op B C)) to yield the same value as (op (op A B) C)

Managed to find the link below to save me typing up some long winded explanation. He uses the example of matrix multiplication, which is associative but obviously not commutative.

- 12qu

12qu said...

EDIT: On further reflection, I think we need both associativity and commutativity.

When we go from fold-left to fold-right, we effectively pull the init value from the far left hand side of the expression to the far right. The only way to guarantee that fold-left will equal fold-right in this case is if (op a b) always gives (op b a) (i.e. it commutes).

In the matrix multiplication example, for instance, if some matrix other than the identity matrix is used for init, then fold-left won't in general give fold-right, as is quite easy to verify.

Likewise, to see that commutativity is not enough, consider the function (define (average x y) (* .5 (+ x y))), which is commutative and not associative, and for which fold-left does not, in general, equal fold right.

Bill the Lizard said...


I think you might be right, it might be both associativity and commutativity. I did some searching around, and there are a lot of sites that say one or the other. To prove that it is both, we'd have to find an operation that works that is associative and not commutative. I'll give it some thought before updating the post.


Wei Xue said...

Yes. Both commutativity and associativity

Anonymous said...

No, only associativity.

Consider this operation:
(define (foo a b) (fringe (list a b)))

This operation takes two things, creates a list of them and then flattens the list.
It is associative, because if a = (list a1 a2 ...) and b = (list b1 b2 ...) and c = (list c1 c2 ...) then:

(foo (foo a b) c) = (list a1 a2 ... b1 b2 ... c1 c2) = (foo a (foo b c))

It isn't commutative:
(foo 1 2) = (list 1 2)
(foo 2 1) = (list 2 1)

> (fold-right foo nil (list 1 2 3 4))
(1 2 3 4)
> (fold-left foo nil (list 1 2 3 4))
(1 2 3 4)

Anonymous said...

Oops, never mind, I was wrong since when the default value is not nil then the results are different. So both associative and commutative.