car, cdr, consと無限リスト

昨日のHaskellの資料のエラトステネスのふるいを元に無限リストの扱いを考えてみた。

Pythonのcar、cdr、consは、jijixiさんのコードを拝借(http://jijixi.azito.com/cgi-bin/diary/index.rb?date=20070101#p01)。

-- Haskell
sieve [] = []
sieve (p:ps) =
    p : sieve [n|n <- ps, n `mod` p /= 0]

main = print $ sieve [2..10]

# Python
def sieve(ls):
    if not ls: return []
    p, ps = car(ls), cdr(ls)
    return cons(p, sieve([n for n in ps if n % p != 0]))
	
def car(lst):
    return lst[0]

def cdr(lst):
    return lst[1:len(lst)]

def cons(x, xs):
    t = type(xs)
    tmp = (x,) + tuple(xs)
    return t(tmp)

print sieve(range(2,11))

car、cdr、consは単なる構文なのでPythonの書き方が面倒なのはしょうがないとして、問題は上記のPythonのコードでrangeをxrangeに(リストをイテレータに)置き換えるとスライシングが使用できずに動かないということである。もちろんHaskellではうまくいく。これは、Pythonでは無限リストをイテレータとして扱っているのに対し、Haskellでは再帰的な構造のリストで表現しているからである。

再帰的な構造であるリストであれば、有限でも無限でもリストを作りだす部分の実装はたいして変わらないと思うので簡単に無限にまで拡張できると思われる。ただし評価に関しては注意が必要で、再帰的な処理で無限リストを扱う場合、すべて取り出すように評価すると無限ループになる。しかし、有限な部分のみを取り出せば、その部分までの評価しかしない。つまり遅延評価が必要となる。これはどうなのだろう？遅延評価というより単なるイテレータに似たクラスを作ればPythonでも表現できそうな気がする。つまり、再帰構造リストクラスの評価の部分のみ遅延評価すれば良い。無限リストでスライシングとイテレータが組み合わせてできれば良い？もちろんリストを作りだすタイミングでも無限に要素を作り出そうとしてはダメなのも言うまでもない。

Haskellの

Prelude> let p:ps = [1..5]
Prelude> p
1
Prelude> ps
[2,3,4,5]
Prelude> p:ps
[1,2,3,4,5]

にあたる処理はパターンマッチというほど大げさな仕組みは不要だと思うが、どうせならPythonの言語自体に「再帰構造リストクラス」、「(有限/無限)範囲リテラル」、「car, cdr, consのみのパターンマッチ」の3つの機能を入れてみてはどうだろうか？これでHaskellみたいなことができるのでは？