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

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

"I *wasn't expecting* that final nil to be there, but I guess it *was* added to the newly-created list.": list is not same as cons.

Notice here we only need init to be communicative with x but don't need one *arbitrary pair* (see woofy's and Nico de Vreeze's comment).

\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

Here it only shows "commutative" and "associative" are necessary conditions. But they may not be sufficient conditions.

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

Strict commutativity is not required. Consider OP as matrix multiplication where INITIAL value is identity marix I. I * A = A * I and also OP is associative so foldleft and foldright on matrix mulitiplication gives the same result. However matrix multiplication (the OP) is not commutative.

Update: However there is no universal Identity Matrix of all shapes! The above arguments are not valid.

Adding to woofy: associativity is required. Next to this either: a) the operator is commutative, as explained before. b) an identity element for the operator is given (see Monoid)

Eg:

(fold-left append nil (list '(1) '(2 3) '() '(4))) ;; (1 2 3 4) (fold-right append nil (list '(1) '(2 3) '() '(4))) ;; (1 2 3 4) ;; if we use something other than nil, results will be different: (fold-left append '(5) (list '(1) '(2 3) '() '(4))) ;; (5 1 2 3 4) (fold-right append '(5) (list '(1) '(2 3) '() '(4))) ;; (1 2 3 4 5)

As woofy says, Monoid "equipped with an *associative binary operation and an identity element*" https://en.wikipedia.org/wiki/Monoid#:~:text=In%20abstract%20algebra%2C%20a%20branch,structures%20between%20magmas%20and%20groups. is enough where identity just means the definition "I * A = A * I".

---

To be more specific, we can be prove this sufficient condition by induction of seq length `n`.

base case: n=2 where each line of comments shows how the transformation between 2 lines is done. Here * can be arbitrary operation meeting associativity and meeting commutativity only needed for I and arbitrary single data.

(A_1 * (A_2 * I)) associativity ((A_1 * A_2) * I) commutativity for I (I * (A_1 * A_2)) associativity ((I * A_1) * A_2)

induction:

(A_1 * (A_2 * (... (A_ n * (A_{n+1} I)) ...))) associativity (A_1 * (A_2 * (... ((A_ n * A_{n+1}) * I) ...))) induction needing n+1>=3 ((... ((I * A_1) * A_2) ...) * (A_ n * A_{n+1})) associativity (((... ((I * A_1) * A_2) ...) * A_ n) * A_{n+1})

Actually, there's a much simpler way to implement `fold-left` iteratively than the book provides. Here it is:

`(define (my-fold-left op init seq) (if (null? seq) init (my-fold-left op (op init (car seq)) (cdr seq))))`

LisScheSic

This is same as

foldhttps://www.gnu.org/software/mit-scheme/documentation/stable/mit-scheme-ref/Folding-of-Lists.html#index-fold_002dleft except that the order ofinit (car seq)is swapped.