无穷流

引言

我们已经看到如何营造「操作整条流」的假象，而实际上只计算需要的那一部分。利用这一技术，即便是很长的序列，我们也能高效地把它表示为流。但更重要的是，我们可以用流来表示无穷长的序列。例如，假设我们定义：

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

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

那么 integers 就表示全体正整数的流。更具体地说，integers 的 stream-car 是 1，而 stream-cdr 是一个等价于 (integers-starting-from 2) 的承诺。

借助 integers，我们可以定义其他无穷流，例如不被 7 整除的整数流：

(define (divisible? x y)
  (= (remainder x y) 0))
(define no-sevens
  (stream-filter (lambda (x) (not (divisible? x 7)))
                 integers))

于是，只要访问这条流的元素，就能找到不被 7 整除的整数：

-> (stream-ref no-sevens 100)
117

流过程

到目前为止，我们定义流的方式与定义列表非常相似。现在我们换一种更「流式」的思路。

我们可以利用延迟求值来隐式地定义流。例如，可以这样定义全 1 的无穷流：

(define ones (cons-stream 1 ones))

它的工作原理与递归过程十分相似：ones 是一个 car 为 1、cdr 为「求值 ones」的承诺的序对。求值 cdr，又得到一个 1 和一个「求值 ones」的承诺，如此无限继续。

我们还可以定义流过程 add-streams，它产生两条流逐元素相加的结果：

(define (add-streams s1 s2)
  (stream-map + s1 s2))

例如，(add-streams ones ones) 会产生全 2 的流。

于是可以隐式地重新定义 integers：

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

这条定义说：integers 是一条 stream-car 为 1、stream-cdr 为 ones 与 integers 之和的流。因此，integers 的第二个元素是 1 加 integers 的第一个元素，即 2；第三个元素是 1 加第二个元素，即 3；依此类推。这个定义之所以成立，是因为在任何时刻，整数流都已经生成了足够多的部分，可以把它反馈回定义中，产生下一个整数。

stream-map 补充说明

注意，上面的例子中我们用两条流调用了 stream-map。而在此之前，我们只用一条流调用过它：

-> (define x (cons-stream 1 (cons-stream 2 (cons-stram 3 the-empty-stream))))
-> (stream-map square x)
(1 #[stream with car 4])

只要给的过程有相应数量的参数，stream-map 可以接受任意条流：

-> (stream-map + x x)
(2 #[stream with car 4])

当然，stream-map 的真实定义会略有不同，不过暂时不用操心。

我们还可以用同样的风格定义斐波那契序列：

(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs) fibs))))

这条定义说：fibs 是一条以 0 和 1 开头的流，其余部分由 fibs 与自身错开一位相加生成。

另一个可用的流操作是 scale-stream。它接受两个参数——一条整数流和一个整数——把流中所有元素乘以该整数：

(define (scale-stream strm factor)
  (stream-map (lambda (x) (* x factor)) strm))

现在可以这样定义全 2 的幂的流：

(define doubles (cons-stream 1 (scale-stream doubles 2)))

我们还可以换一种隐式的方式来定义素数的无穷流：

(define primes
  (cons-stream 2
               (stream-filter prime?
                              (integers-starting-from 3))))

这看起来相当直白——以第一个素数 2 开头，然后把从 3 开始的整数中那些是素数的接到它后面。然而，prime? 的定义方式让这个问题变得有些微妙。

我们判断一个数是否为素数，是看它能否被任何小于 $\sqrt{n}$ 的素数（不只是任何整数！）整除：

(define (prime? n)
  (define (iter ps)
    (cond ((> (square (stream-car ps)) n) #t)
          ((divisible? n (stream-car ps)) #f)
          (else (iter (stream-cdr ps)))))
  (iter primes))

这是一个递归定义（很像你在树里见过的那样），因为 primes 是用 prime? 谓词定义的，而 prime? 本身又使用了 primes 流。这个过程之所以能行，是因为在任何时刻，primes 流已经生成了足够多的部分，足以检验接下来要检查的数的素性。也就是说，对每个待检验素性的 $n$：要么 $n$ 不是素数（这种情况下，已有某个已生成的素数能整除它），要么 $n$ 是素数（这种情况下，已有某个已生成的素数——即小于 $n$ 的素数——大于 $\sqrt{n}$）。

要点总结

本节你学到了：

1. 无穷流是什么；
2. 用它们能做出的一些有趣东西。