Ich spiele mit den Funktionsfähigkeiten von Python 3 und habe versucht, einen klassischen Algorithmus zur Berechnung von Hamming-Zahlen zu implementieren. Das sind die Zahlen, die als Primfaktoren nur 2, 3 oder 5 haben. Erste Hamming-Zahlen sind 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 18, 20 und so weiter.

Meine Implementierung ist die folgende:

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)

Das Problem, das Zusammenführen scheint, funktioniert einfach nicht. Davor habe ich Sieve of Eratosthenes auf die gleiche Weise implementiert, und es hat einwandfrei funktioniert:

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)

Dieser verwendet die gleichen Techniken wie meine Zusammenführungsoperation. Also kann ich keinen Unterschied sehen. Hast du eine Idee?

(Ich weiß, dass all dies auf andere Weise implementiert werden kann, aber mein Ziel ist es, Generatoren und reine Funktionsfähigkeiten, einschließlich der Rekursion, von Python genau zu verstehen, ohne Klassendeklarationen oder spezielle vorgefertigte Python-Funktionen zu verwenden.)

UPD: Für Will Ness ist hier meine Implementierung dieser Algorithmen in LISP (Racket tatsächlich):

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