SICP Solutions: Section 2.2.1

Section 2.2 - Hierarchical Data and the Closure Property

Section 2.2.1 - Representing Sequences

Exercise 2.17

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

Exercise 2.18

This is the iterative version:

(define (reverse items)
    (define (reverse-iter i l)
      (if (null? i)
          l
          (reverse-iter (cdr i) (cons (car i) l))))
    (reverse-iter items nil))

We can use append to create a recursive version:

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

But this will be more expensive because append will iterate over each subset.

Exercise 2.19

The three procedures are really simple actually, just renaming the list-operating procedures.

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

The order of list coin-values does not affect the answer produced by cc. This is because the procedure is not based on any assumption regarding the order of the elements.

Exercise 2.20

(define (same-parity . i)
    (define (iter-parity f l)
      (cond ((null? l) l)
            ((f (car l)) (cons (car l) (iter-parity f (cdr l))))
            (else (iter-parity f (cdr l)))))
    (cond ((null? i) nil)
          ((even? (car i)) (iter-parity even? i))
          ((odd? (car i)) (iter-parity odd? i))))

Exercise 2.21

(define (square-list items)
  (if (null? items)
      nil
      (cons (* (car items) (car items))
            (square-list (cdr items)))))

(define (square-list items)
  (map (lambda (x) (* x x)) items))

Exercise 2.22

Louis’ solution is essentially how we implemented reverse for exercise 2.18. Each iteration creates something like (cons 9 (cons 4 (cons 1 nil))), which is exactly how lists are implemented.

Unfortunately the second solution is no good either, because it is the inverse of how lists are implemented, and results into something like (cons (cons (cons nil 1) 4) 9). The order is correct, but this isn’t how Scheme structures lists from cons cells.

Exercise 2.23

(define (for-each proc items)
  (cond ((null? items) nil)
        (else (proc (car items))
              (my-for-each proc (cdr items)))))