Слияние ленивых потоков (с помощью генераторов) в Python
Я играю с функциональными возможностями Python 3, и я пытался реализовать классический алгоритм для вычисления чисел Хэмминга. Это числа, которые имеют в качестве простых множителей только 2, 3 или 5. Первые числа Хэмминга: 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 18, 20 и так далее.
Моя реализация заключается в следующем:
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)
Проблема в том, что слияние кажется просто не работает. До этого я реализовал Sieve of Eratosthenes таким же образом, и он работал совершенно нормально:
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)
Этот использует те же методы, что и моя операция слияния. Так что я не вижу никакой разницы. У тебя есть идеи?
(Я знаю, что все это может быть реализовано другими способами, но моя цель - точно понять генераторы и чисто функциональные возможности, в том числе рекурсию, Python, без использования объявлений классов или специальных предварительно созданных функций Python.)
UPD: Уилл Несс, вот моя реализация этих алгоритмов в LISP (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)))))