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)

initial

(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)

result

(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))

1/6

> (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

andA 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)

Related:

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