SICP 2.2 exercises

2.17

(define (last-pair items)
  (if (null? (cdr items))
      items
      (last-pair (cdr items))))

Nice and easy exercise.

2.18

(define (reverse items)
  (if (null? (cdr items))
      items
    (append (reverse (cdr items)) (list (car items)))))

(define (reverse-2 items)
  (define (iter src dest)
    (if (null? src)
        dest
        (iter (cdr src) (cons (car src) dest))))
  (iter items (list)))

Made two different version here. This took a while because I kept trying to solve it without using append or iteration, which was silly.

2.19

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

(define (first-denomination coin-values)
  (car coin-values))

(define (except-first-denomination coin-values)
  (cdr coin-values))

(define (no-more? coin-values)
  (null? coin-values))

2.20

(define (same-parity x . z)
  (define (recur first rest)
    (if (null? rest)
        rest
      (if (= (remainder first 2) (remainder (car rest) 2))
          (cons (car rest) (recur first (cdr rest)))
        (recur first (cdr rest)))))
  (cons x (recur x z)))

2.21

(define (square-list-1 items)
  (if (null? items)
      '()
    (cons (square (car items)) (square-list-1 (cdr items)))))

(define (square-list-2 items)
  (map square items))

2.22

The structure is similar to my implementation of reverse above. The last element is cons-ed on to the front of the result, so it flips.

The “bug fix” results in many nested pairs due to the way cons works.

2.23

(define (for-each f items)
  (cond ((null? items) #t)
        (else (f (car items))
              (for-each f (cdr items)))))

One thing that always catches me out is how certain statements like if only allow a single expression while others like define and cond allow multiple clauses. I think there’s something like do later but I haven’t come across it yet.

2.24

guile> (list 1 (list 2 (list 3 4)))
(1 (2 (3 4)))

compound

tree_rep

The box representation turned out to be less straight forward than I thought. The good thing is that what cons, car and cdr are is greatly emphasized.

2.25

(define x (list 1 3 (list 5 7) 9))
(car (cdr (car (cdr (cdr x)))))
7

(define x (list (list 7)))
(car (car x))
7

(define x (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr x))))))))))))
7

The challenge was to do it without trial and error. This again drives home what car and cdr do.

2.26

guile> (append x y)
(1 2 3 4 5 6)
guile> (cons x y)
((1 2 3) 4 5 6)
guile> (list x y)
((1 2 3) (4 5 6))

Cons behavior and how the interpreted handles lists is emphasized in this exercise.

2.27

(define (deep-reverse items)
  (if (not (pair? items))
      items
    (append (deep-reverse (cdr items)) (list (deep-reverse (car items))))))

I used bit of trial and error here, but the logic makes sense in retrospect.

2.28

My first working answer to this was rather silly.

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

I then looked up what other people did and figured out how to stop using both cons and append.

(define (fringe tree)
  (if (null? tree)
      '()
      (if (pair? tree)
          (append (fringe (car tree)) (fringe (cdr tree)))
          (list tree))))

Took a really long time for this one.

Comments: Got a large chunk done today, and it was challenging enough that I feel like I’ve learned a lot doing these exercises.

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s