Classical FP problem in python : Hamming problem

[Nick Craig-Wood]

Francis Girard <francis.girard at free.fr> 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 :
> 
>  *** BEGIN SNAP
>  from itertools import tee, imap
>  import sys
> 
>  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:
>        yield y
>        y = ys.next()

Thinking about this some more leads me to believe a general purpose
imerge taking any number of arguments will look neater, eg

def imerge(*generators):
    values = [ g.next() for g in generators ]
    while True:
        x = min(values)
        yield x
        for i in range(len(values)):
            if values[i] == x:
                values[i] = generators[i].next()

>  def hamming():
>    def _hamming():
>      yield 1
>      hamming2 = hammingGenerators[0]
>      hamming3 = hammingGenerators[1]
>      hamming5 = hammingGenerators[2]
>      for n in imerge(imap(lambda h: 2*h, iter(hamming2)),
>                      imerge(imap(lambda h: 3*h, iter(hamming3)),
>                             imap(lambda h: 5*h, iter(hamming5)))):
>        yield n
>    hammingGenerators = tee(_hamming(), 4)
>    return hammingGenerators[3]

This means that this can be further simplified thus,

def hamming():
    def _hamming():
        yield 1
        for n in imerge( imap(lambda h: 2*h, hamming2),
                         imap(lambda h: 3*h, hamming3),
                         imap(lambda h: 5*h, hamming5) ):
            yield n
    hamming2, hamming3, hamming5, result = tee(_hamming(), 4)
    return result

(Note the iter(...) seemed not to be doing anything useful so I
removed them)

-- 
Nick Craig-Wood <nick at craig-wood.com> -- http://www.craig-wood.com/nick