1 (define (test-case actual expected)
10 (define (accumulate op initial sequence)
14 (accumulate op initial (cdr sequence)))))
16 (define (accumulate-n op init seqs)
17 (if (null? (car seqs))
19 (cons (accumulate op init (map car seqs))
20 (accumulate-n op init (map cdr seqs)))))
22 ;; Exercise 2.38. The accumulate procedure is also known as fold-right, because it combines the first element of the sequence with the result of combining all the elements to the right. There is also a fold-left, which is similar to fold-right, except that it combines elements working in the opposite direction:
24 (define (fold-left op initial sequence)
25 (define (iter result rest)
28 (iter (op result (car rest))
30 (iter initial sequence))
32 ;; What are the values of
34 (test-case (fold-right / 1 (list 1 2 3)) 3/2)
36 (test-case (fold-left / 1 (list 1 2 3)) 1/6)
37 ;;(list 1 (list 2 (list 3 '())))
38 (test-case (fold-right list '() (list 1 2 3)) '(1 (2 (3 ()))))
39 ;;(list (list (list nil 1) 2) 3)
40 (test-case (fold-left list '() (list 1 2 3)) '(((() 1) 2) 3))
42 ;; Give a property that op should satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.
44 ;; we need both associativity and commutativity
46 ;; (op a (op b c)) = (op (op a b) c)
48 ;; (op a b) = (op b a)
52 ;; (op a (op b (op c initial)))
54 ;; (op (op (op initial a) b) c)
56 ;; (op (op initial (op a b)) c)
58 ;; (op (op (op a b) initial) c)
60 ;; (op (op a (op b initial)) c)
62 ;; (op a (op (op b initial) c))
64 ;; (op a (op b (op initial c)))
66 ;; (op a (op b (op c initial)))