SICP-Refresher-Chapter-2(3)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

(list 'a 'b 'c)				;(a b c)

(list (list 'george))			;((george))

(cdr '((x1 x2) (y1 y2)))		;((y1 y2))

(cadr '((x1 x2) (y1 y2)))		;(y1 y2)

(pair? (car '(a short list)))		;false

(define (memq item x)
  (cond ((null? x) #f)
	((eq? item (car x)) x)
	(else (memq item (cdr x)))))

(memq 'red '((red shoes) (blue socks)))	;#f

(memq 'red '(red shoes blue socks))	;(red shoes blue socks)

1
2
3
4
5
6
7
8
9

(define (equal? items1 items2)
  (cond ((and (pair? items1) (pair? items2))
	 (and
	  (equal? (car items1) (car items2))
	  (equal? (cdr items1) (cdr items2))))
	((and (symbol? items1) (symbol? items2))
	 (eq? items1 items2))
	((and (null? items1) (null? items2)) #t)
	(else #f)))

1
2
3
4
5
6
7

(car ''abracadabra)			;quote

;; (quote (quote abracadabra))
;; 第一个 quote 表示引用它的下一个对象，将它看作数据对象而不是应该求值的表达式；

;; 所以这个表达式就是一个输出格式为 (quote abracadabra) 的符号表，对它应用 car
;; 取得表的一个元素－符号 quote

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

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

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

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

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

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

(define (make-product 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 (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (addend s) (cadr s))

;; 2.57
(define (augend s)
  (if (null? (cddr s))
      0
      (cons '+ (cddr s))))

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

(define (multiplier p) (cadr p))

;; 2.57
(define (multiplicand p)
  (if (null? (cddr p))
      1
      (cons '* (cddr p))))

;; 2.56
(define (exponentiation? x)
  (and (pair? x) (eq? (car x) '**)))

(define (exponent x)
  (caddr x))

(define (base x)
  (cadr x))

(define (make-exponentiation base exponent)
  (cond ((=number? exponent 0) 1)
	((=number? exponent 1) base)
	((=number? base 1) 1)
	(else (list '** base exponent))))

1
2
3
4
5
6

(define(union-set set1 set2)
  (cond ((null? set1) set2)
	((null? set2) set1)
	((element-of-set? (car set1) set2)
	 (union-set (cdr set1) set2))
	(else (cons (car set1) (union-set (cdr set1) set2)))))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

(define (adjoin-set x set)
  (cons x set))

(define (remove-set-element x set)
  (define (remove-set-element-iter acc rest)
    (cond ((null? rest) acc)
	  ((equal? x (car rest)) (append acc (cdr rest)))
	  (else (remove-set-element-iter (adjoin-set (car rest) acc) (cdr rest))))) ;literally intersection
   (remove-set-element-iter '() set))

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

(define (union-set set1 set2)
  (append set1 set2))

1
2
3

;; adjoin-set 的代码不变，只是内部使用的 element-of-set? 是新的基于排序集合的版本；
;; adjoin-set 的效率完全依赖于 element-of-set?，所以平均所需步数和它一样；
;; 但是正如 p105 译者注，排序的集合和未排序的集合使用查找操作的期望查找长度其实是一样的。

1
2
3
4
5
6
7
8
9

(define (union-set set1 set2)
  (cond ((null? set1) set2)
	((null? set2) set1)
	((= (car set1) (car set2))
	 (cons (car set1) (union-set (cdr set1) (cdr set2))))
	((< (car set1) (car set2))
	 (cons (car set1) (union-set (cdr set1) set2)))
	((< (car set2) (car set1))
	 (cons (car set2) (union-set set1 (cdr set2))))))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

;; a

;; 结果是一样的；
;; (1 3 5 7 9 11)

;; b

;; 第一个的增长速度 theta(nlog(n))
;; 第二个是 theta(n)
;; 至于是如何得出的请查看《算法导论》4.5节。

1
2
3
4
5
6
7
8
9

;; a

;; partial-tree 的分解过程网上有解释
;; （代码绕来绕去，并不是 sicp 的侧重点）
;; (5 (1 '() 3) (9 7 11))
;; ...

;; c
;; theta(n)

1
2
3
4
5
6
7
8
9

;; theta(n) + theta(n) + theta(n) = theta(n)

(define (union-set tree1 tree2)
  (list->tree (union-set-sorted-list (tree->list-2 tree1)
				     (tree->list-2 tree2))))

(define (intersection-set tree1 tree2)
  (list->tree (intersection-set-sorted-list (tree->list-2 tree1)
					    (tree->list-2 tree2))))

1
2
3
4
5
6
7
8

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) false)
	((= given-key (key (entry set-of-records)))
	 (entry set-of-records))
	((> given-key (key (entry set-of-records)))
	 (lookup given-key (right-branch set-of-records)))
	((< given-key (key (entry set-of-records)))
	 (lookup given-key (left-branch set-of-records)))))

1

;(a d a b b c a)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
	      (encode (cdr message) tree))))

(define (encode-symbol symbol tree)
  (cond ((leaf? tree) '())
	((memq symbol (symbols (left-branch tree)))
	 (cons 0 (encode-symbol symbol (left-branch tree))))
	((memq symbol (symbols (right-branch tree))) (cons 1 (encode-symbol symbol (right-branch tree))))
	(else (error "bad symbol not in tree" symbol tree))))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

(define (successive-merge ordered-pairs)
  (if (null? (cdr ordered-pairs))
      (car ordered-pairs)
      (let ((left (cddr ordered-pairs))
	    (left-branch (car ordered-pairs))
	    (right-branch (cadr ordered-pairs)))
	(let ((sub-tree (make-code-tree
			 left-branch
			 right-branch)))
	  (successive-merge (adjoin-set sub-tree left))))))

1
2
3
4
5
6
7
8
9

(define pairs '((A 2) (NA 16) (BOOM 1) (SHA 3) (GET 2) (YIP 9) (JOB 2) (WAH 1)))

(define rock-tree (generate-huffman-tree pairs))

(define song '(Get a job Sha na na na na na na na na Get a job Sha na na na na na na na na Wah yip yip yip yip yip yip yip yip yip Sha boom))

(define tree-bits (encode song rock-tree)) ;84

(define normal-bits (* 3 (length song))) ;108, it needs three bits to represent a symbol whose system contains 8 elements

1
2
3
4
5
6
7

;; 这样的题目关注的并不是 sicp 的侧重点，不需要纠结。

;; just like a triangle with serveral parallel lines inside it, key world: similar triangle

;; the minimum number of bits: 1

;; the maximum number of bits: (- n 1)

1
2
3
4
5
6
7

;; 此题和上一题一样并不需要纠结....
;; the increasing speed of steps theta(n)
;; 根据算法导论章节4.5主方法推得；

;; the most frequency one: theta(1)

;; the least frequency one: O((expt n 2)) due to the memq operation in every search deeper