All code available on GitHub. Drawings/diagrams available here.
19 days after starting, I’m done with Chapter 1!
Exercise 1.36 in this chapter was pretty interesting - we have to find a solution to x^x = 1000 by finding a fixed point of x -> log(1000)/log(x). I modified fixed-point using the https://github.com/weavejester/hashp #p data reader to print out intermediate values, which makes println-style debugging a lot better.
(def tolerance 1E-5)
(defn fixed-point [f first-guess]
(let [close-enough? (fn [v1 v2] (< (Math/abs ^float (- v1 v2)) tolerance))
try* (fn [guess steps] (let [next #p (f guess)]
(if (close-enough? guess next)
(do (print (str "took " steps " steps, guess=" guess))
next)
(recur next (inc steps)))))]
(try* first-guess 0)))
(defn undampened-x-pow-x [x] (/ (Math/log 1000) (Math/log ^float x)))
(float (fixed-point undampened-x-pow-x 2))
;; took 28 steps
;; 4.5555634
(float (fixed-point #(/ (+ (undampened-x-pow-x %) %) 2) 2))
;; took 7 steps
;; 4.5555468
;; no oscillation at the start; nice!
The rest of the exercises really served to hammer home the point that it’s easy and fun to build higher-level abstractions using first-class functions and some thinking. Just contrast the initial and final implementations of sqrt below:
;; initial version
(defn sqrt-iter [guess x]
(letfn [(good-enough? [guess x]
(< (Math/abs ^float (- (* guess guess) x))
0.001))
(average [x y]
(/ (+ x y) 2))
(improve [guess x]
(average guess (/ x guess)))]
(if (good-enough? guess x) guess
(re cur (improve guess x) x))))
;; final version
(defn sqrt-final [num]
(let [guesser (iterative-improver
(fn [a b] (< (Math/abs ^float (- a b))
0.001))
(fn [guess] (sicp.util/average guess (/ num guess))))]
(guesser 1)))
;; Where iterative-improver is from Exercise 1.46:
(defn iterative-improver [test-fn improve-fn]
(fn [guess] (let [improved-guess (improve-fn guess)
good-enough? (test-fn guess improved-guess)]
(if good-enough? improved-guess
(recur improved-guess)))))