Explore Posterous

this one busted me up a bit today

;exercise 2.20 - return numbers of same parity, arbitrary number of arguments 
(define (same-parity . x) 
  (define (parity y) 
   (modulo y 2)) 
  (define (same-parity-recur x) 
   (cond ((null? (cdr x)) 
      x) 
      ((= (parity (car x)) 
        (parity (car (cdr x)))) 
      (cons (car x) (same-parity-recur (cdr x)))) 
      (else 
      (same-parity-recur (cons (car x) (cdr (cdr x))))))) 
   (same-parity-recur x)) 

although the ". x" takes a variable number of arguments and turns it into a list, it does not mean that you can pass in a list and have it do the right thing. and as far as i can tell, you can't decompose a list into atoms (since a function can't return more than one atom).
 
so therefore i have my hacky wrapper around what i think is a reasonably clever implementation of this, which results in:

(same-parity 1 2 3 4 5 6 7) 
(1 3 5 7) 
 
(same-parity 2 3 4 5 6 7) 
(2 4 6)

anyone have better suggestions? i probably [hopefully] just have a few gaps in my knowledge of scheme right now...

Fried noodles

well, specifically one: mine. not far beyond my last post, i encountered this piece of brain melter, in which we define zero in terms of a procedure and the positive integers from that:

 (define zero (lambda (f) (lambda (x) x)))
 (define (add-1 n)
   (lambda (f) (lambda (x) (f ((n f) x)))))
 

substitution helps to figure it out:

 (add-1 zero)
 (add-1 (lambda (g) (lambda (y) y)))
 (lambda (f) (lambda (x) (f (((lambda (g) (lambda (y) y)) f) x))))
 (lambda (f) (lambda (x) (f x)))
 

therefore, we can now define one, two, and plus in this manner (plus is hard, i will admit that i didn't get it right on my own)

 (define one (lambda (f) (lambda (x) (f x))))
 (define two (lambda (f) (lambda (x) (f (f x)))))
 (define plus (m n) (lambda (f) (lambda (x) ((m f) ((n f) x)))))
 

fascinating stuff, i'm off to read more.

Mind blowing

(define (cons x y) 
 (define (dispatch m) 
  (cond ((= m 0) x) 
     ((= m 1) y) 
     (else (error "Argument not 0 or 1 -- CONS" m)))) 
 dispatch) 
 
(define (car z) (z 0)) 
 
(define (cdr z) (z 1)) 

or even more crazy:

(define (cons x y) 
 (lambda (m) (m x y))) 
 
(define (car z) 
 (z (lambda (p q) p))) 
 
(define (cdr z) 
 (z (lambda (p q) q))) 

i've always been quick to criticize theory. i guess what i needed was
to find some theory that i found fascinating and enlightening.

SICP exercises 1.14 and 1.15 are now commited and other randomness

I did 1.14 in Open Office Draw, which turned out to be a bad idea. I really should have used graphviz to make the tree, and will probably go back and do it in graphviz anyways. Oh well. There are a lot of things I am not really liking about Draw and this problem would have been way easier to do in graphviz. A Draw like program for making diagrams and wireframes is nice sometimes, but Draw itself feels cumbersome. I will be in search of a better application for that purpose.
 
Today I realized that I need new music and in my search remembered http://www.thesixtyone.com/. Last year I signed up with an account and never used it. Now I've used the site a bit and so far I like it. The UI is a bit weird at first, and I was having trouble finding things. Some things about the site aren't really intuitive. I also don't like the modal box that pops up after ever new song when you are listening to songs on the rack. That being said so far the music is new and decent. I want to build up some status on the site to see what sort of recommendations I get. I've noticed that sites like last.fm (while a pretty awesome idea) recommend me stuff that I don't really like or I already listen to. Hopefully the sixty one will be better than that.
 
During my SICP quest I learned about successive squaring today. Successive squaring is defined as if n is even and if n is odd. This quickens things up when finding exponents.

Found a group on HN to go through SICP with

It is completely coincidence that I started going through the SICP course right before a group has been established on Hacker News. I'm really happy that people are interested in going through the course as a group. It's not really that I am unmotivated to work alone, but being able to talk to people who are around the same chapter and doing the same exercises should prove to be helpful.
 
It is my hope that after this course a similar group will form that wants to go through the MIT Intro to Algorithms course. There have been a couple people on the sicp irc channel that have expressed some interest, so hopefully we can make something of that.
 
What I really like about working in groups is that it also gives things a schedule. As nice as it is to work at your own pace having a schedule that you stick to can be useful as well. I'm ahead of the schedule now, and am going to try to stay ahead. I don't think I've ever been so excited to do homework before. Going through the exercises is pretty fun. I just finished up the Pascal's triangle one which took a bit of thinking. It ended up being really simple, but for some reason I was over thinking it. After some really bad attempts I had to stop myself and just let it sit for a while. I then went back to it today and read the mathematical instructions, and just transfered that over to Scheme. That took about 5 minutes. I guess when you have been working too hard you just need to let a problem sit instead of banging your head against the wall over and over. In this case the problem was really simple and I just was trying to rush through it.
 
Here is the answer that I came up with:
http://github.com/emkay/sicp-exercises/tree/master/chapter1/ex1-12.ss

SICP exercises now on Github

I've realized that blog posts are a less than ideal way to keep track of code exercises. This being the case I've decided to keep track of them with git. You can follow it at github if you like.
 
http://github.com/emkay/sicp-exercises/tree/master
 
git://github.com/emkay/sicp-exercises.git

SICP Exercise 1.11

Recursive:
 
(define (rf n)
  (if (< n 3)
  n
  (+ (rf (- n 1))
   (* 2 (rf (- n 2)))
   (* 3 (rf (- n 3))))))
 
Iterative:
 
(define (f n)
  (if (< n 3)
  n
  (f-iter 0 1 2 n)))
 
(define (f-iter a b c counter)
  (if (= 0 counter)
  a
  (f-iter b c (+ c (* 2 b) (* 3 a)) (- counter 1))))
 
The iterative one took me a while to figure out. Every time I started I kept reverting back to recursive thinking.

SICP Exercise 1.10

 
 > (A 1 10)
1024
 > (A 2 4)
65536
 > (A 3 3)
65536
 
(f n) computes 2n.
 
The next two problems I had trouble on. I am no math wizard. I initially came up with:
  (g n) computes to 2(A(1, n - 1))
and figured that I had the wrong notation and that the answer wasn't really completed because A(1, n -1) makes another recursive call. What I didn't intuitively realize was that this is really 2^n.
 
(h n)
Same thing with this one the answer is 2^h(n-1).
 
I found the answer to these both at: http://community.schemewiki.org/?sicp-ex-1.10
 
Although I am trying to go through these myself I had trouble grasping these ones, but now get it. I also got to read the Ackermann's function Wikipedia entry.

SICP Exercise 1.9

(define (+ a b)
  (if (= a 0)
  b
  (inc (+ (dec a) b))))
 
(+ 4 5)
(inc (+ (dec 4) 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (inc (+ 0 5))))))
 
This process is recursive.
 
 
(define (+ a b)
  (if (= a 0)
  b
  (+ (dec a) (inc b))))
 
(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8)
(+ (dec 1) (inc 8))
(+ 0 9)
9
 
This process is iterative.

SICP Exercises 1.6 - 1.8

1.6
IF is a special form, meaning that it does not apply the operator (IF) to all of the opperands. New-if however does apply the operator to all the operands and because of the recursive call to (sqrt-iter) it never ends.
 
1.7
Running (sqrt 1000000000000000) takes an extremely long time to finish (I stopped it so don't really know if it actually does finish). (sqrt 0.00001) produces the result 0.008235 when the correct answer is 0.003162. Changing good-enough? to
 
(define (good-enough? guess x)
  (< (abs (- guess (improve guess x))) .0001))
 
improves things with both large and small numbers and I get these results when plugging in the same numbers:
 
 > (sqrt 0.00001)
0.003172028655357483
 > (sqrt 1000000000000000)
31622776.601683907
 >
 
1.8
$ cat ex1-8.ss
(define (square x)
  (* x x))
 
(define (cube x)
  (* x x x))
 
(define (improve guess x)
  (/ (/ x (+ (square guess) (* 2 guess))) 3))
 
(define (good-enough? guess x)
  (< (abs (- (cube guess) x)) 0.0001))
 
(define (cubert-iter guess x)
  (if (good-enough? guess x )
   guess
   (cubert-iter (improve guess x)
   x)))
 
(define (cubert x)
  (cubert-iter 1.0 x))