Classical FP problem in python : Hamming problem

[Michael Spencer]

Francis Girard wrote:
> The following implementation is even more speaking as it makes self-evident 
> and almost mechanical how to translate algorithms that run after their tail 
> from recursion to "tee" usage :
> 

Thanks, Francis and Jeff for raising a fascinating topic.  I've enjoyed trying 
to get my head around both the algorithm and your non-recursive implementation.

Here's a version of your implementation that uses a helper class to make the 
algorithm itself prettier.

from itertools import tee, imap

def hamming():
     def _hamming():
         yield 1
         for n in imerge(2 * hamming, imerge(3 * hamming, 5 * hamming)):
             yield n

     hamming = Tee(_hamming())
     return iter(hamming)


class Tee(object):
     """Provides an indepent iterator (using tee) on every iteration request
         Also implements lazy iterator arithmetic"""
     def __init__(self, iterator):
         self.iter = tee(iterator,1)[0]
     def __iter__(self):
         return self.iter.__copy__()
     def __mul__(self, number):
         return imap(lambda x: x * number,self.__iter__())

def imerge(xs, ys):
   x = xs.next()
   y = ys.next()
   while True:
     if x == y:
       yield x
       x = xs.next()
       y = ys.next()
     elif x < y:
       yield x
       x = xs.next()
     else: # if y < x:
       yield y
       y = ys.next()

 >>> hg = hamming()
 >>> for i in range(10000):
...     n = hg.next()
...     if i % 1000 == 0: print i, n
...
0 1
1000 51840000
2000 8100000000
3000 279936000000
4000 4707158941350
5000 50960793600000
6000 409600000000000
7000 2638827906662400
8000 14332723200000000
9000 68024448000000000


Regards

Michael