example: dynamic creation of streams
This example illustrates three features: how streams can be created dynamically, how the state can be used, and the use of _no_value. 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 f(v, state, primes): my_prime, last = state output = _no_value if my_prime == 0: my_prime = v primes.append(v) else: if v % my_prime != 0: output = v if last: last = False sieve(out_stream, primes) return output, (my_prime, last) f(in_stream, out_stream, state=(0, True), primes=primes)
The state of the function f is initially 0 and later becomes the 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 after sieve calls itself. The diagram below shows the sequence of sieves generated by the program.
The function f 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 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. The incoming value, 2, gets appended to primes and the function returns a new state: (my_prime, last) = (_no_value, True). Since the output element is _no_value the output stream is not extended. The state records that this execution of f has not yet called sieve because last = True.
The next value that arrives on the input stream is 3. Because state is not 0, my_prime, last are extracted from the state to yield my_prime =2 and last = True. Because 3 is not a multiple of 2, and last is True, a new sieve is called. The parameters passed to the new call of sieve are the out_stream of this f and the stream primes which now has a single element: 2. Next f 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. last is False because f has called sieve.
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.