[edit]
# Infinite Streams

## Introduction

## Stream Procedures

## Note on

## Takeaways

We have seen how to support the illusion of manipulating a stream as a complete sequence, when in actuality we only compute as much of the stream as we need. We can exploit this technique to represent sequences efficiently as streams, even if the sequences are very long. But more importantly, we can use streams to represent sequences that are infinitely long. For instance, suppose we define the following:

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

Then `integers`

represents the stream of all positive integers.
More specifically, the `stream-car`

of `integers`

is 1
and the `stream-cdr`

of `integers`

is a promise equivalent to
`(integers-starting-from 2)`

.

Using `integers`

, we can define other infinite streams, such as the stream of
integers that are not divisible by 7:

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

We can then find integers not divisible by 7 simply by accessing elements of this stream:

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

The way we've been defining streams up until now is very similar to the way we define lists. Now we're going to take a more "streamy" approach.

We can take advantage of delayed evaluation to implicitly define streams. For example, we can define an infinite stream of all ones like this:

```
(define ones (cons-stream 1 ones))
```

This works much like the definition of a recursive procedure: `ones`

is a pair
whose `car`

is `1`

and whose `cdr`

is a promise to evaluate `ones`

. Evaluating
the `cdr`

gives us again a `1`

and a promise to evaluate `ones`

, and so on.

We can also define a stream procedure `add-streams`

, which produces the
elementwise sum of two streams:

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

For example, `(add-streams ones ones)`

would produce a stream of all twos.

We can redefine then define `integers`

implicitly:

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

This defines `integers`

to be a stream whose `stream-car`

is 1 and
whose `stream-cdr`

is the sum of `ones`

and `integers`

.
Thus, the second element of `integers`

is
1 plus the first element of `integers`

, or 2; the third element of integers is 1
plus the second element of integers, or 3; and so on. This definition works
because, at any point, enough of the integers stream has been generated so
that we can feed it back into the definition to produce the next integer.

`stream-map`

Note that in the example above, we called `stream-map`

with two streams.
Previously, we used stream-map with just one stream:

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

You can use `stream-map`

with any number of streams, given that the procedure
you give has the corresponding number of arguments:

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

Naturally, the actual definition of `stream-map`

is slightly different, but don't
worry about it for now.

We can also define the Fibonacci sequence in the same style:

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

This definition says that `fibs`

is a stream beginning with 0 and 1, such that
the rest of the stream can be generated by adding `fibs`

to itself shifted by
one place.

Another stream operation that we can use is `scale-stream`

. It takes in two
arguments—a stream of integers and an integer—and multiplies all elements in
the stream by the integer:

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

We can now define a stream of all the powers of 2 like so:

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

We can define the infinite stream of primes in a different, implicit way now:

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

This might seem fairly straightforward—we start with the first prime, 2, and
we then `cons-stream`

the rest of the integers that are prime to it. However,
the way that `prime?`

is defined makes this problem a little more subtle.

We check if a number is prime by seeing whether it is divisible by any prime (not just any integer!) less than √(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))
```

This is a recursive definition (much like you saw in trees!) since `primes`

is
defined in terms of the `prime?`

predicate, which itself uses the `primes`

stream. The reason this procedure works is that, at any point, enough of the
`primes`

stream has been generated to test the primality of the numbers we
need to check next. That is, for every `n`

we test for primality, either `n`

is not prime (in which case there is a prime already generated that divides
it) or `n`

is prime (in which case there is a prime already generated -- i.e.,
a prime less than `n`

-- that is greater than √(`n`

))

In this section, you learned:

- What infinite streams are!
- Some cool stuff we can make with them