Estou jogando com capacidades funcionais do Python 3 e tentei implementar o algoritmo clássico para calcular números de Hamming. Esses são os números que têm como fatores primos apenas 2, 3 ou 5. Os números do primeiro Hamming são 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 18, 20 e assim por diante.

Minha implementação é a seguinte:

def scale(s, m):
    return (x*m for x in s)

def merge(s1, s2):
    it1, it2 = iter(s1), iter(s2)
    x1, x2 = next(it1), next(it2)
    if x1 < x2:
        x = x1
        it = iter(merge(it1, s2))
    elif x1 > x2:
        x = x2
        it = iter(merge(s1, it2))
    else:
        x = x1
        it = iter(merge(it1, it2))
    yield x
    while True: yield next(it)

def integers():
    n = 0
    while True:
        n += 1
        yield n

m2 = scale(integers(), 2)
m3 = scale(integers(), 3)
m5 = scale(integers(), 5)

m23 = merge(m2, m3)

hamming_numbers = merge(m23, m5)

O problema que mescla parece simplesmente não funciona. Antes disso eu implementei o Sieve of Eratosthenes da mesma maneira, e funcionou perfeitamente bem:

def sieve(s):
    it = iter(s)
    x = next(it)
    yield x
    it = iter(sieve(filter(lambda y: x % y, it)))
    while True: yield next(it)

Este usa as mesmas técnicas que a minha operação de mesclagem. Então não vejo diferença. Você tem alguma ideia?

(Eu sei que tudo isso pode ser implementado de outras formas, mas meu objetivo é exatamente entender geradores e capacidades funcionais puras, incluindo recursão, do Python, sem usar declarações de classe ou funções Python especiais pré-construídas.)

UPD: Para o Will Ness, aqui está minha implementação deste algoritmo no LISP (Racket na verdade):

(define (scale str m)
  (stream-map (lambda (x) (* x m)) str))

(define (integers-from n)
  (stream-cons n
               (integers-from (+ n 1))))

(define (merge s1 s2)
  (let ((x1 (stream-first s1))
        (x2 (stream-first s2)))
    (cond ((< x1 x2)
           (stream-cons x1 (merge (stream-rest s1) s2)))
          ((> x1 x2)
           (stream-cons x2 (merge s1 (stream-rest s2))))
          (else
           (stream-cons x1 (merge (stream-rest s1) (stream-rest s2)))))))


(define integers (integers-from 1))

(define hamming-numbers
  (stream-cons 1 (merge (scale hamming-numbers 2)
                        (merge (scale hamming-numbers 3)
                               (scale hamming-numbers 5)))))