言語ゲーム

とあるエンジニアが嘘ばかり書く日記

Twitter: @propella
トップ > foldr と foldl の違い

foldr と foldl の違い

こないだの属性文法の記事では沢山 foldr が出てきます。foldr や foldl は関数型言語におけるループ構文です。私のようなにわか関数信者は嬉しがってつい再帰を使ってしまいますが、再帰のようなパターンを良しとしない本物の Haskell プログラマは fold を使います(多分)。ただ、foldr や foldl というネーミングは、文章が左から右へ流れると信じて疑わない欧米帝国主義の醜悪な悪習と言わないまでも、再帰についての重要な違いを軽視しているような印象を受けます。これらの関数は、本当は全然対称じゃないのです。というわけで調べてみます。

さて、足し算はどっちに結合しても良いので、1 + 2 + 3 + 4は次のように書けます。

foldr (+) 4 [1, 2, 3] -- 1 + (2 + (3 + 4)) == 10
foldl (+) 1 [2, 3, 4] -- ((1 + 2) + 3) + 4 == 10

しかし引き算は順序によって答えが違うので、両者の結果は異なります。

foldr (-) 4 [1, 2, 3] -- 1 - (2 - (3 - 4)) == -2
foldl (-) 1 [2, 3, 4] -- ((1 - 2) - 3) - 4 == -8

算数の世界では、右か左かは単なる美的問題ですが、プログラムの世界では特に右が重要です。なぜなら、fold の最後の引数であり、一番重要なデータ構造であるリストが右結合という決まりになっているからです。例えば [1, 2, 3] というリストは、1 : (2 : (3 : [])) の略です。このリストの要素を全部 fold を使って二倍する関数を書いてみます。

doubleR seq = foldr (\x xs -> x * 2 : xs) [] seq
-- doubleR [1, 2, 3] ==> [2, 4, 6]
doubleL seq = foldl (\xs x -> xs ++ [x * 2]) [] seq
-- doubleL [1, 2, 3] ==> [2, 4, 6]

一見どっちでも良さそうですが、効率が全然違うし無限リストを使うと結果も違ってきます。

Main> take 5 (doubleR [1..])
[2,4,6,8,10]
Main> take 5 (doubleL [1..])
... シーン ...

じゃあ foldl の特徴は何かと言うと、foldl は末尾再帰を意味します。Prelude.hs の foldl の定義を見ると、もろ最後に自分を呼んでいます。と言うわけで、嬉しがって末尾再帰を書くなら foldl を使えという事なのでしょう。

foldl f z []      = z
foldl f z (x:xs)  = foldl f (f z x) xs

foldl と foldr の関係は、継続という観点から見ると面白いです。それを確かめるために、先ほどの 1 - 2 - 3 - 4 を無理やり foldr で書いてみます。

cont [2, 3, 4] 1 where cont xs = foldr (\x f -> (\n -> f (n - x))) id xs

foldr で引き算のような左再帰の計算をするにはこのように継続渡し形式にする必要があります。つまり、この foldr は計算の結果では無くて「あとでこれを引いてください」という状態を返し、最後に初期値の 1 を与えてざくっと左から頭から計算するわけです。これを一般化して foldr で foldl を実装してみます。

foldrl f z xs = cont z
    where cont = foldr (\x g -> (\n -> g (f n x))) id xs

reverserl xs = foldrl (flip (:)) [] xs -- 動作確認のため reverse を実装。

と言うわけで、嬉しがって CPS 変換するなら(略

追記

筆が滑って foldl は「末尾再帰を意味します」と書いたけど、どうも末尾再帰で書いても Haskell はスタックを伸ばしまくるらしい。Prelude.hs では sum 等の実装に fold' という別の関数を定義してメモリ節約の工夫がしてある。のに、この fold' は外から見えない。どケチ！

foldl' f a []     = a
foldl' f a (x:xs) = (foldl' f $! f a x) xs

Main> foldl' (+) 0 [1..0x7eff1]
135292315753
Main> foldl (+) 0 [1..0x7eff1]
Process hugs exited abnormally with code 5

参考