<< Previous exercise (2.37) | Index | Next exercise (2.39) >>

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

\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

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

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

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.