一昨日のエントリはひどいものだった。僕はこれをPythonでやりたかったんだ。

foldl(op, v, [a, b, c, d]) = (((v op a) op b) op c) op d
foldr(op, v, [a, b, c, d]) = a op (b op (c op (d op v)))

そしてこう書いた。

def foldl(proc, elem, lis):
    lis.insert(0, elem)
    return reduce(proc, lis)

def foldr(proc, elem, lis):
    lis.append(elem)
    lis.reverse()
    return reduce(lambda x, y : apply(proc, [y, x]), lis)

fl = foldl(lambda x, y : x / y, 2.0, [1.0, 2.0, 4.0, 8.0])
fr = foldr(lambda x, y : x / y, 2.0, [1.0, 2.0, 4.0, 8.0])

>>> fl
0.03125
>>> fr
0.5

こんなアホみたいなことをする必要なんて全くなかったんだ……。もう少し考えるべきだった、Pythonがこんな不便なはずはないって。

import operator
def foldl(proc, elem, l):
    lis = l[:]
    lis.insert(0, elem)
    return reduce(proc, lis)

def foldr(proc, elem, l):
    lis = l[::-1]
    lis.insert(0, elem)
    return reduce(lambda x, y : proc(y, x), lis)

fl = foldl(operator.truediv, 2, [1, 2, 4, 8])
fr = foldr(operator.truediv, 2, [1, 2, 4, 8])

>>> fl
0.03125
>>> fr
0.5

これでよかったんじゃないか……。そして忘れていた、普通の言語にはループってものがあるってことを。

def foldl_loop(proc, elem, l):
    lis = l[:]
    for x in lis:
        elem = proc(elem, x)
    return elem

def foldr_loop1(proc, elem, l):
    lis = l[::-1]
    for x in lis:
        elem = proc(x, elem)
    return elem

def foldr_loop2(proc, elem, l):
    lis = l[:]
    while lis:
        elem = proc(lis.pop(),elem)
    return elem

時間を計ってみよう。largelist = range(10000000)として、リストの整数を全て足しあわせてみる。

foldl(operator.add, 0, largelist)
3.36605238934

foldl_loop(operator.add, 0, largelist)
5.12172161546

foldr(operator.add, 0, largelist)
7.88937811929

foldr_loop1(operator.add, 0, largelist)
5.67820882263

foldr_loop2(operator.add, 0, largelist)
8.93474310282

reduceはえー。そして気づいた、こんなことしたってHaskellの勉強にはならないって。