SICP – Section 2.2.1   Leave a comment

Alright, I’ve finished exercises 2.17-23, so here are my solutions.

Note, I’ve figured out how to get proper indentation in my posts, so hopefully it will be prettier :)

Exercise 2.17

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

Not much to say, it’s an iterative algorithm though and runs in O(n) time and O(1) space, where N is the length of the list l.


Exercise 2.18

I’ve written a recursive and iterative version of this.

(define (remove-last l)
  (if (null? (cdr l))
      (cdr l)
      (cons (car l) (remove-last (cdr l)))))

(define (reverse l)
  (if (null? l)
      l
      (cons (last-pair l) (reverse (remove-last l)))))

This is extraordinarily inefficent, because there are two extra recursive procedures being called each recursion. These being remove-last and last-pair. Because of this inefficiency, I’ve rewritten it using an iterative method, and getting rid of last-pair and remove-last.

(define (reverse l)
  (define (iter l r)
    (if (null? l)
        r
        (iter (cdr l) (cons r (car l))))
  (iter (cdr l) (car l)))

Exercise 2.19

Here are the definitions:


(define (except-first-denomination coins) (cdr coins))
(define (first-denomination coins) (car coins))
(define (no-more? coins) (null? coins))

No, the order doesn’t matter. I actually drew a tree diagram of the six permutations of (list 5 10 25) to make certain of this. I don’t think I’ll bother with the

    24

permutations of (list 1 5 10 25). The order does not matter, because the algorithm checks every path possible, removing the denominations which could “block” further processing. eg. if we have (cc 25 (25 10 5)) the 25 branch immediately returns 1, but another branch is also started without 25, allowing processing of (10 5).

Exercise 2.20


(define (filter p? l)
  (cond ((null? l) l)
        ((p? (car l)) (cons (car l) (filter p? (cdr l))))
        (else (filter p? (cdr l)))))

(define (same-parity . a)
  (cond ((even? (car a)) (filter even? a))
        ((odd? (car a)) (filter odd? a))))

The pattern of computing in same-parity can be nicely expressed here using a function called filter, which filters a list for all elements for which a predicate is true of it.

Exercise 2.21
Here are the definitions, again this is pretty simple, “fill-in-the-blank” stuff.


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

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

Exercise 2.22
To show why not, lets take a simple example and go over it using the substitution model (my favourite tool :)
We’ll iterate over the (list 1 2 3)
We get:
(iter (list 1 2 3) nil)
(iter (list 2 3) (list 1))
(iter (list 3) (list 4 1))
(iter () (list 9 4 1))
(list 9 4 1)

As can be seen, Louis is adding the cdr of the list to the car of the list (the answer).
If he interchanges the arguments, he gets:
(iter (list 1 2 3) nil)
(iter (list 2 3) (list nil 1))
(iter (list 3) (list nil 1 4))
(iter () (list nil 1 4 9))
(list nil 1 4 9)

Which doesn’t work, because instead of consing single elements, this algorithm conses the answer to the result of applying square. That is, (cons (list nil 1) 4). This results in:
(cons (cons nil 1) 4)
Instead of the
(cons nil (cons 1 (cons 4 (cons 9))))
that Louis wants. One solution to his dilemna would be to simply reverse the list before or after iterating over it.

Exercise 2.23


(define (my-for-each op items)
  (if (null? items)
      true
      (begin 
        (op (car items))
        (my-for-each op (cdr items)))))

Nothing upsetting here…

These exercises have been pretty easy, I think they’re designed to get people used to the basics of list manipulation. Thankfully, because of my background in python, which also has a really good list data structure, I’m not finding this stuff too difficult.

Advertisements

Posted 30/03/2010 by Emmanuel Jacyna in Chapter 2, SICP

Tagged with , , ,

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

%d bloggers like this: