Coding just likes Art

This is the blog about the coding, the whole coding and nothing but the coding , so God would help me become a better developer.

SanCoder's Blog home

SICP Exercise Results

1 1. Building Abstractions with Procedures

1.1 Exercise 1.1

(list 10
      (+ 5 3 4)
      (- 9 1)
      (/ 6 2)
      (+ (* 2 4) (- 4 6))
      )

(define a 3)
(define b (+ a 1))
(list (+ a b (* a b))
      (= a b)
      (if (and (> b a) (< b (* a b)))
          b
          a)
      (cond ((= a 4) 6)
            ((= b 4) (+ 6 7 a))
            (else 25))
      (+ 2 (if (> b a) b a))
      (* (cond ((> a b) a)
               ((< a b) b)
               (else -1))
         (+ a 1)))

1.2 Exercise 1.2

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
   (* 3 (- 6 2) (- 2 7)))

1.3 Exercise 1.3

(define (func a b c)
  (if (> a b)
      (if (> b c)
          (+ a b)
          (+ a c))
      (if (> a c)
          (+ a b)
          (+ b c))))
(func 4 2 3)

1.4 Exercise 1.4

1.5 Exercise 1.5

(define (q) (q))

This line means to define a non-parameter recursive function. So once it be evaluated, the complier will go into a endless loop.
The difference between normal order and applicative order is the first one will not eval anything before all the expression is expanded.
So in this exercise, if the complier is using the applicative order to interpreter the code, it will crash.
Another interest thing is if syntax. It's a high level structor with a specific process which means there is only one of the expression will be evaluated whatever the predicate is. Hence, if the coplier is using the normal order, the result will be 0.

1.6 Exercise 1.6

Same reason as the Exercise 1.6, the new-if is using the cond syntax, and it will evaluate the predicate and the follow expression at the same time. So it should not be used to stop a recursive process.

1.7 Exercise 1.7

(define (improve guess x)
  (/ (+ guess (/ x guess)) 2))

(define (abs x)
  (if (< x 0)
      (- x)
      x))

(define (good-enough? guess last-guess)
  (if (< (abs (- (/ guess last-guess) 1)) 0.01)
      #t
      #f))

(define (sqrt-iter guess last-guess x)
  (if (= x 0)
      0
      (if (good-enough? guess last-guess)
          guess
          (sqrt-iter (improve guess x) guess x))))

(define (my-sqrt x)
  (sqrt-iter 1.0 x x))

(list
 (my-sqrt 10000)
 (my-sqrt 100)
 (my-sqrt 0.0001)
 (my-sqrt 0))

1.8 Exercise 1.8

(define (improve guess x)
  (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))

(define (abs x)
  (if (< x 0)
      (- x)
      x))

(define (good-enough? guess last-guess)
  (if (< (abs (- (/ guess last-guess) 1)) 0.01)
      #t
      #f))

(define (cube-iter guess last-guess x)
  (if (= x 0)
      0
      (if (good-enough? guess last-guess)
          guess
          (cube-iter (improve guess x) guess x))))

(define (my-cube x)
  (cube-iter 1.0 x x))

(list
 (my-cube 1000000)
 (my-cube 27)
 (my-cube 0.001)
 (my-cube 0))

1.9 Exercise 1.9

(define (inc x)
  (+ x 1))

(define (dec x)
  (- x 1))

(define (mplus1 a b)
  (if (= a 0)
      b
      (inc (mplus1 (dec a) b))))

(define (mplus2 a b)
  (if (= a 0)
      b
      (mplus2 (dec a) (inc b))))

(list (list (mplus1 4 5)
            (inc (mplus1 3 5))
            (inc (inc (mplus1 2 5)))
            (inc (inc (inc (mplus1 1 5))))
            (inc (inc (inc (inc (mplus1 0 5)))))
            (inc (inc (inc (inc 5))))
            (inc (inc (inc 6)))
            (inc (inc 7))
            (inc 8)
            9)

      (list (mplus2 4 5)
            (mplus2 3 6)
            (mplus2 2 7)
            (mplus2 1 8)
            (mplus2 0 9)
            9))

1.10 Exercise 1.10

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

(define (f n) (A 0 n))  ;;2y

(define (g n) (A 1 n))  ;;2^n

(define (h n) (A 2 n))  ;;2^(2^n)

(list (A 1 10)
      (A 2 4)
      (A 3 3))

1.11 Exercise 1.11

Tree Recursion

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3))))))

(list (f 2)
      (f 3)
      (f 4)
      (f 5)
      (f 6)
      (f 7)
      (f 8)
      (f 9))

Iteration Recursion

(define (iter-f c lc llc n)
  (cond ((< n 2) n)
        ((= n 2) c)
        (else (iter-f (+ c (* 2 lc) (* 3 llc))
                      c
                      lc
                      (- n 1)))))

(define (f n)
  (iter-f 2 1 0 n))

(list (f 2)
      (f 3)
      (f 4)
      (f 5)
      (f 6)
      (f 7)
      (f 8)
      (f 9))

1.12 Exercise 1.12

(define (pp n i)
  (if (or (= n i) (= i 1))
      1
      (+ (pp (- n 1) (- i 1))
         (pp (- n 1) i))))

(define (iter-p l i n)
  (if (< i n)
      (iter-p (cons (pp n (+ i 1)) l)
              (+ i 1)
              n)
      l))

(define (p n)
  (iter-p (list (pp n 1))
          1
          n))

(list (p 2)
      (p 3)
      (p 4)
      (p 5)
      (p 6))

1.13 Exercise 1.13 1.14 1.15

What the hell!

1.14 Exercise 1.16

(define (even? n)
  (= (remainder n 2) 0))

(define (square n)
  (* n n))

(define (fast-expt-iter a b n)
  (cond ((= n 0) a)
        ((even? n) (fast-expt-iter a (square b) (/ n 2)))
        (else (fast-expt-iter (* a b) b (- n 1)))))

(define (fast-expt b n)
  (fast-expt-iter 1 b n))

(list (fast-expt 2 5)
      (fast-expt 2 8)
      (fast-expt 2 10)
      (fast-expt 2 11))

1.15 Exercise 1.17 1.18

Using commutation law

(define (even? n)
  (= (remainder n 2) 0))

(define (double n)
  (+ n n))

(define (halve n)
  (/ n 2))

(define (fast-mult-iter a b n)
  (cond ((= n 0) a)
        ((even? n) (fast-mult-iter a (double b) (halve n)))
        (else (fast-mult-iter (+ a b) b (- n 1)))))

(define (fast-mult b n)
  (if (< b n)
      (fast-mult-iter 0 n b)
      (fast-mult-iter 0 b n)))

(list (fast-mult 3 7)
      (fast-mult 5 9)
      (fast-mult 19 111)
      (fast-mult 111 19))

1.16 exercise 1.19

q <- q^2^nil + 2pq
p <- p^2 + q^2

(define (even? n)
  (= (remainder n 2) 0))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count) (fib-iter a
                                 b
                                 (+ (* p p) (* q q))
                                 (+ (* 2 p q) (* q q))
                                 (/ count 2)))
        (else (fib-iter (+ (* b q) (* a (+ p q)))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

(define (fib n)
  (fib-iter 1 0 0 1 n))

(list (fib 1)
      (fib 2)
      (fib 3)
      (fib 4)
      (fib 5)
      (fib 6)
      (fib 7))

1.17 Exercise 1.20

正则序:

(list (gcd 206 40)
      (gcd 40 (remainder 206 40))
      (gcd (remainder 206 40) (remainder 40 (remainder 206 40)))
      (gcd (remainder 40 (remainder 206 40))
           (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
      (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
           (remainder (remainder 40 (remainder 206 40))
                      (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
      (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))

IF: 0 + 1 + 2 + 4 + 7
GCD: 4
SUM: 18

应用序:

(list (gcd 206 40)
      (gcd 40 6)
      (gcd 6 4)
      (gcd 4 2)
      (gcd 2 0))

IF: 0
GCD: 4
SUM: 4

1.18 Exercise 1.21

(define (square n)
  (* n n))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a n)
  (= (remainder n a) 0))

(list (smallest-divisor 199)
      (smallest-divisor 1999)
      (smallest-divisor 19999))

1.19 Exercise 1.22

(define (my-return)
  (display "loading ...")
  5)

(define lazy (my-return))

(list lazy
      lazy
      lazy)

(define (square n)
  (* n n))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a n)
  (= (remainder n a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

(define (runtime)
  (tms:clock (times)))

(define (time-prime-test n)
  (start-prime-test n (runtime)))

;; Need to change this
(define (start-prime-test n start-time)
  (if (prime? n)
      (begin (newline)
             (display n)
             (report-prime (- (runtime) start-time))
             #t)
      #f))

(define (report-prime elapsed-time)
  (display " ** ")
  (display elapsed-time))

(define (next-odd n)
  (if (= (remainder n 2) 0)
      (+ n 1)
      (+ n 2)))

(define (search-for-primes-iter i n)
  (if (> i 0)
      (if (time-prime-test n)
          (search-for-primes-iter (- i 1) (next-odd n))
          (search-for-primes-iter i (next-odd n)))))

(define (search-for-primes n)
  (search-for-primes-iter 3 n))

(list (search-for-primes 1000)
      (search-for-primes 10000)
      (search-for-primes 100000)
      (search-for-primes 1000000)
      (search-for-primes 10000000)
      (search-for-primes 100000000)
      (search-for-primes 1000000000)
      (search-for-primes 10000000000)
      (search-for-primes 100000000000)
      (search-for-primes 1000000000000))

1.20 Exercise 1.23

(define (square n)
  (* n n))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))

(define (divides? a n)
  (= (remainder n a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

(define (runtime)
  (tms:clock (times)))

(define (time-prime-test n)
  (start-prime-test n (runtime)))

;; Need to change this
(define (start-prime-test n start-time)
  (if (prime? n)
      (begin (newline)
             (display n)
             (report-prime (- (runtime) start-time))
             #t)
      #f))

(define (report-prime elapsed-time)
  (display " ** ")
  (display elapsed-time))

(define (next-odd n)
  (if (= (remainder n 2) 0)
      (+ n 1)
      (+ n 2)))

(define (search-for-primes-iter i n)
  (if (> i 0)
      (if (time-prime-test n)
          (search-for-primes-iter (- i 1) (next-odd n))
          (search-for-primes-iter i (next-odd n)))))

(define (search-for-primes n)
  (search-for-primes-iter 3 n))

(list (search-for-primes 1000)
      (search-for-primes 10000)
      (search-for-primes 100000)
      (search-for-primes 1000000)
      (search-for-primes 10000000)
      (search-for-primes 100000000)
      (search-for-primes 1000000000)
      (search-for-primes 10000000000)
      (search-for-primes 100000000000)
      (search-for-primes 1000000000000))

1.21 Exercise 1.24

(define (square n)
  (* n n))

(define (even? n)
  (= (remainder n 2) 0))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

(define (runtime)
  (tms:clock (times)))

(define (time-prime-test n)
  (start-prime-test n (runtime)))

;; Need to change this
(define (start-prime-test n start-time)
  (if (fast-prime? n 100)
      (begin (newline)
             (display n)
             (report-prime (- (runtime) start-time))
             #t)
      #f))

(define (report-prime elapsed-time)
  (display " ** ")
  (display elapsed-time))

(define (next-odd n)
  (if (= (remainder n 2) 0)
      (+ n 1)
      (+ n 2)))

(define (search-for-primes-iter i n)
  (if (> i 0)
      (if (time-prime-test n)
          (search-for-primes-iter (- i 1) (next-odd n))
          (search-for-primes-iter i (next-odd n)))))

(define (search-for-primes n)
  (search-for-primes-iter 3 n))

(list (search-for-primes 1000)
      (search-for-primes 10000)
      (search-for-primes 100000)
      (search-for-primes 1000000)
      (search-for-primes 10000000)
      (search-for-primes 100000000)
      (search-for-primes 1000000000)
      (search-for-primes 10000000000)
      (search-for-primes 100000000000)
      (search-for-primes 1000000000000))

1.22 Exercise 1.28

(define (square n)
  (* n n))

(define (even? n)
  (= (remainder n 2) 0))

(define (trivial-square-test a n )
  (if (and (not (= a 1))
           (not (= a (- n 1)))
           (= (remainder (square a) n) 1))
      0
      a))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (trivial-square-test (expmod base (/ exp 2) m) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

(define (rabin-test n)
  (define (try-it a)
    (= (expmod a (- n 1) n) 1))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((rabin-test n) (fast-prime? n (- times 1)))
        (else #f)))

(define (runtime)
  (tms:clock (times)))

(define (time-prime-test n)
  (start-prime-test n (runtime)))

;; Need to change this
(define (start-prime-test n start-time)
  (if (fast-prime? n 100)
      (begin (newline)
             (display n)
             (report-prime (- (runtime) start-time))
             #t)
      #f))

(define (report-prime elapsed-time)
  (display " ** ")
  (display elapsed-time))

(define (next-odd n)
  (if (= (remainder n 2) 0)
      (+ n 1)
      (+ n 2)))

(define (search-for-primes-iter i n)
  (if (> i 0)
      (if (time-prime-test n)
          (search-for-primes-iter (- i 1) (next-odd n))
          (search-for-primes-iter i (next-odd n)))))

(define (search-for-primes n)
  (search-for-primes-iter 3 n))

(list (search-for-primes 1000)
      (search-for-primes 10000)
      (search-for-primes 100000)
      (search-for-primes 1000000)
      (search-for-primes 10000000)
      (search-for-primes 100000000)
      (search-for-primes 1000000000)
      (search-for-primes 10000000000)
      (search-for-primes 100000000000)
      (search-for-primes 1000000000000))

1.23 Exercise 1.29

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

(define (integral f a b n)
  (define h (/ (- b a) n))
  (define (new-f i)
    (* (+ 2 (* 2 (remainder i 2)))
       (f (+ a (* i h)))))
  (/ (* h
        (+ (f a)
           (f b)
           (sum new-f 1 (lambda (x) (+ x 1)) (- n 1))))
     3.0))

(define (cube x)
  (* x x x))

(list (integral cube 0 1.0 100)
      (integral cube 0 1.0 1000))

1.24 Exercise 1.30

(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a)
              (+ result (term a)))))
  (iter a 0))

(define (inc x)
  (+ x 1))

(list (sum (lambda (x) x) 1 inc 10)
      (sum (lambda (x) (* x x x)) 1 inc 10))

1.25 Exercise 1.31

(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a)
              (* result (term a)))))
  (iter a 1))

(define (inc x)
  (+ x 1))

(define (square x)
  (* x x))

(define (factorial n)
  (product (lambda (x) x) 1 inc n))

(define (PI)
  (define (like-PI n)
    (* 4.0
       (/ 2 (+ 3 (* n 2)))
       (product (lambda (x) (square (/ (+ 2 (* x 2))
                                       (+ 1 (* x 2))))) 1 inc n)))
  (like-PI 10000))

(list (factorial 5)
      (PI))

1.26 Exercise 1.32

(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a)
              (combiner result (term a)))))
  (iter a null-value))

(define (sum term a next b)
  (accumulate (lambda (x y) (+ x y))
              0
              term a next b))

(define (inc x)
  (+ x 1))

(list (sum (lambda (x) x) 0 inc 10))

1.27 Exercise 1.33

(define (square n)
  (* n n))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))

(define (divides? a n)
  (= (remainder n a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

(define (filtered-accumulate filter combiner null-value term a next b)
  (define (iter a result)
    (cond ((> a b) result)
          ((filter a) (iter (next a)
                            (combiner result (term a))))
          (else (iter (next a) result))))
  (iter a null-value))

(define (sum term a next b)
  (filtered-accumulate (lambda (x) #t)
                       (lambda (x y) (+ x y))
                       0
                       term a next b))

(define (inc x)
  (+ x 1))

(define (prime-sum a b)
  (filtered-accumulate prime?
                       (lambda (x y) (+ x y))
                       0
                       (lambda (x) x)
                       a
                       inc
                       b))

(define (prime-n n)
  (filtered-accumulate (lambda (x)
                         (= (gcd x n)
                            1))
                       (lambda (x y) (+ x y))
                       0
                       (lambda (x) x)
                       1
                       inc
                       n))

(list (sum (lambda (x) x) 0 inc 10)
      (prime-sum 0 10)
      (prime-n 10))

1.28 Exercise 1.34

Give a error to use 2 as a function.

1.29 Exercise 1.35

(define tolerance 0.00001)

(define (fixed-point f guess)
  (let ((next-guess (f guess)))
    (begin (display next-guess)
           (newline)
           (if (> tolerance
                  (abs (- guess next-guess)))
               next-guess
               (fixed-point f next-guess)))))

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)

1.30 Exercise 1.36

(define tolerance 0.00001)

(define (average x y)
  (/ (+ x y)
     2))

(define (fixed-point f guess)
  (let ((next-guess (f guess)))
    (begin (display next-guess)
           (newline)
           (if (> tolerance
                  (abs (- guess next-guess)))
               next-guess
               (fixed-point f next-guess)))))

(fixed-point (lambda (x)
               (let ((log1000 (log 1000)))
                 (/ log1000 (log x))))
             10.0)

(newline)

(fixed-point (lambda (x)
               (let ((log1000 (log 1000)))
                 (average (/ log1000 (log x))
                          x)))
             10.0)

1.31 Exercise 1.37

(define (cont-frac N D k)
  (define (cont-frac-recur i)
    (if (> i k)
        0
        (/ (N i) (+ (D i)
                    (cont-frac-recur (+ i 1))))))
  (cont-frac-recur 1))

(/ 1 (cont-frac (lambda (i) 1.0)
                (lambda (i) 1.0)
                100))

(define (cont-frac N D k)
  (define (cont-frac-iter i result)
    (if (= i 1)
        result
        (cont-frac-iter (- i 1)
                        (/ (N i) (+ (D i) result)))))
  (cont-frac-iter k 0))

(/ 1 (cont-frac (lambda (i) 1.0)
                (lambda (i) 1.0)
                100))

CPS iteration

(define (identity x) x)

(define (cont-frac N D k)
  (define (cont-frac-cps i f)
    (if (> i k)
        (f 0)
        (cont-frac-cps (+ i 1)
                       (lambda (x)
                         (f (/ (N i)
                               (+ (D i) x)))))))
  (cont-frac-cps 1 identity))

(/ 1 (cont-frac (lambda (i) 1.0)
                (lambda (i) 1.0)
                100))

1.32 Exercise 1.38

(define (identity x) x)

(define (cont-frac N D k)
  (define (cont-frac-cps i f)
    (if (> i k)
        (f 0)
        (cont-frac-cps (+ i 1)
                       (lambda (x)
                         (f (/ (N i)
                               (+ (D i) x)))))))
  (cont-frac-cps 1 identity))

(define (D i)
  (if (= (remainder i 3) 2)
      (* 2 (ceiling-quotient i 3))
      1))

(+ 2 (cont-frac (lambda (i) 1.0)
                D
                100))

1.33 Exercise 1.39

(define (identity x) x)

(define (cont-frac N D k)
  (define (cont-frac-cps i f)
    (if (> i k)
        (f 0)
        (cont-frac-cps (+ i 1)
                       (lambda (x)
                         (f (/ (N i)
                               (+ (D i) x)))))))
  (cont-frac-cps 1 identity))

(define (tan-cf x k)
  (define (D i)
    (- (* i 2) 1))
  (define (N i)
    (if (= i 1)
        x
        (- (* x x))))
  (cont-frac N D k))

(list (tan-cf (/ 3.1415926 4) 100)
      (tan (/ 3.1415926 4)))

1.34 Exercise 1.40

(define tolerance 0.00001)

(define (fixed-point f guess)
  (let ((next-guess (f guess)))
    (begin (display next-guess)
           (newline)
           (if (> tolerance
                  (abs (- guess next-guess)))
               next-guess
               (fixed-point f next-guess)))))

(define dx 0.00001)

(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))

(define (newton-method g guess)
  (fixed-point (newton-transform g) guess))

(define (cubic a b c)
  (lambda (x) (+ (* x x x)
                 (* a x x)
                 (* b x)
                 (* c))))

(define (polynomial a b c)
  (newton-method (cubic a b c) 1))

(polynomial 0 0 1)

1.35 Exercise 1.41

(define (double f)
  (lambda (x) (f (f x))))

(define (inc x)
  (+ x 1))

(((double (double double)) inc) 5) #|(double (double (double (double inc))))|#

1.36 Exercise 1.42

(define (compose f g)
  (lambda (x)
    (f (g x))))

(define (square x)
  (* x x))

(define (inc x)
  (+ x 1))

((compose square inc) 6)

1.37 Exercise 1.43

(define (id x)
  x)

(define (repeated f n)
  (define (repeated-iter fsum i)
    (cond ((= n 0) id)
          ((= i n) fsum)
          (else (repeated-iter (lambda (x) (f (fsum x)))
                               (+ i 1)))))
  (repeated-iter id 0))

(define (square x)
  (* x x))

((repeated square 2) 5)

1.38 Exercise 1.44

(define (id x)
  x)

(define (repeated f n)
  (define (repeated-iter fsum i)
    (cond ((= n 0) id)
          ((= i n) fsum)
          (else (repeated-iter (lambda (x) (f (fsum x)))
                               (+ i 1)))))
  (repeated-iter id 0))

(define epsonlon 0.00001)

(define (smooth f)
  (lambda (x)
    (/ (+ (f (- x epsonlon)) (f x) (f (+ x epsonlon))) 3)))

(define (repeated-smooth f n)
  ((repeated smooth n) f))

(define (square x)
  (* x x))

((repeated-smooth square 5) 5)

1.39 Exercise 1.45

(define (id x) x)

(define tolerance 0.00001)

(define (repeated f n)
  (define (repeated-iter fsum i)
    (cond ((= n 0) id)
          ((= i n) fsum)
          (else (repeated-iter (lambda (x) (f (fsum x)))
                               (+ i 1)))))
  (repeated-iter id 0))

(define (average x y)
  (/ (+ x y)
     2))

(define (average-damp f)
  (lambda (x) (average x (f x))))

(define (average-n-times f n)
  ((repeated average-damp n) f))

(define (power x n)
  (define (power-iter i acc)
    (if (= i n)
        acc
        (power-iter (+ i 1) (* acc x))))
  (power-iter 0 1))

(define (lg2 n)
  (define (lg2-iter acc remain)
    (if (< remain 1)
        acc
        (lg2-iter (+ acc 1) (/ remain 2))))
  (lg2-iter 0 (/ n 2)))

(define (n-th-root n x)
  (define (fixed-point f guess)
    (define next-guess ((average-n-times f (lg2 n)) guess))
    (display next-guess)
    (newline)
    (if (> tolerance (abs (- guess next-guess)))
        next-guess
        (fixed-point f next-guess)))
  (define (f y) (/ x (power y (- n 1))))
  (fixed-point f 1.0))

(define (square x)
  (* x x))

(n-th-root 5 32)

1.40 Exercise 1.46

(define (abs x)
  (if (< x 0)
      (- x)
      x))

(define (iterative-improve good-enough? update-guess)
  (define (iter-func guess)
    (let ((last-guess guess)
          (updated-guess (update-guess guess)))
      (if (good-enough? updated-guess last-guess)
          updated-guess
          (iter-func updated-guess))))
  iter-func)

(define (sqrt n)
  (define (sqrt-good-enough? guess last-guess)
    (if (< (abs (- (/ guess last-guess) 1)) 0.00001) #t #f))
  (define (sqrt-update-guess guess)
    (/ (+ guess (/ n guess)) 2))
  ((iterative-improve sqrt-good-enough? sqrt-update-guess) 2.0))

(sqrt 100)

(define (f)
  (define (g x y) (+ x y))
  (lambda (x y) (g x y)))

((f) 33 44)

(define (iterative-improve good-enough? update-guess)
  (define (iter-func guess)
    (let ((last-guess guess)
          (updated-guess (update-guess guess)))
      (if (good-enough? updated-guess last-guess)
          updated-guess
          (iter-func updated-guess))))
  (lambda (guess) (iter-func guess)))

(define tolerance 0.00001)

(define (fixed-point f guess)
  (define (fixed-point-good-enough? guess last-guess)
    (> tolerance (abs (- last-guess guess))))
  (define (fixed-point-update-guess guess)
    (f guess))
  ((iterative-improve fixed-point-good-enough? fixed-point-update-guess) guess))

(define (average x y)
  (/ (+ x y) 2))

(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y))) 2.0))

(sqrt 100)

2 Building Abstractions with Data

2.1 Exercise 2.1

(define (make-rat n d)
  (define (assign x)
    (if (> x 0)
        1
        -1))
  (let ((g (gcd n d))
        (n (abs n))
        (d (abs d))
        (a (assign (* n d))))
    (cons (* (/ n g) a) (/ d g))))

(define (numer x) (car x))

(define (denom x) (cdr x))

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))

(define num (make-rat 4 -8))

(print-rat num)

num

2.2 Exercise 2.3

#| Utils |#
(define (average x y)
  (/ (+ x y) 2))

#| Point Definiation |#
(define (make-point x y)
  (cons x y))

(define (x-point x)
  (car x))

(define (y-point x)
  (cdr x))

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ", ")
  (display (y-point p))
  (display ")"))

#| Segment Definiation |#
(define (make-segment x y)
  (cons x y))

(define (start-segment x)
  (car x))

(define (end-segment x)
  (cdr x))


(define (midpoint-segment s)
  (let ((p1 (start-segment s))
        (p2 (end-segment s)))
    (make-point (average (x-point p1) (x-point p2))
                (average (y-point p1) (y-point p2)))))

#| Point Rect Definiation |#
(define (make-point-rect p1 p2)
  (cons p1 p2))

(define (height-rect r)
  (abs (- (y-point (car r))
          (y-point (cdr r)))))

(define (width-rect r)
  (abs (- (x-point (car r))
          (x-point (cdr r)))))

#| Implementation |#
(define (perimeter-rect r)
  (* 2 (+ (height-rect r)
          (width-rect r))))

(define (area-rect r)
  (* (height-rect r)
     (width-rect r)))

(define rect (make-point-rect (make-point -1 1)
                              (make-point 5 -8)))

(list (perimeter-rect rect)
      (area-rect rect))

#| Utils |#
(define (average x y)
  (/ (+ x y) 2))

#| Point Definiation |#
(define (make-point x y)
  (cons x y))

(define (x-point x)
  (car x))

(define (y-point x)
  (cdr x))

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ", ")
  (display (y-point p))
  (display ")"))

#| Segment Definiation |#
(define (make-segment x y)
  (cons x y))

(define (start-segment x)
  (car x))

(define (end-segment x)
  (cdr x))


(define (midpoint-segment s)
  (let ((p1 (start-segment s))
        (p2 (end-segment s)))
    (make-point (average (x-point p1) (x-point p2))
                (average (y-point p1) (y-point p2)))))

#| Point Rect Definiation |#
(define (make-pwh-rect p1 width height)
  (cons p1 (cons width height)))

(define (height-rect r)
  (cdr (cdr r)))

(define (width-rect r)
  (car (cdr r)))

#| Implementation |#
(define (perimeter-rect r)
  (* 2 (+ (height-rect r)
          (width-rect r))))

(define (area-rect r)
  (* (height-rect r)
     (width-rect r)))

(define rect (make-pwh-rect (make-point -1 1)
                            6
                            9))

(list (perimeter-rect rect)
      (area-rect rect))

2.3 Exercise 2.4

Church Encoding

(define (cons x y)
  (lambda (m) (m x y)))

(define (car pair)
  (pair (lambda (x y) x)))

(define (cdr pair)
  (pair (lambda (x y) y)))

2.4 Exercise 2.5

(define (cons x y)
  (* (expt 2 x) (expt 3 y)))

(define (integer-log x y)
  (define (id x) x)
  (define (integer-log-iter x f)
    (let ((quot (/ x y)))
      (if (integer? quot)
          (integer-log-iter quot (lambda (x) (f (+ x 1))))
          (f 0))))
  (integer-log-iter x id))

(define (car x)
  (integer-log x 2))

(define (cdr x)
  (integer-log x 3))

(define pair (cons 2 3))

(list pair
      (car pair)
      (cdr pair))

2.5 Exercise 2.6

(define zero
  (lambda (f) (lambda (x) x)))

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

(define one
  (lambda (f) (lambda (x) (f x))))

(define two
  (lambda (f) (lambda (x) (f (f x)))))

(define (add a b)
  (lambda (f) (lambda (x)
                ((b f) ((a f) x)))))

2.6 Exercise 2.7, 2.8, 2.9, 2.10, 2.11. 2.12, 2.13, 2.14, (2.15, 2.16)

#| Definition |#

(define (make-interval lower-bound upper-bound)
  (cons lower-bound upper-bound))

(define (make-center-percent c pw)
  (make-center-width c (* c pw)))

(define (make-center-width c w)
  (make-interval (- c w) (+ c w)))

(define (lower-bound x)
  (min (car x) (cdr x)))

(define (upper-bound x)
  (max (car x) (cdr x)))

(define (interval-center x)
  (/ (+ (lower-bound x) (upper-bound x)) 2))

(define (interval-width x)
  (/ (- (upper-bound x) (lower-bound x)) 2.0))

(define (interval-percent x)
  (/ (* 100 (interval-width x)) (interval-center x)))

(define (mul-interval-rough-percent x y)
  (+ (interval-percent x) (interval-percent y)))

(define (state x)
  (if (> (* (upper-bound x) (lower-bound x)) 0)
      (if (> (lower-bound x) 0)
          1
          -1)
      0))

(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))

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

(define (mul-interval-1 x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))

(define (mul-interval x y)
  (let ((x0 (lower-bound x))
        (x1 (upper-bound x))
        (y0 (lower-bound y))
        (y1 (upper-bound y))
        (xs (state x))
        (ys (state y)))
    (cond ((and (> xs 0) (> ys 0))
           (make-interval (* x0 y0) (* x1 y1)))
          ((and (> xs 0) (< ys 0))
           (make-interval (* x1 y0) (* x0 y1)))
          ((and (> xs 0) (= ys 0))
           (make-interval (* x1 y0) (* x1 y1)))
          ((and (< xs 0) (> ys 0))
           (make-interval (* x0 y1) (* x1 y0)))
          ((and (< xs 0) (< ys 0))
           (make-interval (* x1 y1) (* x0 y0)))
          ((and (< xs 0) (= ys 0))
           (make-interval (* x1 y1) (* x0 y0)))
          ((and (= xs 0) (> ys 0))
           (make-interval (* x0 y1) (* x1 y1)))
          ((and (= xs 0) (< ys 0))
           (make-interval (* x1 y0) (* x0 y1)))
          ((and (= xs 0) (= ys 0))
           (make-interval (min (* x0 y1) (* x1 y0)) (max (* x0 y0) (* x1 y1)))))))

(define (div-interval x y)
  (if (not (= (state y) 0))
      (mul-interval x
                    (make-interval (/ 1.0 (upper-bound y))
                                   (/ 1.0 (lower-bound y))))
      (throw 'cross-zero "Divided a cross-zero-interval!")))

#| Test |#
(define x1 (make-interval -1 3))
(define x2 (make-interval -2 4))
(define x3 (make-interval 2 4))
(define x4 (make-center-percent 10 0.03))
(define x5 (make-center-percent 5 0.001))
(define x6 (make-interval 1000 1001))
(define x7 (make-interval 2000 2005))


(define (show-bool bool)
  (if bool "true"  "false"))

(list (add-interval x1 x2)
      (sub-interval x1 x2)
      (mul-interval x1 x2)
      (catch 'cross-zero
        (lambda () (div-interval x1 x2))
        (lambda (key arg) (display arg) "NAN"))
      (div-interval x1 x3)
      (show-bool (= (interval-width (add-interval x1 x2))
                    (+ (interval-width x1) (interval-width x2))))
      (show-bool (= (interval-width (sub-interval x1 x2))
                    (+ (interval-width x1) (interval-width x2))))
      (abs (- (interval-percent (mul-interval x1 x2)) (mul-interval-rough-percent x1 x2)))
      (abs (- (interval-percent (mul-interval x4 x5)) (mul-interval-rough-percent x4 x5)))
      (interval-percent x6)
      (interval-percent (add-interval x6 x6))
      (sub-interval x6 x6)
      (interval-percent (mul-interval x6 x6))
      (interval-percent (div-interval x6 x6))
      (interval-percent (div-interval x6 x7)))

2.7 Exercise 2.17

(define (last-pair list)
  (let ((tail (cdr list)))
    (if (null? tail)
        (car list)
        (last-pair tail))))

(last-pair (list 1 2 3 4))

2.8 Exercise 2.18

(define (reverse li)
  (define (reverse-iter src dst)
    (if (null? src)
        dst
        (reverse-iter (cdr src) (cons (car src) dst))))
  (reverse-iter li (list)))

(reverse (list 1 2 3 4))

2.9 Exercise 2.19

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount (first-denomination coin-values)) coin-values)))))

(define no-more? null?)

(define first-denomination car)

(define except-first-denomination cdr)

(define us-coins (list 50 25 10 5 1))

(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(cc 100 us-coins)

2.10 Exercise 2.20

(define (identity x) x)

(define (same-parity n . li)
  (define (same-parity-iter f li)
    (if (null? li)
        (f (list))
        (if (zero? (remainder (- (car li) n) 2))
            (same-parity-iter (lambda (x) (f (cons (car li) x))) (cdr li))
            (same-parity-iter f (cdr li)))))
  (cons n (same-parity-iter identity li)))

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

2.11 Exercise 2.21

(define (map li op)
  (define (identity x) x)
  (define (map-cps-iter src f)
    (if (null? src)
        (f (list))
        (map-cps-iter (cdr src)
                      (lambda (x)
                        (f (cons (op (car src)) x))))))
  (map-cps-iter li identity))

(define (square-list x)
  (map x (lambda (x) (* x x))))

(define my-list (list 1 2 3 4))

(square-list my-list)

2.12 Exercise 2.22

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (car things))))))
  (iter items (list)))

(define (square x) (* x x))

(define my-list (list 1 2 3 4))

(square-list my-list)

2.13 Exercise 2.23

(define (for-each li op)
  (define (for-each-iter src)
    (if (not (null? src))
        (begin
          (op (car src))
          (for-each-iter (cdr src)))))
  (for-each-iter li))

(define my-list (list 1 2 3 4))

(for-each my-list (lambda (x) (newline) (display x)))

2.14 Exercise 2.24

(list 1 (list 2 (list 3 4)))
#| (1 . (2 . (3 . 4))) |#

2.15 Exercise 2.25

(define l1 (list 1 3 (list 5 7) 9))
(define l2 (list (list 7)))
(define l3 (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))

(list
 (car (cdr (car (cdr (cdr l1)))))
 (car (car l2))
 (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr l3)))))))))))))

2.16 Exercise 2.26

(define x (list 1 2 3))
(define y (list 4 5 6))

(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

(list
 (append x y) #|(1 2 3 4 5 6)|#
 (cons x y) #|((1 2 3) 4 5 6)|#
 (list x y) #|((1 2 3) (4 5 6))|#
 )

2.17 Exercise 2.27

(define x (list (list 1 2) (list 3 4)))

(define (reverse li)
  (define (reverse-iter src dst)
    (if (null? src)
        dst
        (reverse-iter (cdr src) (cons (car src) dst))))
  (reverse-iter li (list)))

(define (deep-reverse li)
  (define (reverse-iter src dst)
    (if (null? src)
        dst
        (let ((head
               (if (pair? (car src))
                   (reverse-iter (car src) (list))
                   (car src))))
          (reverse-iter (cdr src) (cons head dst)))))
  (reverse-iter li (list)))

(list (reverse x)
      (deep-reverse x))

2.18 Exercise 2.28

 (define (leaf? x)
   (and (pair? x)
        (not (pair? (car x)))))

 (define (wrap? x)
   (and (pair? x)
        (null? (cdr x))
        (pair? (car x))))

 (define (append-cps x y f)
   (cond ((null? x) (f y))
         ((not (pair? x)) (f (cons x y)))
         (else (append-cps (cdr x) y (lambda (r) (f (cons (car x) r)))))))

 (define (fringe tree)
   (define (id x) x)
   (define (fringe-iter src f)
     (cond ((null? src) '())
           ((wrap? src) (fringe-iter (car src) f))
           ((leaf? src) (if (null? (cdr src))
                            (f (car src))
                            (fringe-iter (cdr src) (lambda (x) (f (cons (car src) x))))))
           (else (fringe-iter (car src) (lambda (x) (fringe-iter (cdr src)
                                                                 (lambda (y) (append-cps x y f))))))))
   (fringe-iter tree (lambda (x) (append-cps x '() id))))

 (define x (list (list 1 2) (list 3 4)))

(fringe (list x x))

2.19 Exercise 2.29

(define (make-mobile left right)
  (list left right))

(define (make-branch length structure)
  (list length structure))

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

(define (mobile? x)
  (and (pair? x)
       (branch? (left-branch x))
       (branch? (right-branch x))))

(define (branch? x)
  (and (pair? x)
       (not (pair? (car x)))))

(define (total-weight mobile)
  (define (id x) x)
  (define (total-weight-cps x f)
    (if (mobile? x)
        (let ((ll (branch-length (left-branch x)))
              (rl (branch-length (right-branch x)))
              (ls (branch-structure (left-branch x)))
              (rs (branch-structure (right-branch x))))
          (total-weight-cps ls
                            (lambda (lw) (total-weight-cps rs
                                                           (lambda (rw) (f (+ lw rw)))))))
        (f x)))
  (total-weight-cps mobile id))

(define (torque x)
  (if (branch? x)
      (let ((bl (branch-length x))
            (bs (branch-structure x)))
        (* bl (total-weight bs)))))

(define (is-balence? mobile)
  (define (id x) x)
  (define (is-balence?-cps x f)
    (if (mobile? x)
        (let ((l (left-branch x))
              (r (right-branch x))
              (ll (branch-length (left-branch x)))
              (rl (branch-length (right-branch x)))
              (ls (branch-structure (left-branch x)))
              (rs (branch-structure (right-branch x))))
          (if (eq? (torque l) (torque r))
              (is-balence?-cps ls
                               (lambda (lb) (is-balence?-cps rs
                                                             (lambda (rb) (f (and lb rb))))))
              (f #f)))
        (f #t)))
  (is-balence?-cps mobile id))
#|Test|#

(define m1 (make-mobile (make-branch 10 100)
                        (make-branch 5 200)))

(define m2 (make-mobile (make-branch 3 100)
                        (make-branch 4 50)))

(define m (make-mobile (make-branch 4 m1)
                       (make-branch 8 m2)))

(list
 (total-weight m1)
 (total-weight m2)
 (total-weight m)
 (is-balence? m1)
 (is-balence? m2)
 (is-balence? m))

2.20 Exercise 2.30, 2.31

(define (recursive-map-tree tree op)
  (cond ((null? tree) '())
        ((not (pair? tree)) (op tree))
        (else (cons (recursive-map-tree (car tree) op)
                    (recursive-map-tree (cdr tree) op)))))

(define (iterative-map-tree tree op)
  (define (id x) x)
  (define (map-tree-cps x f)
    (cond ((null? x) (f '()))
          ((not (pair? x)) (f (op x)))
          (else (map-tree-cps (car x)
                              (lambda (lt) (map-tree-cps (cdr x)
                                                         (lambda (rt) (f (cons lt rt)))))))))
  (map-tree-cps tree id))
#|Test|#
(define t (list 1 (list 2 (list 3 4) 5) (list 6 7)))

(define (op x)
  (* x x))

(list t
      (recursive-map-tree t op)
      (iterative-map-tree t op))

2.21 Exercise 2.32

(define (iterative-map-list li op)
  (define (id x) x)
  (define (map-list-cps x f)
    (if (null? x)
        (f '())
        (map-list-cps (cdr x)
                      (lambda (l)
                        (cons (op (car x)) l)))))
  (map-list-cps li id))

(define (subsets s)
  (if (null? s)
      (list s)
      (let ((rest (subsets (cdr s))))
        (append rest (iterative-map-list rest (lambda (x) (cons (car s) x)))))))
#|Test|#
(define s (list 1 2 3 (list 4 5) 6 7))

(subsets s)

2.22 Exercise 2.33, 2.34

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) '() sequence))

(define (append seq1 seq2)
  (accumulate cons seq2 seq1))

(define (length sequence)
  (accumulate (lambda (x y) (+ y 1)) 0 sequence))

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)
                (+ this-coeff (* x higher-terms)))
              0
              coefficient-sequence))
#|Test|#

(define l1 (list 1 2 3 4 5))

(define l2 (list 6 7 8))

(define (f x) (+ x 1))

(list (map f l1)
      (append l1 l2)
      (length l1)
      (horner-eval 0 (list 2 2 2))
      (horner-eval 2 (list 2 2 2)))

2.23 Exercise 2.35

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (count-leaves t)
  (accumulate (lambda (z x) (+ z x))
              0
              (map (lambda (x)
                       (cond ((null? x) '())
                             ((pair? x) (count-leaves x))
                             (else 1))) t)))

#|Test|#
(define t (list (list 1 2) 3 4 (list 5 6) 7))

(count-leaves t)

2.24 Exercise 2.36

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (seqs-split seqs)
  (define (li-id x y) (cons x y))
  (define (seqs-split-cps seqs f)
    (if (null? seqs)
        (f '() '())
        (seqs-split-cps (cdr seqs)
                        (lambda (x y)
                          (f (cons (car (car seqs)) x)
                             (cons (cdr (car seqs)) y))))))
  (seqs-split-cps seqs li-id))

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (let ((split-seqs (seqs-split seqs)))
        (cons (accumulate op init (car split-seqs))
              (accumulate-n op init (cdr split-seqs))))))

#|Test|#
(define li (list (list 1 2 3 4)
                 (list 3 4 5 6)
                 (list 5 6 7 8)))

(accumulate-n (lambda (z x)
                (+ z x))
              0
              li)

2.25 Exercise 2.37

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (seqs-split seqs)
  (define (li-id x y) (cons x y))
  (define (seqs-split-cps seqs f)
    (if (null? seqs)
        (f '() '())
        (seqs-split-cps (cdr seqs)
                        (lambda (x y)
                          (f (cons (car (car seqs)) x)
                             (cons (cdr (car seqs)) y))))))
  (seqs-split-cps seqs li-id))

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (let ((split-seqs (seqs-split seqs)))
        (cons (accumulate op init (car split-seqs))
              (accumulate-n op init (cdr split-seqs))))))

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

(define (matrix-*-vector m v)
  (map (lambda (w)
         (dot-product w v)) m))

(define (transpose mat)
  (accumulate-n cons '() mat))

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (x)
           (matrix-*-vector cols x))
         m)))
#|Test|#
(define v (list 1 2 3 4))

(define w (list 2 4 6 8))

(define n (list (list 2 2) (list 3 3) (list 4 4) (list 5 5)))

(define m (list (list 1 1 1 1) w))

(list (dot-product v w)
      (matrix-*-vector m v)
      (transpose m)
      (matrix-*-matrix m n))

2.26 Exercise 2.38

(define (fold-right op initial sequence)
  (define (id x) x)
  (define (fold-right-cps seq f)
    (if (null? seq)
        (f initial)
        (fold-right-cps (cdr seq)
                        (lambda (x)
                          (f (op x (car seq)))))))
  (fold-right-cps sequence id))

(define (fold-left op initial sequence)
  (define (id x) x)
  (define (fold-left-cps seq r f)
    (if (null? seq)
        (f r)
        (fold-left-cps (cdr seq)
                       (op r (car seq))
                       f)))
  (fold-left-cps sequence initial id))

#|Test|#
(define seq (list 1 2 3 4))

(list (fold-right (lambda (z x)
                    (+ x (* 2 z))) 0 seq)
      (fold-left (lambda (z x)
                   (+ x (* 2 z))) 0 seq))

2.27 Exercise 2.39

(define (fold-right op initial sequence)
  (define (id x) x)
  (define (fold-right-cps seq f)
    (if (null? seq)
        (f initial)
        (fold-right-cps (cdr seq)
                        (lambda (x)
                          (f (op x (car seq)))))))
  (fold-right-cps sequence id))

(define (fold-left op initial sequence)
  (define (id x) x)
  (define (fold-left-cps seq r f)
    (if (null? seq)
        (f r)
        (fold-left-cps (cdr seq)
                       (op r (car seq))
                       f)))
  (fold-left-cps sequence initial id))

(define (reverse-right sequence)
  (fold-right (lambda (z x)
                (append z (list x)))
              '()
              sequence))

(define (reverse-left sequence)
  (fold-left (lambda (z x)
               (cons x z))
             '()
             sequence))

#|Test|#
(define li (list 1 2 3 4))

(list (reverse-right li)
      (reverse-left li))

2.28 Exercise 2.40

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (flatmap proc seq)
  (accumulate append '() (map proc seq)))

(define (enumerate-interval x y)
  (define (id x) x)
  (define (enumerate-interval-cps x f)
    (if (> x y)
        (f '())
        (enumerate-interval-cps (+ x 1)
                                (lambda (s)
                                  (f (cons x s))))))
  (enumerate-interval-cps x id))

(define (unique-pairs n)
  (flatmap (lambda (x)
             (map (lambda (y)
                    (list y x))
                  (enumerate-interval 1 (- x 1))))
           (enumerate-interval 1 n)))

#|Test|#
(unique-pairs 5)

2.29 Exercise 2.41

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (flatmap proc seq)
  (accumulate append '() (map proc seq)))

(define (enumerate-interval x y)
  (define (id x) x)
  (define (enumerate-interval-cps x f)
    (if (> x y)
        (f '())
        (enumerate-interval-cps (+ x 1)
                                (lambda (s)
                                  (f (cons x s))))))
  (enumerate-interval-cps x id))

(define (filter predicate seq)
  (define (id x) x)
  (define (filter-cps seq f)
    (if (null? seq)
        (f '())
        (if (predicate (car seq))
            (filter-cps (cdr seq) (lambda (x)
                                    (f (cons (car seq) x))))
            (filter-cps (cdr seq) f))))
  (filter-cps seq id))

(define (tri-sum s n)
  (flatmap (lambda (a)
             (map (lambda (b)
                    (list a b (- s a b)))
                  (filter (lambda (x)
                            (and (not (= x a))
                                 (not (= (* 2 x) (- s a)))))
                   (enumerate-interval (max 1 (- n a)) (min n (- s a))))))
           (enumerate-interval 1 (min n s))))

#|Test|#
(tri-sum 8 5)

2.30 Exercise 2.42

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (flatmap proc seq)
  (accumulate append '() (map proc seq)))

(define (enumerate-interval x y)
  (define (id x) x)
  (define (enumerate-interval-cps x f)
    (if (> x y)
        (f '())
        (enumerate-interval-cps (+ x 1)
                                (lambda (s)
                                  (f (cons x s))))))
  (enumerate-interval-cps x id))

(define (filter predicate seq)
  (define (id x) x)
  (define (filter-cps seq f)
    (if (null? seq)
        (f '())
        (if (predicate (car seq))
            (filter-cps (cdr seq) (lambda (x)
                                    (f (cons (car seq) x))))
            (filter-cps (cdr seq) f))))
  (filter-cps seq id))

(define (adjoin-position new k rest)
  (append rest (list new)))

(define (list-get li n)
  (if (= n 0)
      (car li)
      (list-get (cdr li) (- n 1))))

(define (safe? k positions)
  (accumulate (lambda (x y)
                (and x y))
              #t
              (map (lambda (i)
                     (let ((x (list-get positions (- k 1)))
                           (y (list-get positions (- i 1))))
                       (and (not (= x y))
                            (not (= x (+ y (- k i))))
                            (not (= x (- y (- k i)))))))
                   (enumerate-interval 1 (- k 1)))))

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 1) (map list (enumerate-interval 1 board-size))
        (filter (lambda (positions) (safe? k positions))
                (flatmap (lambda (rest-of-queens)
                           (map (lambda (new-row)
                                  (adjoin-position new-row k rest-of-queens))
                                (enumerate-interval 1 board-size)))
                         (queen-cols (- k 1))))))
  (queen-cols board-size))

(queens 4)

2.31 Exercise 2.42

T²

2.32 Exercise 2.53

(list
 (list 'a 'b 'c) ; (a b c)
 (list (list 'george)) ; ((george))
 (cdr '((x1 x2) (y1 y2))) ; ((y1 y2))
 (car '((x1 x2) (y1 y2))) ; (x1 x2)
 (pair? (car '(a short list))) ; #f
 (memq 'red '((red shoes) (blue socks))) ; #f
 (memq 'red '(shoes red blue socks)) ; # (red blue socks)
 )

2.33 Exercise 2.54

(define (equal? s1 s2)
  (if (and (pair? s1) (pair? s2)) ; if they are all pairs
      (and (eq? (car s1) (car s2)) (equal? (cdr s1) (cdr s2)))
      (eq? s1 s2)))

;; Test
(define li1 '(this is a list))

(define li2 '(this (is a) list))

(list (equal? li1 li1)
      (equal? li1 li2))

2.34 Exercise 2.55

(car ''abracadabra)
(car (quote (quote abracadabra)))
(car (list 'quote 'abracadabra))
'quote

2.35 Exercise 3.1

(define (make-accumulator init)
  (define (accumulator increment)
    (set! init (+ init increment))
    init)
  accumulator)

;; Test
(define A (make-accumulator 5))
(list (A 10)
      (A 10))

2.36 Exercise 3.2

(define (make-monitored f)
  (define call-count 0)
  (lambda (x)
    (cond ((eq? x 'how-many-calls?)
           call-count)
          ((eq? x 'reset-count)
           (begin (set! call-count 0)
                  call-count))
          (else (begin
                  (set! call-count (+ call-count 1))
                  (f x))))))

;; Test
(define s (make-monitored sqrt))

(list (s 100)
      (s 81)
      (s 'how-many-calls?)
      (s 'reset-count)
      (s 25)
      (s 'how-many-calls?))

2.37 Exercise 3.3, 3.4

(define (call-the-cops amount)
  "Already called cops")

(define (make-account balance pwd)
  (define psw-wrong-times 0)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (define (complain amount)
    "!")
  (define (dispatch p m)
    (if (not (eq? pwd p))
        (begin
          (set! psw-wrong-times (+ psw-wrong-times 1))
          (if (>= psw-wrong-times 7)
              call-the-cops
              complain))
        (begin
          (set! psw-wrong-times 0)
          (cond ((eq? m 'withdraw) withdraw)
                ((eq? m 'deposit) deposit)
                (else (error "Unknown request -- MAKE-ACOUNT" m))))))
  dispatch)

;; Test

(define acc (make-account 100 'secret-password))

(list
 ((acc 'secret-password 'withdraw) 50)
 ((acc 'secret-password 'withdraw) 60)
 ((acc 'secret-password 'deposit) 40)
 ((acc 'wrong-password 'deposit) 40)
 ((acc 'wrong-password 'deposit) 40)
 ((acc 'wrong-password 'deposit) 40)
 ((acc 'wrong-password 'deposit) 40)
 ((acc 'wrong-password 'deposit) 40)
 ((acc 'wrong-password 'deposit) 40)
 ((acc 'secret-password 'withdraw) 60)
 ((acc 'wrong-password 'deposit) 40)
 ((acc 'wrong-password 'deposit) 40)
 ((acc 'wrong-password 'deposit) 40)
 ((acc 'wrong-password 'deposit) 40)
 ((acc 'wrong-password 'deposit) 40)
 ((acc 'wrong-password 'deposit) 40)
 ((acc 'wrong-password 'deposit) 40))