https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm

https://github.com/DeathKing/Learning-SICP

https://mitpress.mit.edu/sites/default/files/sicp/index.html

https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454

http://community.schemewiki.org/?SICP-Solutions

http://community.schemewiki.org/?sicp

#### 3.63(p235)

(sqrt-stream x)

(stream-map (lambda (guess)
(sqrt-improve guess x))
(sqrt-stream x)))

(stream-map (lambda (guess)
(sqrt-improve guess x))
(cons-stream 1 ...)))

(define (sqrt-stream x)
(define guesses
(cons-stream 1.0
(stream-map (lambda (guess)
(sqrt-improve guess x))
guesses)))
guesses)

#### 3.64(p235)

(load "stream.scm")

(define (stream-limit s d)
(let ((s1 (stream-ref s 0))
(s2 (stream-ref s 1)))
(if (< (abs (- s1 s2)) d)
s2
(stream-limit (stream-cdr s) d))))

; test
(define (sqrt x tolerance)
(stream-limit (sqrt-stream x) tolerance))

(define x0 (sqrt 2 1))
x0

(define x1 (sqrt 2 0.1))
x1

(define x2 (sqrt 2 0.01))
x2

(exit)

1 ]=> (define x0 (sqrt 2 1))
;Value: x0

1 ]=> x0
;Value: 1.5

1 ]=> (define x1 (sqrt 2 0.1))
;Value: x1

1 ]=> x1
;Value: 1.4166666666666665

1 ]=> (define x2 (sqrt 2 0.01))
;Value: x2

1 ]=> x2
;Value: 1.4142156862745097

#### 3.65(p235)

(load "stream.scm")

(define (log2-stream n)
(cons-stream (/ 1.0 n)
(stream-map - (log2-stream (+ n 1)))))

(define log2-v1
(partial-sums (log2-stream 1)))

(define log2-v2
(euler-transform log2-v1))

(define log2-v3
(accelerated-sequence euler-transform log2-v1))

; test
(define log2 (log 2))
log2

(stream-head log2-v3 5)

1 ]=> log2
;Value: .6931471805599453

1 ]=> (stream-head log2-v1 5)
;Value 13: (1. .5 .8333333333333333 .5833333333333333 .7833333333333332)

1 ]=> (stream-head log2-v2 5)
;Value 14: (.7 .6904761904761905 .6944444444444444 .6924242424242424 .6935897435897436)

1 ]=> (stream-head log2-v3 5)
;Value 15: (1. .7 .6932773109243697 .6931488693329254 .6931471960735491)

#### 3.66(p237)

1	2	4	6	8	10	12
3	5	9	13	17	21
7	11	19	27	35
15	23	39	54

• 第$(i,i)$项的序号为$2^{i}-1$
• 第$(i,i+1)$项的序号为$2^{i}-1 + 2^{i-1}=3\times 2^{i-1}-1$
• 第$i$行从第二项起为等差数列，公差为$2^i$
• 第$(i,j),j>i$项的序号为$3\times 2^{i-1}- 1 + (j- i-1)\times 2^i$

1	2
3

3	5
7

#### 3.67(p237)

(load "stream.scm")

(define (pairs s t)
(cons-stream
(list (stream-car s) (stream-car t))
(interleave
(interleave
(stream-map (lambda (x) (list (stream-car s) x))
(stream-cdr t))
(stream-map (lambda (x) (list x (stream-car t)))
(stream-cdr t)))
(pairs (stream-cdr s) (stream-cdr t)))))

; test
(define s (pairs integers integers))

(stream-head s 10)

1 ]=> (stream-head s 10)
;Value 13: ((1 1) (1 2) (2 2) (2 1) (2 3) (1 3) (3 3) (3 1) (3 2) (1 4))

#### 3.68(p237)

http://community.schemewiki.org/?sicp-ex-3.68

https://github.com/kana/sicp/blob/master/ex-3.68.md

• (pairs integers integers)
• 调用interleave
• 运行(stream-map (lambda (x) (list (stream-car s) x)) t)
• 运行(pairs (stream-cdr s) (stream-cdr t))

(load "stream.scm")

(define (pairs s t)
(interleave
(stream-map (lambda (x) (list (stream-car s) x))
t)
(pairs (stream-cdr s) (stream-cdr t))))

; test
(define s (pairs integers integers))

(stream-head s 10)

1 ]=> ; test
(define s (pairs integers integers))
;Aborting!: maximum recursion depth exceeded

#### 3.69(p238)

(load "stream.scm")

(define (interleaves s1 s2 s3)
(interleave s1
(interleave s2 s3)))

(define (triples s t u)
(cons-stream
(list
(stream-car s)
(stream-car t)
(stream-car u))
(interleaves
(stream-map
(lambda (x)
(list (stream-car s) (stream-car t) x))
(stream-cdr u))
(stream-map
(lambda (x)
(cons (stream-car s) x))
(pairs
(stream-cdr t)
(stream-cdr u)))
(triples
(stream-cdr s)
(stream-cdr t)
(stream-cdr u)))))

(define (pred arr)
(let ((i (car arr))
(= (+ (square i)
(square j))
(square k))))

(define integers (integers-starting-from 1))

; test
(define s (triples integers integers integers))
(define pythagorean (stream-filter pred s))

(stream-head pythagorean 2)

1 ]=> (stream-head pythagorean 2)
;Value 13: ((3 4 5) (6 8 10))

#### 3.70(p238)

http://community.schemewiki.org/?sicp-ex-3.70

(load "stream.scm")

(define (merge weight s1 s2)
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else
(let ((s1car (stream-car s1))
(s2car (stream-car s2)))
(cond ((< (weight s1car) (weight s2car))
(cons-stream s1car (merge weight (stream-cdr s1) s2)))
((> (weight s1car) (weight s2car))
(cons-stream s2car (merge weight s1 (stream-cdr s2))))
(else
(cons-stream s1car
(cons-stream s2car
(merge weight (stream-cdr s1)
(stream-cdr s2))))))))))

(define (weighted-pairs weight s t)
(cons-stream
(list (stream-car s) (stream-car t))
(merge weight
(stream-map (lambda (x) (list (stream-car s) x))
(stream-cdr t))
(weighted-pairs weight (stream-cdr s) (stream-cdr t)))))

(define (weight1 arr)
(let ((i (car arr))
(+ i j)))

(define (weight2 arr)
(let ((i (car arr))
(+ (* 2 i)
(* 3 j)
(* 5 i j))))

; test
; (a)
(define s1 (weighted-pairs weight1 integers integers))

; (b)
(define s2 (weighted-pairs weight2 integers integers))
(stream-head s2 10)

1 ]=> (stream-head s1 10)
;Value 13: ((1 1) (1 2) (1 3) (2 2) (1 4) (2 3) (1 5) (2 4) (3 3) (1 6))

1 ]=> (stream-head s2 10)
;Value 14: ((1 1) (1 2) (1 3) (2 2) (1 4) (1 5) (2 3) (1 6) (2 4) (1 7))

#### 3.71(p238)

http://community.schemewiki.org/?sicp-ex-3.71

(load "stream.scm")

(define (weight arr)
(let ((i (car arr))
(+ (cube i) (cube j))))

(define s (weighted-pairs weight integers integers))

(define (ramanujan s)
(define (ramanujan-iter s d)
(let ((s1 (stream-car s))
(s2 (stream-car (stream-cdr s))))
(cond ((not (= (weight s1) d)) (ramanujan-iter (stream-cdr s) (weight s1)))
((= (weight s2) d) (ramanujan-iter (stream-cdr s) (weight s1)))
(else (cons-stream (weight s1) (ramanujan-iter (stream-cdr s) (weight s1)))))))
(ramanujan-iter s 0))

; test
(define Ramanujan (ramanujan s))

(stream-head Ramanujan 6)

1 ]=> (stream-head Ramanujan 6)
;Value 13: (1729 4104 13832 20683 32832 39312)

• 对于函数(ramanujan-iter s d)，d表示当前处理的值。
• ((not (= (weight s1) d)) (ramanujan-iter (stream-cdr s) (weight s1)))对应(d, (a, … ))情形。
• ((= (weight s2) d) (ramanujan-iter (stream-cdr s) (weight s1)))对应(d, (d, d, …))情形。
• else对应(d, (d, d’, …))情形，该情形产生Ramanujan数。

#### 3.72(p238)

(load "stream.scm")

(define (weight arr)
(let ((i (car arr))
(+ (square i) (square j))))

(define (pythagorean s)
(define (pythagorean-iter s d cnt arr)
(let ((s1 (stream-car s))
(s2 (stream-car (stream-cdr s))))
(cond ((not (= (weight s1) d)) (pythagorean-iter (stream-cdr s) (weight s1) 1 (cons s1 '())))
((= (weight s2) d) (pythagorean-iter (stream-cdr s) (weight s1) (+ cnt 1) (cons s2 arr)))
((= cnt 3) (cons-stream
(list (weight s1) arr)
(pythagorean-iter (stream-cdr s) (weight s2) 1 (cons s2 '()))))
(else (pythagorean-iter (stream-cdr s) (weight s2) 1 (cons s2 '()))))))
(pythagorean-iter s 0 1 '()))

(define s (weighted-pairs weight integers integers))
(stream-head s1 5)
1 ]=> ; test
;Value 14: ((325 ((10 15) (6 17) (1 18))) (425 ((13 16) (8 19) (5 20))) (650 ((17 19) (11 23) (5 25))) (725 ((14 23) (10 25) (7 26))) (845 ((19 22) (13 26) (2 29))))