example: dynamic creation of streams
This example shows how streams can be created dynamically, and illustrates the use of _no_value and state. The example is the sieve of Eratosthenes.
In the following, primes is a list and in_streams is a stream, and we will design a function sieve(x, primes) such that if x is the sequence [2, 3, …, n], and primes is initially the empty stream, then the function terminates with primes containing the list of prime numbers up to n.
def sieve(in_stream, primes): out_stream = Stream() @map_e def filter_multiples(v, state, primes): if state == 0: primes.append(v) return _no_value, (v, True) else: my_prime, last = state if v % my_prime == 0: return _no_value, state elif last: sieve(out_stream, primes) return v, (my_prime, False) else: return v, state filter_multiples(in_stream, out_stream, state=0, primes=primes)
The state of the function f is either 0 or a pair (my_prime, last). The state is 0 before the function is called for the first time. After the function is called at least once, my_prime becomes the first value received by the function on its input stream. last is a Boolean where last is initially True and last becomes False when this function has emitted at least one value on its output stream.
The function filter_multiples always returns two values: the next element of the output stream and the next state. When the next element of the output stream is _no_value then the output stream is not extended.
Skip the remainder of the section if the code is self evident.
Let’s look at the very first call to filter_multiples. The value that arrives on the input stream is 2. At this point state is 0 and primes is the empty stream. So 2 gets appended to primes and the function returns a new state: ((my_prime, last) = (_no_value, True), and so the output stream is not extended, and the state records that this execution of filter_multiples is the last one (since last = True) to have been called.
The next value that arrives on the input stream is 3. Since state is not 0, my_prime, last are extracted from the state to yield my_prime =2 and last = True. Since 3 is not a multiple of 2, and since last is True, a new sieve is called. The parameters passed to the new call of sieve are the out_stream of this filter_multiples and the stream primes which now has a single element: 2. Next filter_multiples returns v, (my_prime, False), i.e., the next element v = 3 of its output stream and the next state (2, False) which identifies my_prime as 2, and last as False.
The next value that arrives on the input stream is 4. Since state is not 0, my_prime, last are extracted from the state to yield my_prime =2 and last = False. Since 4 is a multiple of 2, the function returns (_no_value, state) = (_no_value, (2, False)). So, the output stream is not extended and my_prime and last remain unchanged.