Finish Chapter 1 of SICP

2 files changed, 141 insertions, 0 deletions

diff --git a/sicp/scratch.rkt b/sicp/chapter1.rkt
index 298d42d..76716f7 100644
--- a/sicp/scratch.rkt
+++ b/sicp/chapter1.rkt
@@ -214,6 +214,7 @@
 (define (sum-cubes a b) (sum cube a inc b))
 (define (pi-sum a b)
   (sum (lambda (x) (/ 1.0 x (+ x 2))) a (lambda (x) (+ x 4)) b))
+(define dx 0.00001)
 (define (integral f a b dx)
   (* (sum f (+ a (/ dx 2.0)) (lambda (x) (+ x dx)) b) dx))
 
@@ -303,3 +304,91 @@
           ((and (negative? b-value) (positive? a-value))
            (search f b a))
           (else (error "Values are not of opposite sign" a b)))))
+
+(define (fixed-point f first-guess)
+  (define (try guess)
+    (let ((next (f guess)))
+      (if (good-enough? guess next) next (try next))))
+  (try first-guess))
+
+(define (sqrt-fixed x)
+  (fixed-point (lambda (y) (average y (/ x y))) 1.0))
+
+; Exercise 1.35
+(define golden-ratio (fixed-point (lambda (x) (inc (/ x))) 1.0))
+
+; Exercise 1.37
+(define (cont-frac-recursive n d k)
+  (define (cont-frac n d k root)
+    (if (= k 0)
+        root
+        (cont-frac n d (dec k) (/ (n k) (+ (d k) root)))))
+  (if (> k 0)
+      (cont-frac n d (dec k) (/ (n k) (d k)))
+      (error "You weirdo!")))
+(define (cont-frac-iterative n d k)
+  (define (cont-frac n d k c)
+    (if (< c k)
+        (/ (n c) (+ (d c) (cont-frac n d k (inc c))))
+        (/ (n k) (d k)))) ; UB if k is not a positive integer
+  (cont-frac n d k 1))
+
+; Exercise 1.38
+(define (e-2 precision)
+  (cont-frac-iterative
+   (lambda (i) 1.0)
+   (lambda (i) (if (= (remainder i 3) 2) (* (inc i) 2/3) 1.0))
+   precision))
+
+; Exercise 1.39
+(define (tan-cf x k)
+  (cont-frac-iterative
+   (lambda (i) (if (= i 1) x (square x)))
+   (lambda (i) ((if (even? i) - +) (dec (* i 2))))
+   k))
+
+(define (average-damp f) (lambda (x) (average x (f x))))
+(define (newton-method g guess)
+  (define (deriv g)
+    (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))
+  (let ((f (lambda (x) (- x (/ (g x) ((deriv g) x))))))
+    (fixed-point f guess)))
+
+(define (fixed-point-of-transform g transform guess)
+  (fixed-point (transform g) guess))
+
+; Exercise 1.40
+(define (cubic a b c)
+  (lambda (x) (+ (cube x) (* (square x) a) (* x b) c)))
+
+; Exercise 1.41
+(define (duplicate f) (lambda (x) (f (f x))))
+
+; Exercise 1.42
+(define (compose f g) (lambda (x) (f (g x))))
+
+; Exercise 1.43
+(define (repeated f times)
+  (cond ((< times 1) identity)
+        ((= times 1) f)
+        (else (compose f (repeated f (dec times))))))
+
+; Exercise 1.44
+(define (smooth f)
+  (lambda (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3)))
+(define (repeated-smooth f times) (repeated smooth times))
+
+; Exercise 1.45
+(define (root n x)
+  (fixed-point-of-transform
+   (lambda (y) (/ x (expt y (dec n))))
+   (repeated average-damp (log n 2))
+   1.0))
+
+; Exercise 1.46
+(define (iter-improve good-enough improve)
+  (lambda (x)
+    (let ((xim (improve x)))
+      (if (good-enough x xim)
+          xim
+          ((iter-improve good-enough improve) xim)))))
diff --git a/sicp/chapter2.rkt b/sicp/chapter2.rkt
new file mode 100644
index 0000000..2915203
--- /dev/null
+++ b/sicp/chapter2.rkt
@@ -0,0 +1,52 @@
+#lang sicp
+; Exercise 2.1
+(define (make-rat n d)
+  (if (< d 0)
+      (make-rat (- n) (- d))
+      (let ((g (gcd n d)))
+        (cons (/ n g) (/ d g)))))
+(define numer car)
+(define denom cdr)
+(define (print-rat x)
+  (display (numer x))
+  (display "/")
+  (display (denom x))
+  (newline))
+(define (add-rat x y)
+  (let ((dx (denom x))
+        (dy (denom y)))
+    (make-rat (+ (* (numer x) dy)
+                 (* (numer y) dx))
+              (* dx dy))))
+(define (sub-rat x y)
+  (add-rat x (make-rat (- (numer y)) (denom y))))
+(define (mul-rat x y)
+  (make-rat (* (numer x) (numer y))
+            (* (denom x) (denom y))))
+(define (div-rat x y)
+  (make-rat (* (numer x) (denom y))
+            (* (denom x) (numer y))))
+(define (equal-rat? x y)
+  (= (* (numer x) (denom y))
+     (* (numer y) (denom x))))
+
+; Exercise 2.2
+(define make-point cons)
+(define x-point car)
+(define y-point cdr)
+(define make-segment cons)
+(define start-segment car)
+(define end-segment cdr)
+(define (average x y) (/ (+ x y) 2))
+(define (midpoint-segment d)
+  (let ((A (start-segment d))
+        (B (end-segment d)))
+    (make-point (average (x-point A) (x-point B))
+                (average (y-point A) (y-point B)))))
+(define (print-point P)
+  (display "(")
+  (display (x-point P))
+  (display ", ")
+  (display (y-point P))
+  (display ")")
+  (newline))