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)
            input
            (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))
            input
            (last-pair-2 (cdr input)))))
    (define last-pair-3
      (lambda (input)
        (let ([last (cdr input)])
          (if (null? last)
              input
              (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)
              record
              (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)
            #t
            #f)))

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)
          #f
          (or (func (car items))
              (for-each-1 func (cdr items)))))    (define (for-each-1 func items)
      (if (null? items)
          #f
          (or (func (car items))
              (for-each-1 func (cdr items)))))

Exercise 2.24

slightly

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

a)

    (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)
          (list)
          (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)
          (list)
          (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)))
                  0
                  coefficient-sequence))

Exercise 2.35

Exercise 2.36

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