test.rkt
```;; File test.rkt from http://www.neilvandyke.org/racket-sicp/

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; 1.1.1  Expressions

(check-expect (+ 137 349) 486)
(check-expect (- 1000 334) 666)
(check-expect (* 5 99) 495)
(check-expect (/ 10 5) 2)
(check-expect (+ 2.7 10) 12.7)

(check-expect (+ 21 35 12 7) 75)
(check-expect (* 25 4 12) 1200)

(check-expect (+ (* 3 5) (- 10 6)) 19)
(check-expect (+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6)) 57)

;; 1.1.2  Naming and the Environment

(define size 2)

(check-expect size 2)
(check-expect (* 5 size) 10)

(define pi 3.14159)
(define circumference (* 2 pi radius))
(check-expect circumference 62.8318)

;; 1.1.4  Compound Procedures

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

(check-expect (square 21) 441)

(check-expect (square (+ 2 5)) 49)

(check-expect (square (square 3)) 81)

(define (sum-of-squares x y)
(+ (square x) (square y)))

(check-expect (sum-of-squares 3 4) 25)

(define (f a)
(sum-of-squares (+ a 1) (* a 2)))

(check-expect (f 5) 136)

;; 1.1.6  Conditional Expressions and Predicates

(define (abs:1 x)
(cond ((> x 0) x)
((= x 0) 0)
((< x 0) (- x))))

(define (abs:2 x)
(cond ((< x 0) (- x))
(else x)))

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

(define (>=:1 x y)
(or (> x y) (= x y)))

(define (>=:2 x y)
(not (< x y)))

;; 1.1.7  Example: Square Roots by Newton's Method

(define (sqrt:1 x)
(the y (and (>= y 0)
(= (square y) x))))

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

(define (improve guess x)
(average guess (/ x guess)))

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

(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))

(define (sqrt:2 x)
(sqrt-iter 1.0 x))

(check-expect (sqrt:2 9) 3.00009155413138)
(check-expect (sqrt:2 (+ 100 37)) 11.704699917758145)
(check-expect (sqrt:2 (+ (sqrt:2 2) (sqrt:2 3))) 1.7739279023207892)
(check-expect (square (sqrt:2 1000)) 1000.000369924366)

(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))

(check-expect (new-if (= 2 3) 0 5) 5)
(check-expect (new-if (= 1 1) 0 5) 0)

;; 1.1.8  Procedures as Black-Box Abstractions

(define (square:2 x)
(exp (double (log x))))

(define (double x) (+ x x))

(define (sqrt:3 x)
(define (good-enough?:2 guess x)
(< (abs (- (square guess) x)) 0.001))
(define (improve:2 guess x)
(average guess (/ x guess)))
(define (sqrt-iter:2 guess x)
(if (good-enough?:2 guess x)
guess
(sqrt-iter:2 (improve guess x) x)))
(sqrt-iter:2 1.0 x))

(define (sqrt:4 x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess)
(average guess (/ x guess)))
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0))

;; 1.2.1  Linear Recursion and Iteration

(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))

(define (factorial:2 n)
(fact-iter 1 1 n))

(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))

(check-expect (factorial:2 6) 720)

(define (+:1 a b)
(if (= a 0)
b
(inc (+:1 (dec a) b))))

(define (+:2 a b)
(if (= a 0)
b
(+:2 (dec a) (inc b))))

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

(A 1 10)

(A 2 4)

(A 3 3)

;; 1.2.2  Tree Recursion

(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))

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

(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))

(define (count-change amount)
(cc amount 5))

(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))

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

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))

;; 1.2.4  Exponentiation

(define (expt:2 b n)
(if (= n 0)
1
(* b (expt:2 b (- n 1)))))

(define (expt:3 b n)
(expt-iter b n 1))

(define (expt-iter b counter product)
(if (= counter 0)
product
(expt-iter b
(- counter 1)
(* b product))))

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

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

(define (*:2 a b)
(if (= b 0)
0
(+ a (*:2 a (- b 1)))))

;; 1.2.5  Greatest Common Divisors

(define (gcd:2 a b)
(if (= b 0)
a
(gcd:2 b (remainder a b))))

;; 1.2.6  Example: Testing for Primality

(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 b)
(= (remainder b a) 0))

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

(check-expect (prime? 1) #t)
(check-expect (prime? 2) #t)
(check-expect (prime? 3) #t)
(check-expect (prime? 4) #f)

(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) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))

;; TODO: Test that this generates an error?
;;
;; (check-expect (fast-prime? 1 100) #t)

(check-expect (fast-prime? 2 100) #t)
(check-expect (fast-prime? 3 100) #t)
(check-expect (fast-prime? 4 100) #f)

;; Exercise 1.22

(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (runtime)))

(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (runtime) start-time))))

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

;; Exercise 1.25

(define (expmod:2 base exp m)
(remainder (fast-expt base exp) m))

;; Exercise 1.26

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

;; 1.3  Formulating Abstractions with Higher-Order Procedures

(define (cube:1.3 x) (* x x x))

;; 1.3.1  Procedures as Arguments

(define (sum-integers a b)
(if (> a b)
0
(+ a (sum-integers (+ a 1) b))))

(define (sum-cubes a b)
(if (> a b)
0
(+ (cube:1.3 a) (sum-cubes (+ a 1) b))))

(define (pi-sum a b)
(if (> a b)
0
(+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))

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

(define (inc:1.3.1 n) (+ n 1))

(define (sum-cubes:2 a b)
(sum cube:1.3 a inc:1.3.1 b))

(check-expect (sum-cubes:2 1 10) 3025)

(define (identity:1.3.1 x) x)

(define (sum-integers:1.3.1:2 a b)
(sum identity:1.3.1 a inc:1.3.1 b))

(check-expect (sum-integers:1.3.1:2 1 10) 55)

(define (pi-sum:1.3.1:2 a b)
(define (pi-term x)
(/ 1.0 (* x (+ x 2))))
(define (pi-next x)
(+ x 4))
(sum pi-term a pi-next b))

(check-expect (* 8 (pi-sum:1.3.1:2 1 1000)) 3.139592655589783)

(define (integral f a b dx)
(define (add-dx x) (+ x dx))
(* (sum f (+ a (/ dx 2.0)) add-dx b)
dx))

(check-expect-approx (integral cube 0 1 0.01) 0.24998750000000042)
(check-expect-approx (integral cube 0 1 0.001) 0.249999875000001)

;; 1.3.2  Constructing Procedures Using Lambda

(define (pi-sum:1.3.2 a b)
(sum (lambda (x) (/ 1.0 (* x (+ x 2))))
a
(lambda (x) (+ x 4))
b))

(define (integral:1.3.2 f a b dx)
(* (sum f
(+ a (/ dx 2.0))
(lambda (x) (+ x dx))
b)
dx))

(define (plus4:1 x) (+ x 4))

(define plus4:2 (lambda (x) (+ x 4)))

(check-expect ((lambda (x y z) (+ x y (square z))) 1 2 3) 12)

(define (f:1.3.2:1 x y)
(define (f-helper a b)
(+ (* x (square a))
(* y b)
(* a b)))
(f-helper (+ 1 (* x y))
(- 1 y)))

(define (f:1.3.2:2 x y)
((lambda (a b)
(+ (* x (square a))
(* y b)
(* a b)))
(+ 1 (* x y))
(- 1 y)))

(define (f:1.3.2:3 x y)
(let ((a (+ 1 (* x y)))
(b (- 1 y)))
(+ (* x (square a))
(* y b)
(* a b))))

(check-expect (let ((x 5))
(+ (let ((x 3))
(+ x (* x 10)))
x))
38)

(check-expect (let ((x 2))
(let ((x 3)
(y (+ x 2)))
(* x y)))
12)

(define (f:1.3.2:4 x y)
(define a (+ 1 (* x y)))
(define b (- 1 y))
(+ (* x (square a))
(* y b)
(* a b)))

;; Exercise 1.34

(define (f:e.1.34 g)
(g 2))

(check-expect (f:e.1.34 square) 4)

(check-expect (f:e.1.34 (lambda (z) (* z (+ z 1)))) 6)

;; 1.3.3  Procedures as General Methods

(define (search f neg-point pos-point)
(let ((midpoint (average neg-point pos-point)))
(if (close-enough? neg-point pos-point)
midpoint
(let ((test-value (f midpoint)))
(cond ((positive? test-value)
(search f neg-point midpoint))
((negative? test-value)
(search f midpoint pos-point))
(else midpoint))))))

(define (close-enough? x y)
(< (abs (- x y)) 0.001))

(define (half-interval-method f a b)
(let ((a-value (f a))
(b-value (f b)))
(cond ((and (negative? a-value) (positive? b-value))
(search f a b))
((and (negative? b-value) (positive? a-value))
(search f b a))
(else
(error "Values are not of opposite sign" a b)))))

(check-expect-approx (half-interval-method sin 2.0 4.0) 3.14111328125)

(check-expect-approx (half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))
1.0
2.0)
1.89306640625)

(define tolerance 0.00001)

(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))

(check-expect-approx (fixed-point cos 1.0) 0.7390822985224023)

(check-expect-approx (fixed-point (lambda (y) (+ (sin y) (cos y)))
1.0)
1.2587315962971173)

(define (sqrt:1.3.3 x)
(fixed-point (lambda (y) (average y (/ x y)))
1.0))

;; 1.3.4  Procedures as Returned Values

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

(check-expect ((average-damp square) 10) 55)

(define (sqrt:1.3.4:1 x)
(fixed-point (average-damp (lambda (y) (/ x y)))
1.0))

(define (cube-root x)
(fixed-point (average-damp (lambda (y) (/ x (square y))))
1.0))

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

(define dx 0.00001)

(define (cube:1.3.4 x) (* x x x))

(check-expect-approx ((deriv cube:1.3.4) 5) 75.00014999664018)

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

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

(define (sqrt:1.3.4:2 x)
(newtons-method (lambda (y) (- (square y) x))
1.0))

(define (fixed-point-of-transform g transform guess)
(fixed-point (transform g) guess))

(define (sqrt:1.3.4:3 x)
(fixed-point-of-transform (lambda (y) (/ x y))
average-damp
1.0))

(define (sqrt:1.3.4:4 x)
(fixed-point-of-transform (lambda (y) (- (square y) x))
newton-transform
1.0))

;;EOF

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; \$Id: test.rkt,v 1.4 2011/05/02 09:25:47 neilpair Exp \$

;; Chapter 2

(define (linear-combination a b x y)
(+ (* a x) (* b y)))

;; 2.1.1  Example: Arithmetic Operations for Rational Numbers

(make-rat (+ (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))

(define (sub-rat x y)
(make-rat (- (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (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))))

(define x:2.1.1:1 (cons 1 2))

(check-expect (car x:2.1.1:1) 1)
(check-expect (cdr x:2.1.1:1) 2)

(define x:2.1.1:2 (cons 1 2))

(define y:2.1.1:2 (cons 3 4))

(define z:2.1.1:2 (cons x:2.1.1:2 y:2.1.1:2))

(check-expect (car (car z:2.1.1:2)) 1)
(check-expect (car (cdr z:2.1.1:2)) 3)

(define (make-rat n d) (cons n d))

(define (numer x) (car x))

(define (denom x) (cdr x))

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

(define one-half (make-rat 1 2))

;; TODO: check-expect-output
;;
;; (print-rat one-half)
;; 1/2

(define one-third (make-rat 1 3))

;; 5/6

;; (print-rat (mul-rat one-half one-third))
;; 1/6

;; 6/9

;; (define (make-rat n d)
;;   (let ((g (gcd n d)))
;;     (cons (/ n g) (/ d g))))
;;
;; 2/3

;; 2.1.2  Abstraction Barriers

(define (make-rat n d)
(cons n d))

(define (numer x)
(let ((g (gcd (car x) (cdr x))))
(/ (car x) g)))

(define (denom x)
(let ((g (gcd (car x) (cdr x))))
(/ (cdr x) g)))

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

(lambda (f) (lambda (x) (f ((n f) x)))))

;; 2.1.4  Extended Exercise: Interval Arithmetic

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

(define (mul-interval 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 (div-interval x y)
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))

(define (make-interval a b) (cons a b))

(define (lower-bound x) 0) ;; Placeholder
(define (upper-bound x) 0) ;; Placeholder

;; Exercise 2.11

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

(define (center i)
(/ (+ (lower-bound i) (upper-bound i)) 2))

(define (width i)
(/ (- (upper-bound i) (lower-bound i)) 2))

;; Exercise 2.13

(define (par1 r1 r2)
(div-interval (mul-interval r1 r2)

(define (par2 r1 r2)
(let ((one (make-interval 1 1)))
(div-interval one
(div-interval one r2)))))

;; 2.2.1  Representing Sequences

(define one-through-four (list 1 2 3 4))

(check-expect one-through-four '(1 2 3 4))
(check-expect (car one-through-four) 1)
(check-expect (cdr one-through-four) '(2 3 4))
(check-expect (car (cdr one-through-four)) 2)
(check-expect (cons 10 one-through-four) '(10 1 2 3 4))
(check-expect (cons 5 one-through-four) '(5 1 2 3 4))

(define (list-ref:2.2.1 items n)
(if (= n 0)
(car items)
(list-ref:2.2.1 (cdr items) (- n 1))))

(define squares (list 1 4 9 16 25))

(check-expect (list-ref:2.2.1 squares 3) 16)

(define (length:2.2.1:1 items)
(if (null? items)
0
(+ 1 (length (cdr items)))))

(define odds (list 1 3 5 7))

(check-expect (length:2.2.1:1 odds) 4)

(define (length:2.2.1:2 items)
(define (length-iter a count)
(if (null? a)
count
(length-iter (cdr a) (+ 1 count))))
(length-iter items 0))

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

(check-expect (append:2.2.1 squares odds) '(1 4 9 16 25 1 3 5 7))
(check-expect (append:2.2.1 odds squares) '(1 3 5 7 1 4 9 16 25))

;; Exercise 2.19

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

(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 (except-first-denomination coin-values) 0) ; Placeholder
(define (first-denomination coin-values) 0) ; Placeholder

;; Mapping over lists

(define (scale-list:2.2.1:1 items factor)
(if (null? items)
nil
(cons (* (car items) factor)
(scale-list:2.2.1:1 (cdr items) factor))))

(check-expect (scale-list:2.2.1:1 (list 1 2 3 4 5) 10) '(10 20 30 40 50))

(define (map:2.2.1 proc items)
(if (null? items)
nil
(cons (proc (car items))
(map:2.2.1 proc (cdr items)))))

(check-expect (map:2.2.1 abs (list -10 2.5 -11.6 17)) '(10 2.5 11.6 17))
(check-expect (map:2.2.1 (lambda (x) (* x x)) (list 1 2 3 4))
'(1 4 9 16))

(define (scale-list:2.2.1:2 items factor)
(map:2.2.1 (lambda (x) (* x factor))
items))

;; 2.2.2  Hierarchical Structures

(define (count-leaves x)
(cond ((null? x) 0)
((not (pair? x)) 1)
(else (+ (count-leaves (car x))
(count-leaves (cdr x))))))

(define x:2.2.2 (cons (list 1 2) (list 3 4)))

(check-expect (length x:2.2.2) 3)
(check-expect (count-leaves x:2.2.2) 4)
(check-expect (list x:2.2.2 x:2.2.2) '(((1 2) 3 4) ((1 2) 3 4)))
(check-expect (length (list x:2.2.2 x:2.2.2)) 2)
(check-expect (count-leaves (list x:2.2.2 x:2.2.2)) 8)

(define (scale-tree:2.2.2:1 tree factor)
(cond ((null? tree) nil)
((not (pair? tree)) (* tree factor))
(else (cons (scale-tree:2.2.2:1 (car tree) factor)
(scale-tree:2.2.2:1 (cdr tree) factor)))))
(check-expect (scale-tree:2.2.2:1 (list 1 (list 2 (list 3 4) 5) (list 6 7))
10)
'(10 (20 (30 40) 50) (60 70)))

(define (scale-tree:2.2.2:2 tree factor)
(map (lambda (sub-tree)
(if (pair? sub-tree)
(scale-tree:2.2.2:2 sub-tree factor)
(* sub-tree factor)))
tree))

(define (sum-odd-squares:2.2.2:1 tree)
(cond ((null? tree) 0)
((not (pair? tree))
(if (odd? tree) (square tree) 0))
(else (+ (sum-odd-squares:2.2.2:1 (car tree))
(sum-odd-squares:2.2.2:1 (cdr tree))))))

(define (even-fibs:2.2.2:1 n)
(define (next k)
(if (> k n)
nil
(let ((f (fib k)))
(if (even? f)
(cons f (next (+ k 1)))
(next (+ k 1))))))
(next 0))

;; TODO: Added from test-ch-1.ss.  Perhaps combine all into one file?
(define (square x) (* x x))

(check-expect (map square (list 1 2 3 4 5)) '(1 4 9 16 25))

;; Sequence Operations

(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))

(check-expect (filter odd? (list 1 2 3 4 5)) '(1 3 5))

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

(check-expect (accumulate + 0 (list 1 2 3 4 5)) 15)
(check-expect (accumulate * 1 (list 1 2 3 4 5)) 120)
(check-expect (accumulate cons nil (list 1 2 3 4 5)) '(1 2 3 4 5))

(define (enumerate-interval low high)
(if (> low high)
nil
(cons low (enumerate-interval (+ low 1) high))))

(check-expect (enumerate-interval 2 7) '(2 3 4 5 6 7))

(define (enumerate-tree tree)
(cond ((null? tree) nil)
((not (pair? tree)) (list tree))
(else (append (enumerate-tree (car tree))
(enumerate-tree (cdr tree))))))

(check-expect (enumerate-tree (list 1 (list 2 (list 3 4)) 5)) '(1 2 3 4 5))

;; TODO: Added from test-ch-1.ss.  Perhaps combine all into one file?
(define (fib:2 n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))

(define (sum-odd-squares tree)
(accumulate +
0
(map square
(filter odd?
(enumerate-tree tree)))))

(define (even-fibs:2.2.3 n)
(accumulate cons
nil
(filter even?
(map fib:2
(enumerate-interval 0 n)))))

(define (list-fib-squares n)
(accumulate cons
nil
(map square
(map fib:2
(enumerate-interval 0 n)))))

(check-expect (list-fib-squares 10) '(0 1 1 4 9 25 64 169 441 1156 3025))

(define (product-of-squares-of-odd-elements sequence)
(accumulate *
1
(map square
(filter odd? sequence))))

(check-expect (product-of-squares-of-odd-elements (list 1 2 3 4 5)) 225)

(define (fold-left op initial sequence)
(define (iter result rest)
(if (null? rest)
result
(iter (op result (car rest))
(cdr rest))))
(iter initial sequence))

;; Nested Mappings

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

(define (prime-sum? pair)
(prime? (+ (car pair) (cadr pair))))

(define (prime? x) #f) ;; Placeholder

(define (make-pair-sum pair)

(define (prime-sum-pairs n)
(map make-pair-sum
(filter prime-sum?
(flatmap
(lambda (i)
(map (lambda (j) (list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))))

(define (permutations s)
(if (null? s)                    ; empty set?
(list nil)                   ; sequence containing empty set
(flatmap (lambda (x)
(map (lambda (p) (cons x p))
(permutations (remove x s))))
s)))

(define (remove item sequence)
(filter (lambda (x) (not (= x item)))
sequence))

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

;; TODO: !!! Continue starting from 2.2.4 (picture language)

;; 2.3.1  Quotation

(check-expect (list 'a 'b) '(a b))
(check-expect (car '(a b c)) 'a)
(check-expect (cdr '(a b c)) '(b c))

(define (memq:2.3.1 item x)
(cond ((null? x) false)
((eq? item (car x)) x)
(else (memq:2.3.1 item (cdr x)))))

(check-expect (memq:2.3.1 'apple '(pear banana prune)) #f)
(check-expect (memq:2.3.1 'apple '(x (apple sauce) y apple pear)) '(apple pear))

;; Exercise 2.55

;; 2.3.2  Example: Symbolic Differentiation

;; The differentiation program with abstract data

(define (deriv:1 exp var)
(cond ((number? exp) 0)
((variable? exp)
(if (same-variable? exp var) 1 0))
((sum? exp)
(deriv:1 (augend exp) var)))
((product? exp)
(make-sum:1
(make-product:1 (multiplier exp)
(deriv:1 (multiplicand exp) var))
(make-product:1 (deriv:1 (multiplier exp) var)
(multiplicand exp))))
(else
(error "unknown expression type -- DERIV" exp))))

;; Representing algebraic expressions

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
(and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (make-sum:1 a1 a2) (list '+ a1 a2))

(define (make-product:1 m1 m2) (list '* m1 m2))

(define (sum? x)
(and (pair? x) (eq? (car x) '+)))

(define (product? x)
(and (pair? x) (eq? (car x) '*)))

(check-expect (deriv:1 '(+ x 3) 'x) '(+ 1 0))
(check-expect (deriv:1 '(* x y) 'x) '(+ (* x 0) (* 1 y)))
(check-expect (deriv:1 '(* (* x y) (+ x 3)) 'x)
'(+ (* (* x y) (+ 1 0))
(* (+ (* x 0) (* 1 y))
(+  x 3))))

;;

(define (make-sum:2 a1 a2)
(cond ((=number? a1 0) a2)
((=number? a2 0) a1)
((and (number? a1) (number? a2)) (+ a1 a2))
(else (list '+ a1 a2))))

(define (=number? exp num)
(and (number? exp) (= exp num)))

(define (make-product:2 m1 m2)
(cond ((or (=number? m1 0) (=number? m2 0)) 0)
((=number? m1 1) m2)
((=number? m2 1) m1)
((and (number? m1) (number? m2)) (* m1 m2))
(else (list '* m1 m2))))

(define (deriv:2 exp var)
(cond ((number? exp) 0)
((variable? exp)
(if (same-variable? exp var) 1 0))
((sum? exp)
(deriv:2 (augend exp) var)))
((product? exp)
(make-sum:2
(make-product:2 (multiplier exp)
(deriv:2 (multiplicand exp) var))
(make-product:2 (deriv:2 (multiplier exp) var)
(multiplicand exp))))
(else
(error "unknown expression type -- DERIV" exp))))

(check-expect (deriv:2 '(+ x 3) 'x) 1)
(check-expect (deriv:2 '(* x y) 'x) 'y)
(check-expect (deriv:2 '(* (* x y) (+ x 3)) 'x) '(+ (* x y) (* y (+ x 3))))

;; 2.3.3  Example: Representing Sets

;; Sets as unordered lists

(define (element-of-set?:1 x set)
(cond ((null? set) false)
((equal? x (car set)) true)
(else (element-of-set?:1 x (cdr set)))))

(if (element-of-set?:1 x set)
set
(cons x set)))

(define (intersection-set:1 set1 set2)
(cond ((or (null? set1) (null? set2)) '())
((element-of-set?:1 (car set1) set2)
(cons (car set1)
(intersection-set:1 (cdr set1) set2)))
(else (intersection-set:1 (cdr set1) set2))))

;; Sets as ordered lists

(define (element-of-set?:2 x set)
(cond ((null? set) false)
((= x (car set)) true)
((< x (car set)) false)
(else (element-of-set?:2 x (cdr set)))))

(define (intersection-set:2 set1 set2)
(if (or (null? set1) (null? set2))
'()
(let ((x1 (car set1)) (x2 (car set2)))
(cond ((= x1 x2)
(cons x1
(intersection-set:2 (cdr set1)
(cdr set2))))
((< x1 x2)
(intersection-set:2 (cdr set1) set2))
((< x2 x1)
(intersection-set:2 set1 (cdr set2)))))))

;; Sets as binary trees

(define (entry:3 tree) (car tree))
(define (make-tree:3 entry left right)
(list entry left right))

(define (element-of-set?:3 x set)
(cond ((null? set) false)
((= x (entry:3 set)) true)
((< x (entry:3 set))
(element-of-set?:3 x (left-branch:3 set)))
((> x (entry:3 set))
(element-of-set?:3 x (right-branch:3 set)))))

(cond ((null? set) (make-tree:3 x '() '()))
((= x (entry:3 set)) set)
((< x (entry:3 set))
(make-tree:3 (entry:3 set)
(right-branch:3 set)))
((> x (entry:3 set))
(make-tree:3 (entry:3 set)
(left-branch:3 set)

;; Exercise 2.63

(define (tree->list-1:3 tree)
(if (null? tree)
'()
(append (tree->list-1:3 (left-branch:3 tree))
(cons (entry:3 tree)
(tree->list-1:3 (right-branch:3 tree))))))

(define (tree->list-2:3 tree)
(define (copy-to-list tree result-list)
(if (null? tree)
result-list
(copy-to-list (left-branch:3 tree)
(cons (entry:3 tree)
(copy-to-list (right-branch:3 tree)
result-list)))))
(copy-to-list tree '()))

;; Exercise 2.64

(define (list->tree:3 elements)
(car (partial-tree:3 elements (length elements))))

(define (partial-tree:3 elts n)
(if (= n 0)
(cons '() elts)
(let ((left-size (quotient (- n 1) 2)))
(let ((left-result (partial-tree:3 elts left-size)))
(let ((left-tree (car left-result))
(non-left-elts (cdr left-result))
(right-size (- n (+ left-size 1))))
(let ((this-entry (car non-left-elts))
(right-result (partial-tree:3 (cdr non-left-elts)
right-size)))
(let ((right-tree (car right-result))
(remaining-elts (cdr right-result)))
(cons (make-tree:3 this-entry left-tree right-tree)
remaining-elts))))))))

;; Sets and information retrieval

(define (lookup given-key set-of-records)
(cond ((null? set-of-records) false)
((equal? given-key (key (car set-of-records)))
(car set-of-records))
(else (lookup given-key (cdr set-of-records)))))

(define (key x) #f) ;; Placeholder
```