Streams

Collections and Combinatorial Search

We have seen collections and combinatorial search previously.

Consider the example of finding the second prime number in a given range.

Instead of writing recursive functions, We can do that simply by:

((1000 to 10000).filter(isPrime))(1)

But this has drawbacks:

• It constructs all prime numbers between 1000 and 10000 in a list, but only ever looks at the first two elements of that list.
• We can reduce the upper bound, and that would speed things up, but we might miss the second prime number all together.

Solution: Delayed Evaluation

Avoid computing the tail of a sequence until it is needed for the evaluation result (which might be never) This idea is implemented in a new class, the Stream. Streams are similar to lists, but their tail is evaluated only on demand.

Streams

• Streams can be defined from a constant Stream.empty and a constructor Stream.cons.

val xs = Stream.cons(1, Stream.cons(2, Stream.empty)) // Output: Stream.Cons[Int] = Stream(1, ?) // Note that the tail is not evaluated

• They can also be defined like the other collections by using the object Stream as a factory.

Stream(1, 2, 3)       // Output: Stream[Int] = Stream(1, ?) // Note that the tail is not evaluated

• The toStream method on a collection will turn the collection into a stream:

(1 to 1000).toStream  // Output: Stream[Int] = Stream(1, ?) // Note that the tail is not evaluated

As seen above, at any given time only 1 element of the stream is generated. The rest is generated "on demand". If the 2nd element is required, only that will be generated and the 3rd element will be a ?. And so on. This is unlike the case of List where all the elements are generated at once.

The second parameter i.e. the tail in the stream construction is a by name parameter, as opposed to the tail in the list which is by value.

Printing a stream shows only the first element. So to see the whole stream, you have to print it as a list (while debugging, etc)

Stream methods

Stream supports "almost" all methods of List.

The one major exception is ::, so x :: xs always produces a list, never a stream. There is however an alternative operator #:: which produces a stream. Thus we can use x #:: xs which is equivalent to Stream.cons(x, xs).

#:: can be used in expressions as well as patterns.

Problem Solved

Coming back to the original problem, we can resolve it by using streams:

((1000 to 10000).toStream.filter(isPrime))(1)

This only evaluates till the the required element, i.e. index 1 i.e. the second element and then stops.