Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 2.38

From Drewiki
Jump to: navigation, search

Problem

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.

Solution

First let's define fold-right; it's the same as accumulate:

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

Here are the values of the expressions given above:

(fold-right / 1 (list 1 2 3))

Output:

1.5

(fold-left / 1 (list 1 2 3))

Output:

0.166666666666667

(fold-right list nil (list 1 2 3))

Output:

(1 (2 (3 ())))

(fold-left list nil (list 1 2 3))

Output:

(((() 1) 2) 3)


To guarantee that fold-right and fold-left will produce the same values for any sequence, op must be commutative.

(fold-right + 0 (list 1 2 3))

Output:

6

(fold-left + 0 (list 1 2 3))

Output:

6

Personal tools