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

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.

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.