# SICP Exercise Solution Chapter 2

Links to the original text: http://www.cnblogs.com/richard-g/p/3589813.html

# 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 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)))))```

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.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.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)))))```

Reprinted at: https://www.cnblogs.com/richard-g/p/3589813.html

Keywords: Lambda REST

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