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:

The starting state is the number 2 and an empty set of prime checking functions

Sequentially check each number for primeness until a prime is found

Convert the prime to a check function and add it to the prime checking functions

Return the prime number and the new set of prime checking functions