;;;;;; #1
;;;;;; 1.16
(define (expt base power)
  (define (expt-iter base power result)
       (cond ((= power 0) result)
	     ((even? power) (expt-iter (square base) (/ power 2) result))
	     (else (expt-iter base (- power 1) (* base result)))))

  (if (= base 0) 0
       (expt-iter base power 1)))

;STk> (expt 100 1)
;100
;STk> (expt 100 0)
;1
;STk> (expt 100 2)
;10000
;STk> (expt 2 10)
;1024

;;;;;; 1.31a
(define (product fun next a b)
  (if (> a b) 1
      (* (fun a) (product fun next (next a) b))))

(define (factorial n)
  (define (id a) a)
  (define (inc a) (+ 1 a))
  (product id inc 1 n))

(define (pi/4)
  (define (formula a)
       (/ (* 4 a (+ a 1)) (sq (+ 1 (* a 2)))))
  (define (sq x) (* x x))
  (product formula inc 1 1000))

;STk> (pi/4)
;0.78559434127347
;STk> (factorial 10)
;3628800
;STk> (factorial 5)
;120
;STk> (* 10 9 8 7 6 5 4 3 2 1)
;3628800

;;;;;; 1.32a.
(define (accumulate combiner null-value term a next b)
       (if (> a b) null-value
	   (combiner (term a) (accumulate combiner null-value term (next a) next b))))

(define (product_2 fun next a b)
       (accumulate * 1 fun a next b))

(define (sum_2 fun next a b)
       (accumulate + 0 fun a next b))

;STk> (define (inc x) (+ x 1))
;inc
;STk> (define (id x) x)
;id
;STk> (sum_2 id inc 1 10)
;55
;STk> (product_2 id inc 1 10)
;3628800

;;;;;; 1.33
;;;;;; a.
(define (filtered-accumulate combiner null-value term a next b filter)
       (cond ((> a b) null-value)
	     ((filter a b) (combiner (term a) (filtered-accumulate combiner null-value term (next a) next b filter)))
	     (else (filtered-accumulate combiner null-value term (next a) next b filter))))

(define (sum_square_prime a b)
  (define (sq x) (* x x))
  (define (inc a) (+ 1 a))
  (define (test? a b) (prime? a))
  (filtered-accumulate + 0 sq a inc b test?))

;STk> (sum_square_prime 4 10)
;74
;STk> (+ 25 49)
;74

;;;;;;;;;;;;;;book's version of prime (using divisor approch)
(define (prime? n)
  (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 b)
       (= (remainder b a) 0))
  (define (square x) (* x x))
  (define (smallest-divisor n)
       (find-divisor n 2))
  (= n (smallest-divisor n)))

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

(define (product_relative_prime n)
  (define (relative_prime? a b)
    (define (gcd a b)
       (if (= b 0)
	   a
	   (gcd b (remainder a b))))
    (if (= 1 (gcd a b)) #t #f))
  (define (id a) a)
  (define (inc a) (+ 1 a))
  (filtered-accumulate * 1 id 2 inc n relative_prime?))

;STk> (product_relative_prime 9)
;2240
;STk> (* 2 4 5 7 8)
;2240

;;;;;; 1.35
(define tolerance 0.00001)
(define (fixed-point1 f first-guess)
       (define (try guess)
	 (let ((next (f guess)))
	   (if ((lambda (v1 v2) (< (abs (- v1 v2)) tolerance))  guess next)
	       next
	       (try next))))
       (try first-guess))

(define (golden_ratio)
       (fixed-point1 (lambda (x) (+ 1 (/ 1 x))) 1.0))

;STk> (golden_ratio)
;1.61803278688525

;;;;;; 1.41
(define (inc x) (+ x 1))
(define (double f)
       (lambda (x) (f (f x))))
;STk> (((double (double double)) inc) 5)
;21

;;;;;; 1.43
(define (compose f g)
       (lambda (x) (f (g x))))
(define (repeated f n)
       (cond ((< n 1) (lambda (x) 0))
	     ((= n 1) f)
	     (else (compose f (repeated f (- n 1))))))
(define (square x) (* x x))
(define (inc x) (+ 1 x))

;STk> ((repeated square 3) 5)
;390625
;STk> ((repeated square 4) 5)
;152587890625
;STk> ((repeated inc 10) 5)
;15

;;;;;; 1.46
(define (iterative-improve good? improve f)
  (lambda (guess)
    (if (good? f guess)  guess
      ((iterative-improve good? improve f) (improve f guess)))))

(define (good? f guess)
  (< (abs (- (f guess) guess)) 0.00001))

(define (improve_sqrt f guess)
  (/ (+ guess (f guess)) 2))
(define (sqrt n)
  ((iterative-improve good? improve_sqrt (lambda (x) (/ n x))) 1.0))

(define (improve_fix f guess)
  (f guess))
(define (fixed-point f)
  ((iterative-improve good? improve_fix f) 1.0))

;STk> (sqrt 100)
;10.0000000001399
;STk> (sqrt 2)
;1.41421568627451
;STk> (fixed-point cos)
;0.739089341403393
;STk> (fixed-point (lambda (x) (+ (sin x) (cos x))))
;1.25872287430527


;;;;;; #2
(define (next_perf n)
  (if (= n (sum_fac n)) n
      (next_perf (+ n 1))))

(define (sum_fac n)
  (if (even? n) (sum n 1 1 0)
      (sum n 1 2 0)))

(define (sum n start step res)
  (cond ((= n start) res)
	((= (remainder n start) 0)
	 (sum n (+ start step) step (+ res start)))
	(else (sum n (+ start step) step res))))

;STk> (load "home2.scm")
;STk> (next_perf 1)
;6
;STk> (next_perf 4)
;6
;STk> (next_perf 7)
;28
;STk> (next_perf 29)
;496

;;;;;; #3
       ; formula b^n = (b^counter)*product
; remark: b^n means the nth power of b

;;;;;; #4
(define (every f arg)
  (every_iter f arg '()))
(define (every_iter f arg res)
  (if (empty? arg) res
      (every_iter f (bf arg) (se res (f (first arg))))))

;STk> (every (lambda (x) (* x x)) '(1 2 3 4 5))
;(1 4 9 16 25)
;STk> (every (lambda (wd) (word 'e wd 'e)) '(we have nothing))
;(ewee ehavee enothinge)