# weima learns to program

my attempt to do the exercises in sicp.

## Thursday, July 17, 2008

### sicp exercise 2.38

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

; (define (fold-left op initial sequence)
;   (define (iter result rest)
;     (if (null? rest)
;         result
;         (iter (op result (car rest))
;               (cdr rest))))
;   (iter initial sequence))

; What are the values of

; (fold-right / 1 (list 1 2 3))
; (fold-left / 1 (list 1 2 3))
; (fold-right list nil (list 1 2 3))
; (fold-left list nil (list 1 2 3))

; Give a property that op should satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

(define (accumulate op init seq)
(cond ((null? seq) init)
(else (op (car seq) (accumulate op init (cdr seq))))))

(define (fold-right op initial sequence)
(define (iter result rest)
(if (null? rest)
result
(iter (op (car rest) result )
(cdr rest))))
(iter 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))

(display (fold-right / 1 (list 1 2 3 4))) (newline)
(display (fold-left  / 1 (list 1 2 3 4))) (newline)

(display (fold-right + 1 (list 1 2 3 4))) (newline)
(display (fold-left  + 1 (list 1 2 3 4))) (newline)

(display (fold-right list (list) (list 1 2 3 4))) (newline)
(display (fold-left  list (list) (list 1 2 3 4))) (newline)

(display (fold-right cons (list) (list 1 2 3 4))) (newline)
(display (fold-left  cons (list) (list 1 2 3 4))) (newline)

(display (accumulate cons (list) (list 1 2 3 4))) (newline)