<< Previous exercise (2.37)
| Index |
Next exercise (2.39) >>
;; Accumulates the result of the first and the already-accumulated
(define (accumulate op initial sequence)
(if (null? sequence)
(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)
(iter (op result (car rest))
(iter initial sequence))
(fold-right / 1 (list 1 2 3))
= (/ 1 (/ 2 (/ 3 1)))
= (/ 1 2/3)
(fold-left / 1 (list 1 2 3))
= (/ (/ (/ 1 1) 2) 3)
= (/ (/ 1 2) 3)
= (/ 1/2 3)
(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.
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.
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.
(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
Multiplication and addition properties for op works as well if we want to ensure commutative criteria.