Archive for the ‘scheme’ Tag

SICP Section 2.3.4   Leave a comment

This section puts what we’ve learned about sets into practice implementing a method of encoding and decoding messages encoded with huffman code trees, and also a method of generating the trees.

;;Exercise 2.67
> (decode sample-message sample-tree)
(A D A B B C A)

;;Exercise 2.68
The encode-symbol procedure I wrote is straightforward, but takes a rather large number of steps to encode a symbol, because we have to search the set of symbols at each node for the correct branch to take. I’m not sure if there’s a better way to do this…

(define (encode-symbol symbol tree)
  (cond ((leaf? tree) '())
        ((element-of-set? symbol (symbols (left-branch tree)))
         (cons 0 (encode-symbol symbol (left-branch tree))))
        ((element-of-set? symbol (symbols (right-branch tree)))
         (cons 1 (encode-symbol symbol (right-branch tree))))
        (else (error "symbol not in tree - ENCODE-SYMBOL" symbol))))

;;Exercise 2.69
Successive-merge was actually fairly straightforward to code, however, when I first attempted to do this, I did not fully understand the actual tree generation procedure! Perhaps this is what the authors were warning about when they said it was tricky, I was certainly tricked initially :D

(define (successive-merge leaf-set)
  (if (= (length leaf-set) 1)
      (car leaf-set)
       (adjoin-set (make-code-tree (car leaf-set)
                                   (cadr leaf-set))
                   (cddr leaf-set)))))

;;Exercise 2.70
I never knew 50s rock was so repetitive ;)
Probably better than the junk that gets put out these days though…

(define freq-pairs (list (list 'A 2) (list 'BOOM 1) (list 'GET 2) (list 'JOB 2) (list 'NA 16) (list 'SHA 3) (list 'YIP 9) (list 'WAH 1)))

(define message '(GET A JOB
                  SHA NA NA NA NA NA NA NA NA
                  GET A JOB
                  SHA NA NA NA NA NA NA NA NA
                  SHA BOOM))

(define rock50s-tree (generate-huffman-tree freq-pairs))

(define encoded-message (encode message rock50s-tree))
(define huffman-length (length encoded-message))

(define logbase2-of-8 3)
(define fixed-length (* (length message) logbase2-of-8))

fixed-length turns out to be 108 bits long, whereas the huffman-length is only 84 bits long. That’s a pretty fair length saving.

;;Exercise 2.71
I’m not really a fan of drawing large trees, so I’ll just give the code to generate it.

(define freq-pairs-5 (list (list '1 1) (list '2 2) (list '3 4) (list '4 8) (list '5 16)))
(define freq-pairs-tree-5 (generate-huffman-tree freq-pairs-5))

(define freq-pairs-10 (list (list '1 1) (list '2 2) (list '3 4) (list '4 8) (list '5 16) (list '6 32) (list '7 64) (list '8 128) (list '9 256) (list '10 512)))
(define freq-pairs-tree-10 (generate-huffman-tree freq-pairs-10))

The number of bits required for n=5 code are
Largest frequency: 1
Lowest frequency: 4
For n=10
Largest frequency: 1
Lowest frequency 9

It’s fairly obvious that the largest frequency will always have 1 bit, and the lowest frequency will have (n-1) bits.

;;Exercise 2.72
As we descend the tree we have to search the list of symbols at the node we are on, which is of the order O(n). We will need to descend n levels worst case, therefore n searches n deep is O(n2)

SICP Section 2.3.3   Leave a comment

The focus of this section is on representing mathematical sets with Scheme’s built-in data structures, and methods of combining these data structures to enable us to write faster algorithms for performing set operations. We go from a basic list based representation, to binary trees. I found this section to be quite a test of my abstract thinking skills; visualizing the operations on the representations was quite difficult for me.

;;Exercise 2.59
Implementing union-set is fairly straightforward for the unordered-list representation.

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((element-of-set? (car set1) set2)
         (union-set (cdr set1) set2))
        (else (cons (car set1) (union-set (cdr set1) set2)))))

;;Exercise 2.60
This exercise was pretty interesting, it makes you think about situations in which what would seem to be an inefficient algorithm is actually the best for a job. Here’s my implementation of the set operations for an unordered set which allows duplicates.

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))

(define (adjoin-set x set)
  (cons x set))

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)
         (cons (car set1)
               (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))

(define (union-set set1 set2)
  (append set2 set1))

From the code we can see that, when duplicates are allowed,

  • element-of-set? is still O(n)
  • adjoin-set is O(1) from O(n)
  • intersection-set is still O(n^2)
  • union-set is O(n) from O(n^2)

By allowing duplicates, we have sped things up quite a bit, even if the algorithms are going to use up a lot more memory. In choosing which algorithm to use in a certain situation, we need to take into account the environment it will be used in. If we are, for example, on a machine with limited CPU speed, but a lot of memory (not uncommon in machines that have been upgraded), the duplicate representation would be best. On the other hand, if we were dealing with huge numbers, it would be a big drain on memory to use the duplicate representation, and the non-duplicate representation would be better for keeping overhead down.

;;Exercise 2.61
Now we’re starting to optimize the representations a bit more, it’s really neat to see how simple ideas like ordering the sets can produce fairly large performance gains :)

(define (adjoin-set x S)
  (cond ((null? S) (list x))
        ((< x (car S)) (cons x S))
        ((> x (car S)) (cons (car S) (adjoin-set x (cdr S))))
        ((= x (car S)) S)))

The ordered-list representation will take less time to adjoin, on the average, because we will not necessarily have to process the whole list in order to know if a duplicate exists.

;;Exercise 2.62
This particular exercise required a fair bit of thought. Here’s my explanation.
If the first element of set1 is less than the first element of set2, we make that element the car of a new list, and the cdr of the new list is the union of the cdr of set1 and set2…

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((< (car set1) (car set2))
         (cons (car set1) (union-set (cdr set1) set2)))
        ((> (car set1) (car set2))
         (cons (car set2) (union-set set1 (cdr set2))))
        ((= (car set1) (car set2))
         (cons (car set1)
               (union-set (cdr set1)
                          (cdr set2))))))

;;Exercise 2.63
I think this exercise is designed to see how well we can transform a diagram into the actual representation of a tree as the most difficult part was writing down the trees :D

(define tree1 (make-tree 7
                         (make-tree 3
                                    (make-tree 1 '() '())
                                    (make-tree 5 '() '()))
                         (make-tree 9
                                    (make-tree 11 '() '()))))

(define tree2 (make-tree 3
                         (make-tree 1 '() '())
                         (make-tree 7
                                    (make-tree 5 '() '())
                                    (make-tree 9
                                               (make-tree 11 '() '())))))

(define tree3 (make-tree 5
                         (make-tree 3
                                    (make-tree 1 '() '()))
                         (make-tree 9
                                    (make-tree 7 '() '())
                                    (make-tree 11 '() '()))))

After running these through both functions, you’ll see that both the recursive and iterative procedures produce the same result, which is expected if they are to do the same job…

Yes, they both have the same order of growth, however tree->list-2 uses less memory than tree->list-3, and thus could be faster in certain situations.

;;Exercise 2.64
Partial-tree works in a very recursive fashion :)
The best way I can explain is to work through an example.
Let’s say we have the list '(1 2 3 4 5) to turn into a tree.
Partial-tree first assigns equal, or almost equal sizes for the left and right branch of the new tree. So for our tree left-size will be 2, and right-size will be 3 (because the size of the list is not even). Then, partial tree conses together the result of partial-tree on the left and right halves of the given list. It’s quite a bit for me to wrap my head around, to be sure!

The list looks like so:

;;Exercise 2.65
Still a work in progress for me…

;;Exercise 2.66
The lookup procedure is basically element-of-set?, except instead of returning true or false, we return the item requested by key, or false if it’s not found.

(define (lookup key records)
  (cond ((null? records) false)
        ((= key (entry records)) (record-value (entry records)))
        ((< key (entry records))
         (lookup key (left-branch records)))
        ((> key (entry records))
         (lookup key (right-branch records)))))

;;Where a record structure looks like
(define (make-record key value)
  (cons key value))

Posted 23/09/2010 by Emmanuel Jacyna in Scheme, SICP

Tagged with , , , , , , , , ,

SICP – Section 2.2.4   Leave a comment

This section is a powerful demonstration of abstraction, using a “picture language”. For this section I used the sicp package from the PLaneT repository in DrScheme. Normally, I just use mzscheme and vim, but apparently you need DrScheme open to use that particular (graphical) package. Anyway, I found it pretty enjoyable, and even made some fractals with it.

;;Exercise 2.44

They could have made this one a little tougher ;)
Telling us to flip the arguments to right-split took any challenge out of it…

(define (up-split painter n)
  (if (= n 0)
      (let ((smaller (up-split painter (- n 1))))
        (below painter (beside smaller smaller)))))

;;Exercise 2.45

We follow the usual patter of making abstractions.

(define (split op1 op2)
  (define (rec painter n)
    (if (= n 0)
        (let ((smaller (rec painter (- n 1))))
          (op1 painter (op2 smaller smaller)))))

(define up-split (split below beside))
(define right-split (split beside below))

;;Exercise 2.46

Not much to it, I used a list, but a cons would do fine too, however, I decided on list, because perhaps we’ll want to add a z coordinate for 3D vectors.

(define (make-myvect x y)
  (list x y))
(define (xcor-myvect vect)
  (car vect))
(define (ycor-myvect vect)
  (cadr vect))

(define (add-myvect a b)
  (make-myvect (+ (xcor-myvect a) (xcor-myvect b))
             (+ (ycor-myvect a) (ycor-myvect b))))

(define (sub-myvect a b)
  (make-myvect (- (xcor-myvect a) (xcor-myvect b))
             (- (ycor-myvect a) (ycor-myvect b))))

(define (scale-myvect s v)
  (make-myvect (* s (xcor-myvect v))
             (* s (ycor-myvect v))))

;;Exercise 2.47

First definition

(define (make-myframe origin edge1 edge2)
  (list origin edge1 edge2))

(define (origin-myframe f) (car f))

(define (edge1-myframe f) (cadr f))

(define (edge2-myframe f) (caddr f))

Second definition

(define (make-myframe origin edge1 edge2)
  (cons origin (cons edge1 edge2)))

(define (origin-myframe f) (car f))

(define (edge1-myframe f) (cadr f))

(define (edge2-myframe f) (cddr f))

;;Exercise 2.48

(define (make-mysegment start end) (cons start end))

(define (start-mysegment seg) (car seg))

(define (end-mysegment seg) (cdr seg))

;;Exercise 2.49

;;a.  The painter that draws the outline of the designated frame.
(define outline (segments->painter (list
  (make-segment (make-vect 0 0)
                (make-vect 0 1))
  (make-segment (make-vect 0 0)
                (make-vect 1 0))
  (make-segment (make-vect .99 0)
                (make-vect .99 1))
  (make-segment (make-vect 0 .99)
                (make-vect 1 .99)))))

;;b.  The painter that draws an ``X'' by connecting opposite corners of the frame.
(define X (segments->painter (list
  (make-segment (make-vect 0 0)
                (make-vect 1 1))
  (make-segment (make-vect 1 0)
                (make-vect 0 1)))))

;;c.  The painter that draws a diamond shape by connecting the midpoints of the sides of the frame.
(define diamond (segments->painter (list
  (make-segment (make-vect 0 .5)
                (make-vect .5 0))
  (make-segment (make-vect .5 0)
                (make-vect 1 .5))
  (make-segment (make-vect 1 .5)
                (make-vect .5 1))
  (make-segment (make-vect .5 1)
                (make-vect 0 .5)))))

;;d.  The wave painter.
(define wave (segments->painter (list
  (make-segment (make-vect 0 .84) (make-vect .13 .6))
  (make-segment (make-vect .13 .6) (make-vect .3 .66))
  (make-segment (make-vect .3 .66) (make-vect .4 .66))
  (make-segment (make-vect .4 .66) (make-vect .36 .84))
  (make-segment (make-vect .36 .84) (make-vect .4 1))
  (make-segment (make-vect .6 1) (make-vect .64 .84))
  (make-segment (make-vect .64 .84) (make-vect .6 .66))
  (make-segment (make-vect .6 .66) (make-vect .71 .66))
  (make-segment (make-vect .71 .66) (make-vect 1 .34))
  (make-segment (make-vect 1 .16) (make-vect .6 .44))
  (make-segment (make-vect .6 .44) (make-vect .74 0))
  (make-segment (make-vect .6 0) (make-vect .5 .3))
  (make-segment (make-vect .5 .3) (make-vect .4 0))
  (make-segment (make-vect .24 0) (make-vect .34 .5))
  (make-segment (make-vect .34 .5) (make-vect .3 .6))
  (make-segment (make-vect .3 .6) (make-vect .14 .4))
  (make-segment (make-vect .14 .4) (make-vect 0 .64)))))

;;Exercise 2.50
The key to figuring these out is to draw a diagram of the unit square, draw the original picture, and then draw the rotated one, and note the coordinates of the origin, edge1, and edge2.

(define (myflip-horiz painter)
  ((transform-painter (make-vect 1 0)
                      (make-vect 0 0)
                      (make-vect 1 1)) painter))

(define (rotate-90 painter)
  ((transform-painter (make-vect 1 0)
                     (make-vect 1 1)
                     (make-vect 0 0)) painter))

(define (rotate-180 painter)
  ((transform-painter (make-vect 1 1)
                      (make-vect 0 1)
                      (make-vect 1 0)) painter))

(define (rotate-270 painter)
  ((transform-painter (make-vect 0 1)
                      (make-vect 0 0)
                      (make-vect 1 1)) painter))

;;Exercise 2.51

(define (my-below painter1 painter2)
  (let ((split-point (make-vect 0 .5)))
    (let ((paint-top
           ((transform-painter split-point
                               (make-vect 1 .5)
                               (make-vect 0 1)) painter1))
           ((transform-painter (make-vect 0 0)
                               (make-vect 1 0)
                               split-point) painter2)))
      (lambda (frame)
        (paint-top frame)
        (paint-bottom frame)))))

(define (my-below2 painter1 painter2)
  (rotate-90 (beside (rotate-270 painter1) (rotate-270 painter2))))

Okay, this has been a pretty boring article… lack of pictures, &c. However, I do have a couple pictures of some nice fractals that I generated with some functions I wrote in this picture language.

The sierpinski painter generates a sierpinski triangle with n iterations using an MRCM (Multiple Reduction Copy Machine) process. This is based on the idea from the book, Computational Beauty of Nature.

(define (sierpinski painter n)
  (if (= n 0)
            (let ((top ((transform-painter (make-vect .25 0)
                      (make-vect .75 0)
                      (make-vect .25 1))
        (sierpinski (below (beside painter painter) top) (- n 1))))) 

And here it is generating it with the einstein painter.

There’s also another neat fractal, which is defined as

(define (crystal painter n)
  (if (= n 0)
            (let ((top ((transform-painter (make-vect .25 0)
                      (make-vect .75 0)
                      (make-vect .25 1))
        (crystal (below (beside (rotate-90 painter)
                                   (rotate-270 painter))
                    (- n 1))))) 

And looks like

As you can see, it’s pretty easy to define MRCM fractals using this picture language.

Posted 24/04/2010 by Emmanuel Jacyna in Code, Scheme, SICP

Tagged with , , , ,

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

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

;;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.

Posted 24/04/2010 by Emmanuel Jacyna in Code, Scheme, SICP

Tagged with , ,

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))))))
> (define b (list (list 7)))
> (display (car (car b)))
> (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)))))))))))))

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

Posted 03/04/2010 by Emmanuel Jacyna in Code, Scheme, SICP

Tagged with , , , ,

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


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

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

Tagged with , , ,

SICP – Section 2.1.4   Leave a comment

I’ve been silent for the past couple days, but not without good reason :)

I decided to finish all my solutions to the interval arithmetic exercise
before posting, because I can share as much insight as I have gained, in one
hit. ;)

In this extended exercise, we are helping Alyssa P. Hacker
(note the pun :)  to develop an interval arithmetic system for
her fellow electrical engineering compatriots.

The answers to exercises 2.7 to 2.10 are fairly clear, so here they are:

Exercise 2.7

(define (make-interval a b) (cons a b))

(define (lower-bound i) (car i))
(define (upper-bound i) (cdr i))

Exercise 2.8

(define (sub-interval x y)
(make-interval (- (lower-bound x) (lower-bound y))
(- (upper-bound x) (upper-bound y))))

Exercise 2.9

Let’s add some intervals and note the relation between the width of the
operands and the width of the result.

(define a (make-center-width 5 1))
(define b (make-center-width 10 2))
(define x (mul-interval a b))
(width x) = 3

From this it is fairly obvious that the width of the result of addition can
be described like so:
w(x*y) = w(x)+w(y)

The inverse holds true of division:
w(x/y) = w(x)-w(y)

Hmm… anyone else see the relation to logarithms?

Exercise 2.10
This one is also fairly simple.

(define (zero-span? i)
(if (and (<= (lower-bound i) 0) (>= (upper-bound i) 0))

(define (div-interval x y)
(if (zero-span? y)
(error "Attempt to divide by an interval that spans 0")
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y))))))

Exercise 2.11

To be honest, I didn’t get Ben’s cryptic comment. After reading
Eli Bendersky’s post on the topic I understood, but previously I had
gone off on a wrong tangent.

Regarding this, let me state my policy regarding my completion of these exercises. I firmly believe that cheating cheats the cheater, and while it is not necessarily cheating to check an answer to get hints, this is usually not necessary. There have been a few exercises where I have encountered a mindblock, but my advice to others is to go do something else, completely unrelated to computing or using your brain. Hop on your bike, go for a run or eat a pie, whatever works for you :) Usually when you get a mindblock it shows that you’ve been working your brain too long, too hard, and you just need to let it relax. This also happens a bit in programming, at least when you’re starting out, and in “How To Think Like A Computer Scientist” the author also suggests taking a break when you get frustrated, as this can be a source of unpleasant code and bugs.

I tend to read Eli’s posts after completing a section, because they are quite enlightening and informative. There is nothing quite like a veteran hackers view of the topic :)

This leads me to a shout out to Eli. Thanks for writing such detailed, interesting, and informative posts! I believe that, along with watching the lectures, doing the exercises and reading the book, your posts are a very complementary aid in understanding the material.

Exercise 2.12

(define (make-center-percent c p)
(make-interval (- c (* c p))
(+ c (* c p))))

(define (percent i)
(/ (- (upper-bound i)
(center i))
(center i)))

Again, this is fairly simple. The percent selector may have caused
some trouble, but it’s not too hard to figure out.

Exercise 2.13

;;Let's try:
(define a (make-center-percent 1 .1))
(define b (make-center-percent 1 .2))
(define x (* a b))
(percent x)

So we can indeed see that (percent x) ~= (percent a) + (percent b)
This follows from exercise 2.9, except here we see that the percentage
is only approximate.

Exercise 2.14

To show why, we will use:

(define A (make-center-percent 8 .01))
(define B (make-center-percent 9 .05))

We will process A/A by hand, in order to see what’s going on.

(mul-interval A (make-interval (/ 1 8.08) (/ 1 7.92)))
;;p1 = .980
;;p2 = 1
;;p3 = 1
;;p4 = 1.02

The result is: (make-interval .980 1.02)
Instead of (make-interval 1 1) which you might have expected.

Let’s also do (/ A B) as suggested

;;(mul-interval A (make-interval (/ 1 9.45) (/ 1 (8.55))))
;;p1 = .838
;;p2 = .926
;;p3 = .855
;;p4 = .945

So the result is: (make-interval .838 .945) instead of the more accurate
(make-interval .855 .926)

Here’s my explanation.

Interval A/A is not an interval spanning 1 <-> 1 as we would expect in normal arithmetic, but an interval spanning .980 <-> 1.02. The width of this interval is a factor of the initial uncertainty .01, where the new uncertainty is .04. Interval A/B is also not the .855 <-> .926 that we might expect, but instead .838 <-> .945. We can see from these examples that arithmetic operations increase the innacuracy/uncertainty of the answer. The error in the answer is therefore directly related to the uncertainty in the intervals given.

Exercise 2.15

She is correct. As stated above, the amount of error in the answer is directly related to the uncertainty in the intervals given. Because there are more intervals in par1, there is a higher error in the answer. That is why par2 is a better method.

Reading Eli’s solutions to this extended exercise also gives a different view on the matter, he talks about it in terms of the fact that interval arithmetic is not a one-to-one mapping of simple numerical arithmetic.

Posted 27/03/2010 by Emmanuel Jacyna in Code, Scheme, SICP

Tagged with , , ,