526互联

Streams

发布时间 2024-01-03 20:05:31作者: viewoverlook

Streams

Sequence Operations

Map, filter, and reduce express sequence manipulation using compact expressions

Example: Sum all primes in an interval from a(inclusive) to b(exclusive)

def sum_primes(a, b):
	total = 0
	x = a
	while x < b:
		if is_prime(x):
			total += x
		x+=1
	return total

def sum_primes(a, b):
	return sum(filter(is_prime, range(a,b)))

Streams allow scheme to process sequences while using an efficient amount of space just like a Python iterator.
But unlike iterators which are mutable values, Steams are immutable.

stream can be infinite.
I can define a new procedure that takes a stream and returns another stream just by inspecting and manipulating some elements from the front of the input stream and then using con stream to build something new.

A stream is an example of a lazy sequence. Specifically, it is a lazily evaluated Scheme list. In other words, the stream's elements (except for the first element) are only evaluated when the values are needed. In addition, streams are memoized: the elements that have already been computed are saved!
流是惰性序列的一个示例。具体来说，它是一个延迟计算的Scheme列表。换句话说，流的元素（第一个元素除外）仅在需要值时才计算。此外，流会被记忆：已经计算过的元素会被保存！

Because a stream is simply a lazy list, the rest of a stream is also a stream (just like the rest of a list is also a list). In addition, nil can also serve as an empty stream. To check if a stream is empty, we can use the built-in procedure null?.
因为流只是一个惰性列表，所以流的其余部分也是一个流（就像列表的其余部分也是一个列表一样）。另外 nil 也可以作为空流。要检查流是否为空，我们可以使用内置过程 null? 。

The procedures involved for working with streams are as follows:
使用流所涉及的过程如下：

  • (cons-stream first rest): A special form that constructs a stream by evaluating the first operand first and storing its value as the first element in the stream, and storing the second operand rest, unevaluated, to be evaluated later.
    (cons-stream first rest) ：一种特殊形式，通过计算第一个操作数 first 并将其值存储为流中的第一个元素，并存储第二个操作数 rest （未计算，以便稍后计算）来构造流。
  • (car s): A procedure that works on streams the same way it does on lists. It returns the first element of the stream, which had already been computed on construction of the stream.
    (car s) ：处理流的过程与处理列表的方式相同。它返回流的第一个元素，该元素已经在流的构造中计算出来。
  • (cdr-stream s): A procedure that returns the rest of the stream by evaluating the rest expression that was stored on construction of the stream. It then stores the value of this expression so that on subsequent calls to cdr-stream on this stream, rest no longer has to be evaluated.
    (cdr-stream s) ：通过评估在构建流时存储的 rest 表达式来返回流的其余部分的过程。然后，它存储该表达式的值，以便后续调用该流上的 cdr-stream 时，不再需要计算 rest 。

Now we are ready to look at a simple example. This stream is an infinite stream where each element is 1.
现在我们准备看一个简单的例子。该流是一个无限流，其中每个元素都是 1。

scm> (define ones (cons-stream 1 ones))
ones
scm> (car ones)
1
scm> (cdr-stream ones)
(1 . #[promise (forced)])

The reason we are able to recursively reference this object without causing an error is because the second operand to cons-stream is not evaluated. Instead, it is stored until cdr-stream is called, at which point the expression will be evaluated and the resulting value will be stored.
我们能够递归引用该对象而不导致错误的原因是因为 cons-stream 的第二个操作数没有被求值。相反，它会被存储直到调用 cdr-stream ，此时将计算表达式并存储结果值。

Next, here's one way to build a stream of the natural numbers starting at n.
接下来，这是构建从 n 开始的自然数流的一种方法。

scm> (define (naturals (n)) 
	   (cons-stream n (naturals (+ n 1)))) 
naturals 
scm> (define nat (naturals 0)) 
nat 
scm> (car nat) 
0 
scm> (car (cdr-stream nat)) 
1 
scm> (car (cdr-stream (cdr-stream nat))) 
2

Here, the expression that is stored is a recursive call to naturals. When we evaluate this call, we get another stream whose first element is one greater than the previous number in the sequence. The second element of this stream is uncomputed until cdr-stream is called on it, which will activate yet another call to naturals. Hence, we effectively get an infinite stream of integers, where each integer is computed one at a time. This is almost like infinite recursion, but one which can be viewed one step at a time, so it does not crash.
这里，存储的表达式是对 naturals 的递归调用。当我们评估这个调用时，我们得到另一个流，其第一个元素比序列中的前一个数字大一个。该流的第二个元素在调用 cdr-stream 之前不会被计算，这将激活对 naturals 的另一个调用。因此，我们有效地获得了无限的整数流，其中每个整数一次计算一个。这几乎就像无限递归，但可以一次查看一步，因此不会崩溃。