SICP 全笔记

无限流

因为 stream 可以延迟之后将要做的操作,所以可以使用 stream 来产生一个无限大的数字序列。

在这个序列中,我们可以要多少取多少,不用担心序列是否会被取完。

搭配上 stream-filter,我们就可以使用 sieve 算法来生成无限大的素数序列了。

理解隐式定义的流

定义无限的整数流可以使用如下两种形式

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

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

(define ones (cons-stream 1 ones))

(define integers (cons-stream 1 (add-streams ones integers)))

对第一种形式,我们应该比较容易理解,因为流在递归一个过程,这个过程将产生流的下一个值与其后的一个 promise。使用替换模型来解释程序,则 integers 为:

(cons-stream 1 (cons-stream 2 (cons-stream 3 (cons-stream 4 ..))))

对第二种形式,integers 流将自己毫无变动地传递到了一个过程中以产生下一个值。我们可以如下来看这个替换模型:

(cons-stream 1
             ; #[promise 1] expanded from (stream-map + (1 . #[Promise 1]) ..)
             (cons-stream (+ (stream-car s)
                             (stream-car s))
                          ;#[promise 2] <= (stream-map + (2 . #[promise 2]) ..)
                          (cons-stream (+ (stream-car s)
                                          (stream-car s))
                                       ;#[primise 3]
                                       (stream-map + (cdr-stream s) (cdr-stream s))))

当运行 #[promise 1] 时,s 为 (1 . #[promise 1]) 所以 stream-car 是 1;两个相加之后变为 2

#[promise 2] 中 s 实际为 (2 . #[promise 2]),所以 stream-car 是 2,两个相加之后变为 4

运行到 #[promise 3] 的时候,s 实际为 (4 . #[promise 3]),所以 stream-car 是 8。以此类推。