## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 2.38

## Problem

The `accumulate` procedure is also known as `fold-right`, because it combines the first element of the sequence with the result of
combining all the elements to the right. There is also a `fold-left`, which is similar to `fold-right`, except that it combines
elements working in the opposite direction:

(define (fold-left op initial sequence) (define (iter result rest) (if (null? rest) result (iter (op result (car rest)) (cdr rest)))) (iter initial sequence))

What are the values of

(fold-right / 1 (list 1 2 3)) (fold-left / 1 (list 1 2 3)) (fold-right list nil (list 1 2 3)) (fold-left list nil (list 1 2 3))

Give a property that `op` should satisfy to guarantee that
`fold-right` and `fold-left` will produce the same values for any sequence.

## Solution

First let's define `fold-right`; it's the same as `accumulate`:

(define (accumulate op initial sequence) (if (null? sequence) initial (op (car sequence) (accumulate op initial (cdr sequence))))) (define (fold-right op initial sequence) (accumulate op initial sequence))

Here are the values of the expressions given above:

(fold-right / 1 (list 1 2 3))

*Output:*

`
`

1.5

(fold-left / 1 (list 1 2 3))

*Output:*

`
`

0.166666666666667

(fold-right list nil (list 1 2 3))

*Output:*

`
`

(1 (2 (3 ())))

(fold-left list nil (list 1 2 3))

*Output:*

`
`

(((() 1) 2) 3)

To guarantee that `fold-right` and `fold-left` will produce the same
values for any sequence, `op` must be commutative.

(fold-right + 0 (list 1 2 3))

*Output:*

`
`

6

(fold-left + 0 (list 1 2 3))

*Output:*

`
`

6