Folds equivalence - exercise 2.38

[sechmo]

https://github.com/mk12/sicp/blob/6213929f1c848d36551e40889bd2886e1dbaca4a/src/sicp/chapter-2.ss#L1111

I think the operation must be both associative and commutative.

Commutativity is needed since fold-left corresponds to nested (op prev-values-acc curr-el) calls, that is (left-fold op init (1 2 3 ... n)) = (op ...(op (op (op init 1) 2) 3)... n) while fold-right corresponds to (op curr-el next-values-acc), that is (fold-right op init (1 2 3 ... n)) = (op 1 (op 2 (op 3 ...(op n init)...))) So we need to swap the order of each op, but to move the init from (op last-el init) "up to" (op init-fist el) we need associativity

We can visualize it like this

(left-fold op init (1 2 3 ... n))
= (op ...(op (op (op init 1) 2) 3)... n)
{ associativity }
= (op ...(op (op (op init 1) 2) n)... 3) ;; elements move to the right
= (op (op ...(op (op init 1) n)... 2) 3)
= (op (op ...(op (op init 1) n)... 3) 2) ;; to their appropiate ordered place
= (op (op (op ...(op init n)... 1) 3) 2)
= (op (op (op ...(op init n)... 3) 1) 2)
= (op (op (op ...(op init n)... 3) 2) 1)
{ commutativity }
= (op (op (op ...(op n init)... 3) 2) 1) ;; argument swaps
= (op (op (op 3 ...(op n init)...) 2) 1)
= (op (op 2 (op 3 ...(op n init)...)) 1)
= (op 1 (op 2 (op 3 ...(op n init)...)))
= (fold-right op init (1 2 3 ... n))

Here is an example that commutativity does not suffice

(define (f a b) (+ (* 2 a) (* 2 b)))
;; f is commutative
;; f(a,b) = 2a + 2b = 2b + 2a = f(b,a)
;; but not associative
;; f(a,f(b,c)) = 2a + 2f(b,c) = 2a + 2(2b + 2c) = 2a + 4b + 4c
;; !=
;; f(f(a,b),c) = 2f(a,b) + 2c = 2(2a + 2b) = 4a + 4b + 2c

(fold-left f 0 (list 1 2 3 4)) ;; 52
(fold-right f 0 (list 1 2 3 4)) ;; 98