# sicp-ex-2.38

jz

```
;; Accumulates the result of the first and the already-accumulated
;; rest.
(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))

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

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

I wasn't expecting that final nil to be there, but I guess it *was* added to the newly-created list.

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

Same story with the innermost nil here.

Op has to be associative for fold-left and fold-right to be equivalent. For example, folding left and right with division would not be equivalent, but with matrix multiplication would (despite it's not a commutative operation).

```  (fold-left + 0 (list 1 2 3 4))
(fold-right + 0 (list 1 2 3 4))
```

The op must be commutative to ensure fold-left and fold-right get the same result. Consider sequence to be [x1, x2, ... xn], then (fold-left op init sequence) will be (op (op ... (op init x1) x2) ... xn) and (fold-right op init sequence) will be (op (op ... (op xn init) xn-1) ... x1). Now consider a special case sequence only contains one element, so sequence = [x1], then fold-left will get (op init x1) and fold-right will get (op x1 init), for these two to be equal, op must be commutative.

brother anon

\n

\n

examples of unfolding (brackets show priority):

1. seq = '(a), op = +, zero = 0

```   foldr: a + 0
foldl: 0 + a
```

2. seq = '(a b)

```   foldr: a + (b + 0)
foldl: (0 + a) + b
```

[foldl, foldr as given in the book]

so i'd say you need both commutativity and associativity. either alone is not enough.

hairybreeches

\n

\n

Suppose (foldl f a s) = (foldr f a s) for all a, s

Then (f a b) = (foldl f a (b)) = (foldr f a (b)) = (f b a)
So f is commutative.

also
(f a (f b c)) = (f a (f c b)) (commutativity)
= (foldr f b (a c))
= (foldl f b (a c))
= (f (f b a) c)
= (f (f a b) c) (commutativity)
so f is associative

bxblin

Multiplication and addition properties for op works as well if we want to ensure commutative criteria.