foldlをfoldrで実装する

はじめに

@ruiccさんのスペースリーク、その傾向と対策のコメント欄において、@maoeさんが「最近のbaseではfoldlの実装にfoldrを使っている」という内容のコメントをされていました。
そのリンク先では、次のような形でfoldlを定義しています。

foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
foldl k z0 xs = foldr (\(v::a) (fn::b->b) (z::b) -> fn (k z v)) (id :: b -> b) xs z0

(；・∀・)
(；・∀・)
(；・∀・)
(；・∀・)
(´・ω・｀)

なにを言っているのかわけがわからないですね！
ということで、スペースリーク自体とは多少離れてしまうかもしれませんが、この記事ではなぜこれがfoldlになるのかを少しずつ解き明かしていきます。
きっと、foldrによる定義をすると、どのように最適化されてどのようにスペースリークが抑制されるかなどは、誰かが教えてくれると思います。

読み解いてみる

実はfoldlをfoldrで実装する方法については、Real World Haskellでも少し触れていますが、なぜそのように書けるのか詳細については触れていません。
Real World Haskellでは、次のような定義になっています。

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z xs = foldr step id xs z     -- (1)
    where step x g a = g (f a x)

前述の式のラムダ式の部分に名前をつけてwhere節に分けただけなので、本質的には変わりありませんね？

ここで、本来 foldr :: (a -> b -> b) -> b -> [a] -> b で、引数を2つしかとらないfoldrに3つの引数を与えているように見えて紛らわしいので、このように書き換えましょう。

foldl f z xs = (foldr step id xs) z   -- (2)
    where step x g a = g (f a x)

(foldr step id xs) の中のfoldrは

foldr :: (b -> (a -> a) -> (a -> a)) -- step 関数
       -> (a -> a)                   -- id 関数
       -> [b]                        -- xs
       -> (a -> a)                   -- z を変換する関数

というように、関数を評価結果として返しています。
さらに、(2)の式のfは f :: a -> b -> a で2引数をとる関数なので、わかりやすさのために中置演算子で置き換えましょう。
つまり、f a b == a ?? b となる中置演算子??を使って

foldl (??) z xs = (foldr step id xs) z   -- (3)
    where step x g a = g (a ?? x)

と書き換えました。
同じくfoldrの引数のstepも step a b == a ?! b となる中置演算子?!を使うと...

foldl (??) z xs = (foldr (?!) id xs) z   -- (4)
    where (?!) x g a = g (a ?? x)

ここで、?!演算子を次のように変換します。


(?!) x g a
=> g (a ?? x)      -- (?!)の定義
=> g ((?? x) a)
=> g . (?? x) $ a  -- 関数合成の性質

つまり、(?!) x g = g . (?? x) です。
その結果、次のように書き換えられます。

foldl (??) z xs = (foldr (?!) id xs) z   -- (5)
    where x ?! g = g . (?? x)

では、式(5)の左辺がfoldlになることを確かめましょう。
カッコが多くて途中で??って気持ちになりそうですが、がんばって式変形を追うと最後に感動が待っています。


(foldr (?!) id xs) z
=> ((xs!!0) ?! ((xs!!1) ?! ( ... ((xs!!(n-1)) ?! ((xs!!n) ?! id)) ...))) z        -- foldrの展開
     where n = length(xs)
=> ((xs!!0) ?! ((xs!!1) ?! ( ... ((xs!!(n-1)) ?! (id . (?? (xs!!n)))) ...))) z    -- (?!)の定義
=> ((xs!!0) ?! ((xs!!1) ?! ( ... (id . (?? (xs!!n)) . (?? (xs!!(n-1)))) ...))) z  -- (?!)の定義
=> (id . (?? (xs!!n)) . (?? (xs!!(n-1))) . ... . (?? (xs!!1)) . (?? (xs!!0)))) z  -- (?!)の定義
=> ((?? (xs!!n)) . (?? (xs!!(n-1))) . ... . (?? (xs!!1)) . (?? (xs!!0))) z        -- idの定義
=> (?? (xs!!n)) . (?? (xs!!(n-1))) . ... . (?? (xs!!1)) $ (?? (xs!!0)) z          -- 関数合成の性質
=> (?? (xs!!n)) $ (?? (xs!!(n-1))) $ ... $ (?? (xs!!1)) $ (?? (xs!!0)) z          -- 関数合成の性質

いつの間にか、xsの要素の並びが逆順に変わっています。
それに気づいたあなたの気持ちは?!って感じでしょう。ほら、そういう意図でこんな中置演算子にしたのです(・∀・)
嘘です。こじつけです。

さて、最後の行の処理を読みとくと...

初期値zに対してxsの最初の要素を(??)で適用して
その結果に対してxsの次の要素を(??)で適用して
その結果に対してxsの次の要素を(??)で適用して
...

これはまさにfoldlの挙動ですね！

いつの間にリスト要素の順番が逆転したのでしょうか？

x ?! g = g . (?? x)

という?!の定義で、g （ここにfoldrによって右から「蓄積」されてきた関数が入る）の適用される順番が後（左）に移されています。
このトリックによって、気づいたらリストの各要素の並びが反転してしまうのです！
このトリック、なんだか差分リストを想起させますね。

あらためて定義を見てみよう！

ということで、このようなfoldrの使い方のメンタルモデル（@ruiccさんがこのアドベントカレンダーの最初の記事で意図した「メンタルモデル」という言葉の使い方ではないかもしれないですが...)ができたあとに改めて(5)の定義式をながめてみましょう。

foldl (??) z xs = (foldr (?!) id xs) z   -- (5)
    where x ?! g = g . (?? x)

foldrがzを変換するための関数を作っている
idを初期値にして、xsのリストを使ってすこしずつ関数を「育てて」いる
いままで育てられた関数が、(?? x) のあとに評価されるように合成している

ということが見えるようになり、「なんとなくfoldlになっているっぽい」と思えるようになったのではないでしょうか？

はすけるたのしい。