Estoy jugando con las capacidades funcionales de Python 3 y traté de implementar el algoritmo clásico para calcular los números de Hamming. Esos son los números que tienen como factores primos solo 2, 3 o 5. Los primeros números de Hamming son 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 18, 20 y así sucesivamente.

Mi implementación es la siguiente:

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)

El problema que parece que la fusión simplemente no funciona. Antes de eso implementé el Tamiz de Eratóstenes de la misma manera, y funcionó perfectamente bien:

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)

Esta utiliza las mismas técnicas que mi operación de combinación. Así que no puedo ver ninguna diferencia. ¿Tienes alguna idea?

(Sé que todo esto se puede implementar de otras maneras, pero mi objetivo es entender exactamente los generadores y las capacidades funcionales puras, incluida la recursión, de Python, sin utilizar declaraciones de clase ni funciones especiales de Python precreadas).

UPD: Para Will Ness, aquí está mi implementación de estos algoritmos en LISP (Racket en realidad):

(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)))))