Computing with Infinite Sequences

As we saw in the last 2 lectures, all elements of a stream except the first one are computed only when they are needed to produce a result. This opens up the possibility to define infinite streams!

For instance, here is the stream of all integers starting from a given number:

def from(n: Int): Stream[Int] = n #:: from(n+1)

// The stream of all natural numbers
val nats = from(0)

// The stream of all multiples of 4:
val m4 = nats.map(_ * 4)

The Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient technique to calculate prime numbers.

• Start with all integers from 2, the first prime number.
• Eliminate all multiples of 2.
• The first element of the resulting list is 3, a prime number.
• Eliminate all multiples of 3.
• Iterate forever. At each step, the first number in the list is a prime number and we eliminate all its multiples.

Since this requires numbers going up to infinity, we use Streams to implement this.

Implementation:

def sieve(s: Stream[Int]): Stream[Int] = {
    s.head #:: sieve(s.tail filter (_ % s.head != 0))
}

val primes = sieve(from(2))