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.33

From Drewiki
Jump to: navigation, search

Problem

Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:

(define (map p sequence)
  (accumulate (lambda (x y) <??>) nil sequence))
 
(define (append seq1 seq2)
  (accumulate cons <??> <??>))
 
(define (length sequence)
  (accumulate <??> 0 sequence))

Solution

Here's the definition of accumulate as given in the text:

(define nil (quote ()))
 
(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

Here's an implementation of map which uses accumulate:

(define (map p sequence)
  (accumulate (lambda (x y)
                (cons (p x) y))
              nil sequence))

Test:

(define (square x) (* x x))
 
(map square (list 2 3 5 7 8))

Output:

(4 9 25 49 64)


An implementation of append:

(define (append seq1 seq2)
  (accumulate cons seq2 seq1))

Test:

(append (list 1 2 3 4) (list 5 6 7 8))

Output:

(1 2 3 4 5 6 7 8)


And finally, length:

(define (length sequence)
  (accumulate (lambda (x y) (+ 1 y))
              0
              sequence))

Test:

(length (list 1 2 3 4))

Output:

4
(length (list))

Output:

0
(length (list 4 3 11 1 3 4))

Output:

6
Personal tools