Solution to the Hamming Number problem. Demonstrates a lazy evaluation evaluation technique using itertools.tee() to feed an iterator into itself. This is a common technique with Haskell. The deferred_output() function is the key technique for implementing a forward reference to the output of the stream.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | ```
from itertools import tee, chain, islice, groupby
from heapq import merge
def hamming_numbers():
# Generate "5-smooth" numbers, also called "Hamming numbers"
# or "Regular numbers". See: http://en.wikipedia.org/wiki/Regular_number
# Finds solutions to 2**i * 3**j * 5**k for some integers i, j, and k.
def deferred_output():
'Works like a forward reference to the "output" global variable'
for i in output:
yield i
result, p2, p3, p5 = tee(deferred_output(), 4) # split the output streams
m2 = (2*x for x in p2) # multiples of 2
m3 = (3*x for x in p3) # multiples of 3
m5 = (5*x for x in p5) # multiples of 5
merged = merge(m2, m3, m5)
combined = chain([1], merged) # prepend starting point
output = (k for k, v in groupby(combined)) # eliminate duplicates
return result
if __name__ == '__main__':
print(list(islice(hamming_numbers(), 1000))) # Show first 1000 hamming numbers
``` |

Problem statement (see http://en.wikipedia.org/wiki/Regular_number ) : "Output in ascending sequence all numbers which have only 2, 3, and 5 as non-trivial factors. The first such number is 1; and if *x* is any such number, so are *2x*, *3x*, and *5x*. Use three generators to produce the multiples and feed them to a merge routine, then eliminate duplicates which ensures they are eventually output in ascending order."

- The output is split four ways: one returned result and three copies to feed back in.
- Each of the three copies is consumed in a generator of multiples.
- The combined result has 1 as a starting point and is followed by the merge of the multiples.
- Repeated values (runs of the same value) are eliminated.

The important part of the technique is the *deferred_output* function which lets you assume the result is known. Using those assumed values, the actual results get assigned to the *output* variable which is referred to by *deferred_output*. The *tee* itertool copies and splits-off the returned result from the buffered streams which are fed back into the multiple generators. The *chain* itertool loads the initial value to the result so that the cyclical iterator will have a starting point.

This is a general purpose technique. It is used extensively in Haskell programming language examples.

The same technique can be used for a fibonacci sequence (though there are much simpler ways to do it):

```
def fibonacci():
def deferred_output():
for i in output:
yield i
result, c1, c2 = tee(deferred_output(), 3)
paired = map(add, c1, islice(c2, 1, None))
output = chain([0, 1], paired)
return result
print(list(islice(fibonacci(), 50)))
```

I needed to change "i is not last" to "i != last" to get no_repeats() to work properly.

Could function deferred output be seen as a form of forward declaration of variable output, allowing it to be referenced before it is later assigned too?

P.S. this recipe inspired this

As written above, I get repeats in the sequence:

After making Mike's suggested change, the repeats disappear and the results tally with another generator using a different algorithm:

Very nice, Raymond.

This whole idea looks general&useful enough that may deserve some support in the language or in the itertools module, if possible.

(I'll need to work some on the D language standard library to allow similar things).

In that fibonacci() function this line:

paired = map(add, c1, islice(c2, 1, None))

Needs an imap() to work, instead of a map().

@bearophile: although not explicitely stated, this recipe seems to be using Python 3, where builtin

mapbehaves likeitertools.imapin 2.x But since that's the only place where the difference 2 vs 3 matters, a short comment in the code would be nice.