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.

## 10 comments:

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.

Tim,

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.

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.

[1] http://stackoverflow.com/questions/8778492/why-is-foldl-defined-in-a-strange-way-in-racket

[2] http://planet.plt-scheme.org/package-source/neil/sicp.plt/1/16/planet-docs/sicp/index.html

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.

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.

http://danboykis.com/2009/08/exercise-2-38-of-sicp/

- 12qu

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

andcommutativity.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.

12qu,

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.

Thanks!

Yes. Both commutativity and associativity

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)

Now:

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

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

Post a Comment