The Sieve of Eratosthenes, implemented lazily in Python
x = start
while 1:
yield x
x += 1
def filter_out_multiples(stream, f):
return (i for i in stream if i%f != 0)
numbers = (i for i in integers_from(2))
while numbers:
p = numbers.next()
print p
numbers = filter_out_multiples(numbers, p)
This was done after a student wondered about how to make nicer my Java version of the same. An important thing here is that these implementations are lazy — no generating a huge array of numbers and then crossing them out. Instead, they take each number in turn and run it through an ever-increasing series of filters. I feel virtually certain that this kind of thing is exactly what Haskell was made for, but can’t quite incant it due to my total lack of Haskell experience. Any help? What about in your language of choice? Do Ruby blocks make this even simpler?
This particular problem seems to be of high enough difficulty while being conceptually easy that it might be a good addition to the list of programs one uses to show how to do X in a given language.
