在这种情况下，Racket 流是如何工作的？

Question

我目前正在学习 Racket（只是为了好玩），我偶然发现了这个例子：

(define doubles
   (stream-cons
     1
     (stream-map 
        (lambda (x) 
            (begin
                (display "map applied to: ")
                (display x)
                (newline)
                (* x 2)))
        doubles)))

它产生 1 2 4 8 16 ...

我不太明白它是如何工作的。

所以它创建了 1 作为第一个元素；当我调用 (stream-ref doubles 1) 时，它会创建第二个元素，这显然是 2.

然后我调用 (stream-ref doubles 2)，它应该强制创建第三个元素，所以它为已经有 2 个元素的流调用 stream-map – (1 2) – 所以它应该产生 (2 4) 然后将此结果附加到流中。

为什么这个 stream-map 总是应用到 last 创建的元素？它是如何工作的？

感谢您的帮助！

Answer 1

这是一个标准技巧，可以根据其前一个元素定义惰性流。将流视为值的无限序列：

s = x0, x1, x2, ...

现在，当您 map 通过一个流时，您提供一个函数并生成一个新流，该函数应用于流的每个元素：

map(f, s) = f(x0), f(x1), f(x2), ...

但是，当流是根据其自身的映射来定义时会发生什么？好吧，如果我们有一个流 s = 1, map(f, s)，我们可以扩展该定义：

s = 1, map(f, s)
  = 1, f(x0), f(x1), f(x2), ...

现在，当我们实际去评估流的第二个元素时，f(x0)，那么 x0 显然是 1，因为我们将流的第一个元素定义为是 1。但是当我们去评估流的第三个元素f(x1)时，我们需要知道x1。幸运的是，我们刚刚评估了 x1，因为它是 f(x0)！这意味着我们可以一次“展开”序列一个元素，其中每个元素都是根据前一个元素定义的：

f(x) = x * 2

s = 1, map(f, s)
  = 1, f(x0), f(x1), f(x2), ...
  = 1, f(1),  f(x1), f(x2), ...
  = 1, 2,     f(x1), f(x2), ...
  = 1, 2,     f(2),  f(x2), ...
  = 1, 2,     4,     f(x2), ...
  = 1, 2,     4,     f(4),  ...
  = 1, 2,     4,     8,     ...

这种打结之所以有效，是因为流是延迟求值的，因此每个值都是按需从左到右计算的。因此，在需要后续元素时，前面的每个元素都已计算完毕，自引用不会造成任何问题。

在这种情况下，Racket 流是如何工作的？

How Racket streams work in this case?

stream

scheme

racket

self-reference

sicp