src/main/clojure/sicp/ch1_1.clj

   1 (ns sicp.ch1-1)
   2
   3 (defn square [x] (* x x))
   4
   5 (defn sum-of-squares [x y]
   6   (+ (square x) (square y)))
   7
   8 (defn f [a]
   9   (sum-of-squares (+ a 1) (* a 2)))
  10
  11 (defn abs
  12   "find absolute value of x"
  13   [x]
  14   (if (< x 0) (- x) x))
  15
  16 (defn abs1 [x]
  17   (cond (< x 0) (- x)
  18         :else x))
  19
  20 ;; exercise 1.1: What is the result printed by the interpreter in response
  21 ;;               to each expression (in order) ?
  22
  23 (def a 3)
  24 (def b (+ a 1))
  25
  26 (+ a b (* a b))  ; 19
  27 (= a b) ; false
  28
  29 (if (and (> b a) (< b (* a b)))
  30     b
  31     a)   ; 4
  32
  33 (cond (= a 4) 6
  34       (= b 4) (+ 6 7 a)
  35       :else 25)  ; 16
  36
  37 (+ 2 (if (> b a) b a)) ; 6
  38
  39 (* (cond (> a b) a
  40          (< a b) b
  41          :else -1)
  42    (+ a 1))      ; 16
  43
  44 ;; exercise 1.2: Translate the given expression into prefix form
  45 (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 1 5)))))
  46    (* 3 (- 6 2) (- 2 7)))  ; -71/300
  47
  48 ;; exercise 1.3:  Define a procedure that takes three numbers as
  49 ;;                arguments and returns the sum of the squares of
  50 ;;                the two larger numbers.
  51 (defn sort3 [a b c]
  52   (cond (> b a) (sort3 b a c)
  53         (< b c) (sort3 a c b)
  54         :else [a b c]))
  55
  56 (defn sum-of-sq-of-two-largest [a b c]
  57   (apply sum-of-squares (take 2 (sort3 a b c))))
  58
  59 ;; well, I cheated above. Let me use only the constructs introduced
  60 ;; so far in the book. (follows after the sicp meetup #2 on 28/mar/2010.
  61 (defn sum-of-square-of-two-largest [a b c]
  62   (if (> a b)
  63     (if (> b c)
  64       (sum-of-squares a b) ; a > b > c
  65       (sum-of-squares a c))
  66     (if (> a c)
  67       (sum-of-squares b a)
  68       (sum-of-squares b c))))
  69
  70 ;; exercise 1.4: Observe that our model of evaluation allows for
  71 ;;               combinations whose operators are compound
  72 ;;               expressions. Use this observation to describe the
  73 ;;               behavior of the following procedure:
  74 ;; (defn a-plus-abs-b [a b]
  75 ;;   ((if (> b 0) + -) a b))
  76 (comment
  77   If b is positive, we do (+ a b) and if it is negative, we do (- a b).
  78   This makes use of the fact that the first element in a list is an
  79   operand. Here, the operand is chosen based on other operators.
  80   )
  81
  82 ;; exercise 1.5:  Ben Bitdiddle has invented a test to determine
  83 ;;                whether the interpreter he is faced with is
  84 ;;                using applicative-order evaluation or normal-order
  85 ;;                evaluation. He defines the following two procedures:
  86 ;; (defn p [] (p))
  87 ;; (defn test [x y]
  88 ;;   (if (= x 0)
  89 ;;    0
  90 ;;    y))
  91 ;;
  92 ;; Then he evaluates the expression
  93 ;;
  94 ;; (test 0 (p))
  95 ;;
  96 ;; What behavior will Ben observe with an interpreter that uses
  97 ;; applicative-order evaluation?
  98 (comment
  99   In the case of applicative order evaluation, the test gets into
 100   and infinite loop (eventually using all the stack), as the parameters
 101   are evaluated before they are actualy used in the function.
 102   )
 103 ;; What behavior will he observe with an interpreter that uses
 104 ;; normal-order evaluation? Explain your answer.
 105 (comment
 106   It will print 0, as (p) is not evaluated in this case.
 107   )
 108
 109 ;; 1.1.7 Square root finding using Newton's method
 110 (defn average [x y]
 111   (/ (+ x y) 2))
 112
 113 (defn improve [guess x]
 114   (average guess (/ x guess)))
 115
 116 (defn good-enough? [guess x]
 117   (< (abs (- (square guess) x)) 0.001))
 118
 119 (defn sqrt-iter [guess x]
 120   (if (good-enough? guess x)
 121     guess
 122     (sqrt-iter (improve guess x)
 123                x)))
 124
 125 (defn sqrt [x]
 126   (sqrt-iter 1.0 x))
 127
 128 ;; exercise 1.6
 129 ;; Alyssa P. Hacker doesn't see why if needs to be provided as a special form.
 130 ;; ``Why can't I just define it as an ordinary procedure in terms of cond?''
 131 (defn new-if [predicate then-clause else-clause]
 132   (cond predicate then-clause
 133         :else else-clause))
 134
 135 (new-if (= 3 2) 0 5)  ; 5
 136 (new-if (= 1 1) 0 5)  ; 0
 137
 138 ;; Delighted, Alyssa uses new-if to rewrite the square-root program:
 139
 140 (defn sqrt-iter [guess x]
 141   (new-if (good-enough? guess x)
 142           guess
 143           (sqrt-iter (improve guess x)
 144                      x)))
 145
 146 ;; what happens when Alyssa attempts to use this to compute square roots? Explain.
 147 (comment
 148   Since `new-if' is a function, when it is called from sqrt-iter, the parameters
 149   are evaluated before it gets called. good-enough? will return a false unless
 150   the guess and x are almost the same. guess evaluated to the initial value of
 151   guess. sqrt-iter gets evaluated, but gets into an infinite loop. The predicate
 152   will have no effect.)
 153
 154 ;; Exercise 1.7: The good-enough? test used in computing square roots will not
 155 ;; be very effective for finding the square roots of very small numbers. Also,
 156 ;; in real computers, arithmetic operations are almost always performed with
 157 ;; limited precision. This makes our test inadequate for very large numbers.
 158 ;; Explain these statements, with examples showing how the test fails for small
 159 ;; and large numbers.
 160 (comment
 161  user> (sqrt (square 0.001))
 162  0.031260655525445276
 163  user> (sqrt (square 0.2))
 164  0.20060990407779591
 165  user> (sqrt (square 0.01))
 166  0.03230844833048122
 167  user> (sqrt (square 0.02))
 168  0.0354008825558513
 169  user> (sqrt (square 10))
 170  10.000000000139897
 171  user> (sqrt (square 100))
 172  100.00000025490743
 173  user> (sqrt (square 200))
 174  200.000000510076
 175  user> (sqrt (square 2))
 176  2.0000000929222947
 177  user> (sqrt (square 0.1))
 178  0.10032578510960607
 179  user> (sqrt (square 0.01))
 180  0.03230844833048122
 181  user> (sqrt (square 10000))
 182  10000.0
 183  user> (sqrt (square 20000))
 184  20000.0
 185  user> (sqrt (square 200000))
 186  200000.0
 187  user> (sqrt (square 20000000))
 188  2.0E7
 189  user> (sqrt (square 20000000000))
 190  2.0E10
 191  user> (sqrt (square 200000.012))
 192  200000.012
 193  user> (sqrt (square 2000000.123))
 194  2000000.123
 195  user> (sqrt (square 200000000.123))
 196  2.00000000123E8
 197  user> (sqrt (square 2000000000.123))
 198  2.000000000123E9
 199  user> (sqrt (square 20000000000.123))
 200  2.0000000000123E10
 201  user> (sqrt (square 2000000000000.123))
 202  2.000000000000123E12
 203  )
 204 ;; An alternative strategy for implementing good-enough? is to watch how guess
 205 ;; changes from one iteration to the next and to stop when the change is a very
 206 ;; small fraction of the guess.
 207 (defn sqrt-iter [old-guess new-guess x]
 208   (if (good-enough? old-guess new-guess x)
 209     new-guess
 210     (sqrt-iter new-guess (improve new-guess x)
 211                x)))
 212
 213 (defn improve [guess x]
 214   (average guess (/ x guess)))
 215
 216 (defn average [x y]
 217   (/ (+ x y) 2))
 218
 219 (defn good-enough? [old-guess new-guess x]
 220   (< (/ (abs (- new-guess old-guess)) new-guess) 0.0001))
 221
 222 (defn sqrt [x]
 223   (sqrt-iter x 1.0 x))
 224 (comment
 225 user> (sqrt (square 0.01))
 226 0.010000000025490743
 227 user> (sqrt (square 0.001))
 228 0.0010000000000000117
 229 user> (sqrt (square 0.0001))
 230 1.0000000000082464E-4
 231 user> (sqrt (square 0.02))
 232 0.020000000050877154
 233 user> (sqrt (square 0.002))
 234 0.0020000000000000235
 235 user> (sqrt (square 4))
 236 4.000000000000051
 237 user> (sqrt (square 20))
 238 20.000000000298428
 239 user> (sqrt (square 25))
 240 25.000000063076968
 241 user> (sqrt 5)
 242 2.236067977499978
 243 user> (sqrt 25)
 244 5.000000000053722
 245 user> (sqrt 9)
 246 3.000000001396984
 247 user> (sqrt 81)
 248 9.000000000007091
 249 )
 250 ;; exercise 1.8: cube root
 251 (defn cube [x]
 252   (* x x x))
 253
 254 (defn improve [guess x]
 255   (/ (+ (/ x (square guess)) (* 2 guess)) 3))
 256
 257 (defn cubert-iter [old-guess new-guess x]
 258   (if (good-enough? old-guess new-guess x)
 259     new-guess
 260     (cubert-iter new-guess (improve new-guess x)
 261                  x)))
 262
 263 (defn cuberoot [x]
 264   (cubert-iter x 1.0 x))
 265
 266 (comment
 267 user> (cuberoot (cube 2))
 268 2.000000000012062
 269 user> (cuberoot (cube 10))
 270 10.000000000000002
 271 user> (cuberoot (cube 9))
 272 9.000000000053902
 273 user> (cuberoot (cube 0.001))
 274 0.001000000000000962
 275 user> (cuberoot (cube 0.0001))
 276 1.000000000000001E-4
 277 user>
 278 )
 279 ;; section 1.1.8
 280 ;; hiding the non-public procedure definitions
 281 (defn- sqrt-iter [guess x]
 282   (if (good-enough? guess x)
 283     guess
 284     (sqrt-iter (improve guess x)
 285                x)))
 286
 287 (defn- improve [guess x]
 288   (average guess (/ x guess)))
 289
 290 (defn- average [x y]
 291   (/ (+ x y) 2))
 292
 293 (defn- good-enough? [guess x]
 294   (< (abs (- (square guess) x)) 0.001))
 295
 296 (defn sqrt [x]
 297   (sqrt-iter 1.0 x))