Consリスト

Python

を読み直していて、PythonでLispのような連結リストを表現するのは (1, (2.0, ("three", None))) とあったので、これを基にして自分の「car, cdr, consと無限リスト」(http://d.hatena.ne.jp/morchin/20080924#p1)で作ったサンプルを実装しなおしてみた。ここでは、LispやHaskellのリストをConsリストと呼ぶことにする。

def car(seq):
    return seq[0]

def cdr(seq):
    return seq[-1]

def cons(x, xs):
    return [x, xs]

def list_to_cons(seq):
    ls = []
    for i in range(len(seq)):
        ls = cons(seq[~i], ls)
    return ls

def cons_to_list(seq):
    if not seq: return []
    ls = []
    while True:
        p, ps = car(seq), cdr(seq)
        ls.append(p)
        if not ps: break
        seq = ps
    return ls

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

L = list_to_cons(range(2, 11))
print L                       #=> [2, [3, [4, [5, [6, [7, [8, [9, [10, []]]]]]]]]]
print cons_to_list(L)         #=> [2, 3, 4, 5, 6, 7, 8, 9, 10]
print cons_to_list(sieve(L))  #=> [2, 3, 5, 7]

ConsリストがPythonの通常のリストのように扱えればlist_to_cons関数とcons_to_list関数は不要になるのだが、リストのデータ構造を変更しているのでしょうがない。


sieve関数の実装を比較してみると当たり前であるが全く同じである。cdr関数とcons関数の実装を比較してみるとPythonリストよりConsリストの方が効率が良い。しかしlist_to_cons関数やcons_to_list関数が入る分遅くなるのでどちらが早いかは計測していないので不明。この意味で、Pythonで通常のリストの他にConsリストを入れてくれれば、こういう使い方をした際にパフォーマンスアップする。クラスで作れないかなと思ったけど、インスタンスが値として評価された処理をフックする特殊メソッドがないのでできなかった。Pythonには演算子オーバーロードくらいで他にマクロ機能のような機能が弱い。私はメタクラスもあまり使い道を理解していない。


まとめると、リストを再帰呼び出しで扱う場合はConsリストの方が効率が良くなると思うが、Pythonでは再帰処理よりもforループ処理を積極的に使う。再帰処理が有用な場合としては再帰的なデータ構造を扱う場合などだと思う。


Haskellでも独自のスタックを実装していない言語では末尾再帰以外の再帰はスタックオーバーフローする。car、cdr、cons程度のパターンマッチは見やすさ程度のメリットしかない(でもよく使う機能の見易さは重要!Javaを考えてみると分かる)。Consリストを使用することによりHaskellがPythonよりも有利な点は、遅延評価と末尾再帰の最適化と再代入不可能とカリー化の機能との組み合わせであると思う。Pythonでもイテレータで遅延評価できるが制限がある。


Pythonでも遅延評価、末尾再帰の最適化、カリー化の機能をもっと積極的に使いやすくして取り入れればHaskellのメリットがだんだんなくなってくると思う。ただしパフォーマンスで勝負することはもちろんできないので、それは勝負しなくてOK。


今回Python 2.6や3.0でクラス周りやイテレータ周りでだいぶ手を入れたということなので将来的には期待できるかなあ。特に無限リストと有限リストを抽象化して同じレベルで扱えるようにしてほしい。


Groovyの作者の恐らくPythonに魅力を感じていないのでRubyをベースにしてしまったが、私は魅力を感じているのでPython + HaskellなJVMスクリプト言語誰か作ってくれないかなあ。もちろんScalaはやりすぎ。そこまでの複雑さいらない。というかRubyの方がこういった機能を取り入れる可能性あるかな？私から見るとRubyは必要以上に複雑。確かに高機能だけど私にはPythonくらいで十分。ただしもう少し無限リストの扱いを簡単にしてほしい。なぜitertoolsをimportしないといけないと扱えないのかが不明。よく使うのに。