SICP Exercise Solution Chapter 2

Links to the original text:

Construction of Computer Program and Solution of Explanation Exercises

Structure and Interpretation os Computer Programs Exercises Answer

Chapter 2 Constructing Data Abstraction

Exercise 2.17

    (define last-pair-1
      (lambda (input)
        (if (= (length input) 1)
            (last-pair-1 (cdr input)))))
    ;because length The definition is recursive, so if it's a long list, use length It can be very time-consuming.
    ;last-pair-2 and last-pair-3 use null´╝čIt's more efficient to check whether the list is empty or not.
    (define last-pair-2
      (lambda (input)
        (if (null? (cdr input))
            (last-pair-2 (cdr input)))))
    (define last-pair-3
      (lambda (input)
        (let ([last (cdr input)])
          (if (null? last)
              (last-pair-3 last)))))

Exercise 2.18

    (define reverse-1
      (lambda (input)
        (if (null? input)
            (append (reverse-1 (cdr input)) (cons (car input) '())))))
    ;More efficient in an iterative way       
    (define reverse-2
      (lambda (input)
        (define reverse-iter
          (lambda (remain record)
            (if (null? remain)
              (reverse-iter (cdr remain) (cons (car remain) record)))))
      (reverse-iter input '())))

Exercise 2.19

Understand the logic of changing change. The different ways of changing total cash into n coins are equal to:

  • Regardless of the first coin, the number of different ways of converting cash a into all other coins except the first coin, plus
  • Considering the first kind of coin, the number of different ways of converting cash a-v[0] into all kinds of coins.

So the ranking order of coin-values has nothing to do with the results. Whether the results are ordered or not is the same.

    (define first-denomination
      (lambda (coin-values)
        (car coin-values)))
    (define except-first-denomination
      (lambda (coin-values)
        (cdr coin-values)))
    (define no-more?
      (lambda (coin-values)
        (if (null? coin-values)

Exercise 2.21

    (define (square-list-1 items)
      (if (null? items)
          (cons (* (car items) (car items)) (square-list-1 (cdr items)))))
    (define (square-list-2 items)
      (map (lambda (x) (* x x)) items))

Exercise 2.22

The function of (cons x y) is to insert x as an element at the beginning of list y, if x itself is one
For a list, x is inserted as a list at the beginning of y.
For example, the result of (cons'(1)'(23)) is not'(123), but'('(1) 23).
Appnd can be used here.

Exercise 2.23

    (define (for-each-1 func items)
      (if (null? items)
          (or (func (car items))
              (for-each-1 func (cdr items)))))    (define (for-each-1 func items)
      (if (null? items)
          (or (func (car items))
              (for-each-1 func (cdr items)))))

Exercise 2.24


Exercise 2.25

    (car (cdr (car (cdr (cdr '(1 3 (5 7 9)))))))
    (car (car '((7))))
    (car (cdr (car (cdr (car (cdr (car(cdr (car (cdr (car (cdr '(1 (2 (3 (4 (5 (6 7))))))))))))))))))

Exercise 2.26

- (append x y): '(1 2 3 4 5 6)
- (cons x y): '((1 2 3) (4 5 6))
- (list x y): '((1 2 3) (4 5 6))

Exercise 2.27

    (define (deep-reverse items)
        [(null? items) (list)]
        [(not (pair? (car items))) (append (deep-reverse (cdr items)) (list (car items)))]
        [else (append (deep-reverse (cdr items)) (cons (deep-reverse (car items)) (list)))]))

Exercise 2.28

    (define (fringe items)
      (if (null? items)
          (if (pair? (car items))
              (append (fringe (car items)) (fringe (cdr items)))
              (cons (car items) (fringe (cdr items))))))

Exercise 2.29


    (define (left-branch bran)
      (car bran))
    (define (right-branch)
      (car (cdr bran)))

Exercise 2.30

1) Direct definition without using higher-order functions

    (define (square-tree items)
      (if (null? items)
          (if (not (pair? (car items)))
              (cons (* (car items) (car items)) (square-tree (cdr items)))
              (append (cons (square-tree (car items)) (list)) (square-tree (cdr items))))))

2) use map

    (define (tree-map proc trees)
      (if (null? trees)
          (if (not (pair? (car trees)))
              (cons (proc (car trees)) (tree-map proc (cdr trees)))
              (append (cons (tree-map proc (car trees)) (list)) (tree-map proc (cdr trees))))))

Exercise 2.31

The answer is the same as 2.30.

Exercise 2.32

Exercise 2.33

    (define (map p sequence)
      (accumulate (lambda (x y) (p x)) '() sequence))
    (define (append seq1 seq2)
      (accumulate cons seq2 seq1))
    (define (length sequence)
      (accumulate (lambda (x y) (+ y 1)) 0 sequence))

Exercise 2.34

    (define (horner-eval x coefficient-sequence)
      (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* x higher-terms)))

Exercise 2.35

Exercise 2.36

    (define (first-elems items)
      (if (null? items)
          (cons (car (car items)) (first-elems (cdr items)))))
    (define (rest-elems items)
      (if (null? items)
          (cons (cdr (car items)) (rest-elems (cdr items)))))
    (define (accumulate-n op init seqs)
      (if (null? (car seqs))
          (cons (accumulate op init (first-elems seqs))
                (accumulate-n op init (rest-elems seqs)))))

Reprinted at:

Keywords: Lambda REST

Added by IAK on Sat, 12 Oct 2019 20:35:52 +0300