## Infinite streams and prime numbers

01 May 2016

I was playing with Streams after reading the strictness chapter in Functional Programming in Scala and thought I’d share my ramblings. Streams and Lists are similar data structures, except Streams compute their elements lazily. Because not all elements are computed during construction it is possible to implement infinitely long Streams.

## Fibonacci Sequence

Generating the Fibbonacci sequence is a simple example from the Streams scaladoc page

The `#::` operator will compute the right side lazily. We can use the Stream the same as a List, for example, taking the first 10 elements of the sequence

## The unfold function

The `fibFrom` method takes the current state of the sequence as inputs, calculates the next element, and recurses with the next state. We can generalize these steps with a function called `unfold`, which takes an initial state and a function to produce the next element and state.

This implementation allows the Stream to terminate when the function returns `None`

## Algorithm for finding primes

The Sieve of Eratosthenes is an old and simple algorithm for finding prime numbers. From wikipedia, “It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2”

Using this idea we can generate an infinite stream of prime numbers. We can implement the algorithm using `unfold` in the following steps:

1. The starting state is the number 2 and an empty set of prime checking functions
2. Sequentially check each number for primeness until a prime is found
3. Convert the prime to a check function and add it to the prime checking functions
4. Return the prime number and the new set of prime checking functions

## An infinite stream of prime numbers

The algorithm implemented with `unfold`

We can use the Stream like so: