Gram z możliwościami funkcjonalnymi Pythona 3 i próbowałem zaimplementować klasyczny algorytm do obliczania liczb Hamminga. Są to liczby, które jako czynniki pierwsze mają tylko 2, 3 lub 5. Liczby pierwszego Hamminga to 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 18, 20 i tak dalej.

Moja realizacja jest następująca:

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)

Problem, że łączenie się wydaje, po prostu nie działa. Wcześniej zaimplementowałem Sito Eratostenesa w ten sam sposób i działało to doskonale:

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)

Ten używa tych samych technik, co moja operacja łączenia. Więc nie widzę żadnej różnicy. Czy masz jakies pomysły?

(Wiem, że wszystkie te mogą być wdrożone w inny sposób, ale moim celem jest dokładnie zrozumienie generatorów i czystych możliwości funkcjonalnych, w tym rekurencji Pythona, bez używania deklaracji klas lub specjalnych wbudowanych funkcji Pythona).

UPD: Dla Will Ness przedstawię moje implementacje tych algorytmów w LISP (właściwie Racket):

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