[fork] Sieve

sieve1.py

"""Translated from Haskell:
let sieve(p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs) in sieve [2..]
"""

from itertools import ifilter

def ints(k):
    while True:
        yield k
        k+=1

def sieve(g):
    p = g.next()
    yield p
    g = sieve(ifilter(lambda x: x % p != 0, g))
    while True:
        yield next(g)

primes = sieve(ints(2))
# busts stack if +1
for i in xrange(996):
    print next(primes)

sieve2.py

"""Translated from Haskell:
let sieve(p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs) in sieve [2..]
"""

from itertools import ifilter

def ints(k):
    while True:
        yield k
        k+=1

# needed due to scoping issues
def make_filter_pred(p):
    return lambda x: x % p != 0

def sieve(g):
    while True:
        p = g.next()
        yield p
        g = ifilter(make_filter_pred(p), g)

primes = sieve(ints(2))
for i in xrange(10000):
    print next(primes)

sieve3.py

"""Translated from Haskell:
let sieve(p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs) in sieve [2..]
"""

from itertools import ifilter, chain

def ints(k):
    while True:
        yield k
        k+=1

class sieve(object):
    def __init__(self, g):
        self.g = g

    def __iter__(self):
        p = self.g.next()
        return chain([p], sieve(ifilter(lambda x: x % p != 0, self.g)))

primes = iter(sieve(ints(2)))
for i in xrange(10000):
    print next(primes)

1. You're still awake.

2. This is awesome shit. ;-)

Also like how you managed to remove tail and head.

Yup, there's no need for head() and tail(), because we already have next(g) or g.next() for the former, and after running the former we've "advanced" the generator so that's tail().