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.
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