SICP 習題參考答案，3.5

win_hate

1. 
   
2. 本貼用與存放 SICP 3.5 節(jié)的習題參考答案。為保持可讀性，請勿直接回復(fù)本貼。討論請另開新貼。
   

復(fù)制代碼

• 本節(jié)電子版: [原書連接 3.5 Stream]
  
• 答案目錄 [點這里]
  

[ 本帖最后由 win_hate 于 2008-9-13 16:59 編輯 ]

win_hate

Exercise 3.50.  Complete the following definition, which generalizes stream-map to allow procedures that take multiple arguments, analogous to map in section 2.2.3, footnote 12.

1. 
   
2. (define (stream-map proc . argstreams)
   
3.   (if (<??> (car argstreams))
   
4.       the-empty-stream
   
5.       (<??>
   
6.        (apply proc (map <??> argstreams))
   
7.        (apply stream-map
   
8.               (cons proc (map <??> argstreams))))))
   

復(fù)制代碼

[ 本帖最后由 win_hate 于 2008-9-2 15:54 編輯 ]

win_hate

1. 
   
2. (define (stream-map proc . argstreams)
   
3.   (if (stream-null? (car argstreams))
   
4.       the-empty-stream
   
5.       (cons-stream
   
6.         (apply proc (map stream-car argstreams))
   
7.         (apply stream-map
   
8.                (cons proc (map stream-cdr argstreams))))))
   

復(fù)制代碼

win_hate

Exercise 3.51.  In order to take a closer look at delayed evaluation, we will use the following procedure, which simply returns its argument after printing it:

(define (show x)
  (display-line x)
  x)

What does the interpreter print in response to evaluating each expression in the following sequence?59

(define x (stream-map show (stream-enumerate-interval 0 10)))
(stream-ref x 5)
(stream-ref x 7)

win_hate

1. 
   
2. 0       ;;<- define
   
3. 1       ;;<- ref 5
   
4. 2
   
5. 3
   
6. 4
   
7. 5
   
8. 6       ;;<- ref 7
   
9. 7
   

復(fù)制代碼

本題想說，force 有記憶。 show 有輸出的副作用，但如果只提取已有的值，則無需執(zhí)行 show.

[ 本帖最后由 win_hate 于 2009-4-15 15:36 編輯 ]

win_hate

Exercise 3.52.  Consider the sequence of expressions

1. 
   
2. (define sum 0)
   
3. (define (accum x)
   
4.   (set! sum (+ x sum))
   
5.   sum)
   
6. (define seq (stream-map accum (stream-enumerate-interval 1 20)))
   
7. (define y (stream-filter even? seq))
   
8. (define z (stream-filter (lambda (x) (= (remainder x 5) 0))
   
9.                          seq))
   
10. (stream-ref y 7)
    
11. (display-stream z)
    

復(fù)制代碼

What is the value of sum after each of the above expressions is evaluated? What is the printed response to evaluating the stream-ref and display-stream expressions? Would these responses differ if we had implemented (delay <exp>) simply as (lambda () <exp>) without using the optimization provided by memo-proc ? Explain.

[ 本帖最后由 win_hate 于 2008-9-2 16:00 編輯 ]

win_hate

[解]

1. (define seq (stream-map accum (stream-enumerate-interval 1 20)))

復(fù)制代碼

此語句執(zhí)行后，sum=1

1. (define y (stream-filter even? seq))

復(fù)制代碼

此語句執(zhí)行后， sum=1+2+3=6

1. (define z (stream-filter (lambda (x) (= (remainder x 5) 0))
   
2.                          seq))
   

復(fù)制代碼

此語句執(zhí)行后， sum=6+4=10

1. 
   
2. (stream-ref y 7)
   

復(fù)制代碼

此語句執(zhí)行時，seq 前 4 項已知，后面的要動態(tài)計算，取其中第 8 個偶數(shù)。seq 的第 n 項為正整數(shù)列的前 n 項之和 n(n+1)/2，為偶數(shù)僅當 n=3,0 (mod 4)。所以 n=3, 4, 7, 8, 11, 12, 15, 16.

(stream-ref y 7) 的值為 16(16+1)/2=136. 如果在交互環(huán)境，輸出 135，如果是腳本運行模式，沒有輸出。

1. 
   
2. (display-stream z)
   

復(fù)制代碼

此語句輸出 seq 中的全部能被 5 整除的數(shù)。n(n+1)/2 為 5 的倍數(shù)，當且僅當 n=4,0 (mod 5)。所以 n 取 4,5,9,10,14,15,19,20. 由于

(map (lambda (n) (/ (* n (+ n 1)) 2)) '(4 5 9 10 14 15 19 20))

得到

(10 15 45 55 105 120 190 210)

所以輸出為：

10
15
45
55
105
120
190
210


＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝


如果沒有使用 memo-proc 優(yōu)化，則 force 不保存首次求值的結(jié)果。

(1) define seq, sum=1

(2) define y, sum=6

(3) define z,

由于 seq 的第一項不是 promise，所以不產(chǎn)生累加 sum 的副作用。

sum=6+2+3+4=15

(4) (stream-ref y 7)

從流 y 中提第 8 個數(shù)，即用 stream-filter 在 seq 中提取第 8 個偶數(shù)。此時 seq 的通項為

s(n)=15+n(n+1)/2-6，其中 n>=4

s(n) 為偶數(shù)，相當于  n(n+1)/2=1 (mod 4)，化簡有 (n-1)(n-2)=0 (mod 4)，即 n=1,2 (mod 4)

這樣的 n 依次為 5, 6, 9, 10, 13, 14, 17. 所以 (stream-ref y 7) 的值，也就是 sum 的當前值為 s(17)=162

(5) (display-steam z)

此表達式遍歷流 z，而 z 是 stream-filter 過濾 seq, 提取 5 的倍數(shù)得到的列表。

此時 seq 的通項為：

t(n)=162+n(n+1)/2-10，其中 4 < n < 21

5|t(n)，相當于 n(n+1)/2=3 (mod 5)，化簡有 (n-2)^2=0 (5).
即 n=2 (mod 5)

這樣的 n 依次為 7, 12 17。所以該語句的輸出為：15, t(7), t(12), t(17), 即

15
180
230
305

而 sum 的當前值為 t(20)=362.

[ 本帖最后由 win_hate 于 2008-9-2 23:36 編輯 ]

win_hate

Exercise 3.53.  Without running the program, describe the elements of the stream defined by

(define s (cons-stream 1 (add-streams s s)))

win_hate

每一項是前一項的兩倍，得到序列 {2^n, n in  N}.

[ 本帖最后由 win_hate 于 2008-9-3 12:57 編輯 ]

win_hate

Exercise 3.54.  Define a procedure mul-streams, analogous to add-streams, that produces the elementwise product of its two input streams. Use this together with the stream of integers to complete the following definition of the stream whose nth element (counting from 0) is n + 1 factorial:

(define factorials (cons-stream 1 (mul-streams <??> <??>)))