SICP – Section 2.2.3   Leave a comment

This section had just enough challenging problems, along with just enough hints to guide me along, to make it quite fun. I did this section about two weeks ago, but, due to school starting, and some other things in my life, it’s taken a bit longer to put it up. Also, I’ve put up my solutions in a github repo for people to check out, critique, and possibly correct. Anyway, without further ado, here are my solutions.

;;Exercise 2.34

The horner-eval exercise was fairly straightforward, you just have to remember that
(...(anx + an-1) x + ... + a1) x + a0
is equivalent to
a0 + x (a1 + x( ... an-1 + x (an))...)


(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)
                (+ this-coeff (* x higher-terms)))
              0
              coefficient-sequence))

;;Exercise 2.35

I felt a bit sneaky with my solution for this, my map was pretty much an identity function, it had no affect on the end result…

(define (count-leaves t)
  (accumulate (lambda (x y) (+ (if (not (pair? x)) 1 (count-leaves x)) y))
              0
              (map (lambda (x) x) t)))

;;Exercise 2.36

I had to define a couple auxiliary functions for this one, car-tree and cdr-tree take the car and cdr of the lists in a list… that is,
> (car-tree ((1 2 3) (2 3 4) (3 4 5)))
> (1 2 3)

(define (car-tree t)
  (map (lambda (l) (car l)) t))
(define (cdr-tree t)
  (map (lambda (l) (cdr l)) t))

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (accumulate op init  (map (lambda (l) (car l)) seqs))
            (accumulate-n op init (map (lambda (l) (cdr l)) seqs)))))

;;Exercise 2.37
I haven’t done much matrix and vector math, so some of my definitions may be incorrect, however, I’m pretty sure they work like they’re meant to. I’m also pretty impressed with the way these functions work so nicely. I also added a bit of error/dimensions checking, so you can’t multiply a 2×3 by a 1×4 matrix, etc.

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

(define (element r c)
  (accumulate + 0 (accumulate-n * 1 (list r c))))

(define (matrix-*-vector m v)
  (map (lambda (r) (element r v)) m))

(define (dimensions m)
  (cons (length m) (length (car m))))

(define (transpose mat)
  (accumulate-n (lambda (x y) (cons x y)) '() mat))

(define (matrix-*-matrix m n)
  (if (not (= (cdr (dimensions m)) (car (dimensions n))))
      (error "Dimension mismatch")
      (let ((cols (transpose n)))
      (map (lambda (row)
             (map (lambda (col)
                    (element col row))
                  cols))
           m))))

;;Exercise 2.38

> (fold-right / 1 (list 1 2 3))
> 3/2
> (fold-left / 1 (list 1 2 3))
> 1/6

As we can see, we get different answers, the property is fairly obvious, op must have the associative property.

;;Exercise 2.39

(define (right-reverse sequence)
  (fold-right (lambda (x y) (append y (list x))) '() sequence))

(define (left-reverse sequence)
  (fold-left (lambda (x y) (append (list y) x)) '() sequence))

Just have to flip the order in either one.

;;Exercise 2.40

(define (unique-pairs n)
  (filter (lambda (i) (not (eqv? i '())))
          (flatmap (lambda (i)
                   (map (lambda (j) (if (< j i) (list i j) '()))
                        (enumerate-interval 1 (- n 1))))
                   (enumerate-interval 1 n))))

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum? (unique-pairs n))))

This does indeed greatly simplify the definition of prime-sum-pairs, from 8 to 3 lines.

;;Exercise 2.41

I found this one a little a little tricky, but after studying the chapter again, I got it. The key is the nested mapping, and the use of flatmap, also note the abstraction in in-order?

(define (triples n)
  (flatmap (lambda (i)
             (flatmap (lambda (j)
                    (map (lambda (k)
                           (list i j k))
                         (enumerate-interval 1 n)))
                  (enumerate-interval 1 n)))
            (enumerate-interval 1 n)))

(define (in-order? cmp l)
  (cmp (car l) (cadr l) (caddr l)))

(define (gt? l)
  (in-order? > l))

(define (ordered-triples n)
  (filter gt? (triples n)))

(define (sum-to? triple s)
  (= (in-order? + triple) s))

(define (ordered-triples-which-sum-to-s n s)
  (filter (lambda (t) (sum-to? t s)) (ordered-triples n)))

;;Exercise 2.42

I haven’t completed this one yet, I think I have the general idea, but there are some issues with my implementation.

Advertisements

Posted 24/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: