SICP – Section 2.2.2   Leave a comment

Phew, finished another section of chapter 2! This one was pretty fun, mucking around with tree structures :)

P.S. For people who don’t have a hardcopy of the book, you can check out these exercises online.

;;Exercise 2.24

When doing these by hand (which I did) remember that we simply expand like so:
(list 1 (list 2 (list 3 4)))
(cons 1 (cons (cons 2 (cons (cons 3 (cons 4 nil)) nil)) nil))

Thus, the interpreter spits out:
(1 (2 (3 4)))
Here’s the box & pointer diagram:

Box and Pointer diagram for (1 (2 (3 4)))

Box and Pointer diagram for (1 (2 (3 4)))

And the Tree Diagram:

Tree Diagram for (1 (2 (3 4)))

Tree Diagram for (1 (2 (3 4)))

;;Exercise 2.25

> (define a (list 1 3 (list 5 7) 9))
> (display (car (cdr (car (cdr (cdr a))))))
7
> (define b (list (list 7)))
> (display (car (car b)))
7
> (define c (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
> (display (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr c)))))))))))))
7

;;Exercise 2.26

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

;;Exercise 2.27

This was an interesting exercise in thinking recursively. One of my favourite things about recursion is that so long as you define a base case, the function works almost magically. We are indeed controlling the spirits in the machine :)

(define (deep-reverse l)
  (define (iter l r)
    (cond ((null? l) r)
             ((pair? (car l)) (iter (cdr l) (cons (deep-reverse (car l)) r)))
             (else (iter (cdr l) (cons (car l) r)))))
  (iter l '()))

;;Exercise 2.28

This one I did last night, with good old pen & paper, and the trusty human evaluator, the brain :)
One of the things I love about lisp is its really easy syntax which makes it possible for me to parse it logically. Anyway, the first time I did this, I was using cons in place of append, which was preserving the original structure of the lists. After a bit of head scratching, I realized that what I actually wanted to be done was to merge the lists. Hence the use of append and only returning lists in this function.

(define (fringe l)
  (cond ((null? l) '())
        ((not (pair? l)) (cons l '()))
        (else (append (fringe (car l)) (fringe (cdr l))))))

;;Exercise 2.29
;;Part A
The selectors just have to take into account that we are dealing with lists not conses. That is the structure is:

a = (cons 'left-branch (cons 'right-branch nil))

So to access right-branch we do:

(car (cdr a))
Code follows:

(define (left-branch mobile)

  (car mobile))

(define (right-branch mobile)
  (car (cdr mobile)))

(define (branch-length branch)
  (car branch))

(define (branch-structure branch)
  (car (cdr branch)))

;;Part B
This procedure is best defined by referring to a branch weight, as well as a mobile weight. This way we do not use extraneous code (abstraction, remember!), and it just flows better in the mind.


(define (branch-weight branch)
  (if (number? (branch-structure branch))
      (branch-structure branch)
      (total-weight (branch-structure branch))))

(define (total-weight mobile)
  (+ (branch-weight (left-branch mobile))
     (branch-weight (right-branch mobile))))

;;Part C
This one had me confused for a while, but again, to achieve enlightenment, we must talk about a branch being able to be balanced, as well as an actual mobile.


(define (torque branch)
  (* (branch-length branch) (branch-weight branch)))

(define (branch-balanced? branch)
  (if (number? (branch-structure branch))
      true
      (balanced? (branch-structure branch))))

(define (balanced? mobile)
  (and (= (torque (right-branch mobile)) (torque (left-branch mobile)))
       (and (branch-balanced? (right-branch mobile))
            (branch-balanced? (left-branch mobile)))))

;;Part D
Because of our wonderful abstraction, the only thing we need change are the selectors!

(define (left-branch mobile)
  (car mobile))

(define (right-branch mobile)
  (cdr mobile))

(define (branch-length branch)
  (car branch))

(define (branch-structure branch)
  (cdr branch))

;;Exercise 2.30

This one’s pretty easy, I think they just want to make sure we see the possibility to abstract.

(define (square-tree tree)
  (cond ((null? tree) '())
        ((not (pair? tree)) (square tree))
        (else (cons (square-tree (car tree)) (square-tree (cdr tree))))))

;;Exercise 2.31

And here is the abstraction :)

(define (tree-map op tree)
  (cond ((null? tree) '())
        ((not (pair? tree)) (op tree))
        (else (cons (tree-map op (car tree)) (tree-map op (cdr tree))))))

;;Exercise 2.32

I found this one quite tricky, but reasoned that we must do something with (car s). So I figured that they wanted us to pair (car s) to rest somehow. The most obvious way to do this is using a cons in the function. I have italicized the added part.

(define (subsets s)
  (if (null? s)
      (list '())
      (let ((rest (subsets (cdr s))))
        (append rest (map (lambda (x) (cons (car s) x)) rest)))))

I can’t give a mathematical explanation for this, as my darned high school education hasn’t said much about set theory so far. However, it’s not too hard to follow, that we are basically appending the car of each iteration, onto the cdr, in order to get (() (1) (2) (1 2)).

Okay, so that’s not a clear explanation :D
Anyone have a better one ;)

Advertisements

Posted 03/04/2010 by Emmanuel Jacyna in Code, Scheme, 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: