[メモ]数学の記述ではやはりHaskellがPythonよりも上手ですが、変態的Pythonなら肉薄できそう

エラストテネスのふるいという素数生成アルゴリズムがあるが、これを（平方と素数の間に成り立つ不等式を考慮せずシンプルに）Haskellで書くと３行で書ける。

removenum x xs = filter (\a -> a `mod` x /= 0) xs
hurui (x: xs) = x : (hurui $ removenum x xs)

main = do  print $ take 100 $ hurui [2..]

これを標準的な作法に従ったPythonで書くと少し行数が増える。（けっこうがんばったのですが。。。）

from itertools import ifilter, count, islice

def hurui(xs):
    first = xs.next()
    yield first
    for x in hurui(ifilter(lambda x: x % first != 0, xs)):
        yield x

for i in islice(hurui(count(2)), 100):
    print i, 

しかも、10000個ぐらい素数を出力させようとすると再帰呼び出しのスタックがあふれてしまう。
Haskellの場合は10000個でも大丈夫だし、きっといくつでも大丈夫なんだろう。（だからこそ関数型なんだろうし）

Pythonで無理矢理遅延評価を実現すれば、以下のようにも書けて、再帰であるのにスタックあふれもなくなる。

from itertools import ifilter, count, islice, takewhile, tee, dropwhile

def hurui(xs):
    first = xs.next()
    return (first, lambda : hurui(ifilter(lambda x: x % first != 0, xs)))

first, func = hurui(count(2))
for i in range(10000):
    print first,
    first, func = func()
 

こういうテクニックって、一般にはなんて言うんだろう。末尾再帰？


追記
コメントで頂いたのだが、以下のサイトによりエレガントな方法が。
http://4topcoder.blogspot.com/2007/07/python-generator.html
なるほどすごい。