西尾泰和のブログ @ Cybozu Labs

Pythonで実装してみました。

404 Blog Not Found:Code Snippets - reduce(l|r)を実装汁!

解答は下のようになります。

>>> reducel = reduce
>>> reducer = lambda f, xs: reduce(lambda y, x: f(x, y), reversed(xs))

動作を確認してみましょう。

>>> concat = lambda x, y: "(%s#%s)" % (x, y)
>>> reducer(concat, range(1, 5))
'(1#(2#(3#4)))'
>>> reducel(concat, range(1, 5))
'(((1#2)#3)#4)'

解説は後で書きます。

= ちなみにHaskellでは、まともに書くと下のようになってとても悲しいです。

reducer = foldr1
reducel = foldl1 

そこであえてfoldを封じてみると下のようになります。

reducer::(String->String->String)->[String]->String
reducer f [x] = x
reducer f (x:xs) = f x $ reducer f xs

reducel::(String->String->String)->[String]->String
reducel f [x, y] = f x y
reducel f (x:y:xs) = reducel f $ f x y :xs 

= PythonのreduceはHaskellのfoldlに相当するのですが foldrに相当する組み込みの関数はありません。 そこで、リストをreversedを使ってひっくり返し、 関数の引数の順番もひっくり返してreduceを使っています。

reducer = lambda f, xs: reduce(lambda y, x: f(x, y), reversed(xs))

ここで重要なのはxs.reverse()ではなく reversed(xs)を使うというところです。 reversed(xs)はxs.reverse()を関数型言語っぽく書くための飾りだというとらえ方を されている人もいるようですが、違います。 実際に10万件のリストをひっくり返すのにかかる時間を計ってみると reversed(xs)の方が100倍近く速い、という桁違いの差が出ていることがわかります。 (statとTimerに関しては西尾泰和のブログ @ Cybozu Labs: Python2.4以降での高速なソートを参照)

>>> stat(Timer("xs.reverse()", "xs = range(100000)").repeat(100, 100))
(0.039828419533763509, 0.0018198081738915054)
>>> stat(Timer("reversed(xs)", "xs = range(100000)").repeat(100, 100))
(0.00038362976300049923, 0.00013374982828255732)

なぜでしょうか？これはreversed(xs)が何を返しているのか見てみるとわかります。

>>> reversed(range(100))
<listreverseiterator object at 0x00DC46F0>

xs.reverse()はそこで実際にリストの中身を書き換えてしまうのに対し、 reversed(xs)は単に「リストに逆順でアクセスするイテレータ」を作っているわけです。