foldl vs. foldl'に終止符を打つ

今回はfoldlとfoldl'についてまとめます。

foldl

今から5年ほど前、base-4.7.0.2(GHC 7.8.4)の時代まで、foldlは以下のように定義されていました。

foldl        :: (b -> a -> b) -> b -> [a] -> b
foldl f z0 xs0 = lgo z0 xs0
             where
                lgo z []     =  z
                lgo z (x:xs) = lgo (f z x) xs

ソース

これはみなさん教科書で習うfoldlですね。

しかしbase-4.8(GHC 7.10)からfoldlは大きく変わってしまいました。

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

ソース

まず型からして違います。Foldable/Traversable Proposalによって、foldl, foldr, sum, anyなどの様々な関数が、リストだけでなくFoldable型クラス上で定義されるようになりました。

そしてその実装も大きく変わっています。

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

foldlがfoldrを用いて実装されています。
この定義は本当に正しいのか、確認してみましょう。

foldrは次のように定義されています。

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

この定義に従ってfoldlを変換していきましょう。

foldl k z0 xs 
 == foldr (\v fn -> oneShot (\z -> fn (k z v))) id xs z0
 -- foldrをインライン展開
 == go xs z0
    where go [] = id
          go (y:ys) = (\v fn -> oneShot (\z -> fn (k z v))) y (go ys)
 -- beta簡約
 == go xs z0
    where go [] = id
          go (y:ys) = oneShot (\z -> go ys (k z y))

oneShotはコンパイラへのヒントで実態はid関数なので、これを簡約します。

foldl k z0 xs 
 == ...
 == go xs z0
    where go [] = id
          go (y:ys) = (\z -> go ys (k z y))

さて、ここで再帰関数goは１引数関数ですが、返す値の型はb -> bです。すなわち、もう一つ引数を取ります。加えて、go関数を呼び出す箇所では必ず、2つの引数を同時に渡しています。このような場合goの定義をη展開して２引数関数にしても良いことが知られています。(Call Arity変換)

goを２引数関数に変換すると以下のようになります。

 == go xs z0
    where go [] eta = id eta
          go (y:ys) eta = (\z -> go ys (k z y)) eta
 -- idをインライン展開、beta簡約
 == go xs z0
    where go [] eta = eta
          go (y:ys) eta = go ys (k eta y)

さてこの定義をbase-4.7以前の定義と見比べてみましょう。

foldl        :: (b -> a -> b) -> b -> [a] -> b
foldl f z0 xs0 = lgo z0 xs0
             where
                lgo z []     =  z
                lgo z (x:xs) = lgo (f z x) xs

引数の順番こそ違いますが、全く同じ形をしていることがわかると思います。

コンパイルの過程では今説明したような変換が実際に行われているので安心してfoldlを使うことができます。(うまくいってないケースを見つけたらGHCにバグ報告を行いましょう)

foldl'

foldl'はGHCが今ほど賢くなかった時代に作られたfoldlの正格なバージョンです。
foldl同様現在はfoldrを使って以下のように定義されています。

foldl' k z0 xs =
  foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> z `seq` fn (k z v))) (id :: b -> b) xs z0

これも同様に変形していくと以下のような形になります。

foldl' k z0 xs
 == go xs z0
    where go [] eta = eta
          go (y:ys) eta = eta `seq` go ys (k eta y)

foldlとの違いは再帰関数goの第２引数(ここではaccumulation引数と呼びます)を正格に評価するということです。

foldl vs foldl'

さて、一般にfoldl'の方がaccumulation引数を正格に評価するため、効率が良いとされています。しかし最近のGHCは十分に賢いのでほとんどの場合foldlを使って大丈夫です。その理由はGHCの正格性解析にあります。

正格性

一般に$n$-引数関数$f$が$i$番目の引数について正格であるとは、
任意の項$e_1 \dots e_n$に対して$e_i = \bot$ならば$f\ e_1 ... e_n = \bot$
が成り立つことと定義されます。
ここで$\bot$はボトムすなわち停止しない項あるいはエラーを発生させる項(undefined)をさします。
言い換えると、「$i$番目の引数にundefinedを渡したならば、それ以外の引数がどうだったとしても関数呼び出しの結果は停止しないあるいは例外を発生させる」ということです。

例えば

f :: Int -> Int -> Int
f x y = if x > y then x else y

はx > yの評価時に両方の引数を評価するので、両方の引数に関して正格です。
一方

f :: Int -> Int -> Int
f x y = if x > 0 then x else y

は第１引数に関しては正格ですが、第２引数に関しては正格ではありません。
実際f 1 undefinedは1に評価されるためです。

GHCは適当な方法(Demand Analysis)で関数の正格性を推論します。この推論は健全ですが、完全ではありません。すなわち、実際には正格なのに正格でないと判断するケースがあります。
GHCがどのように正格性を推論したかは-ddump-str-signaturesでわかります。

試しに以下のプログラムで実験してみましょう。

module Hoge where

f1 :: Ord a => a -> a -> a
f1 x y = if x > y then x else y
{-# NOINLINE f1 #-}

g :: Int -> Int -> Int
g x y = f1 x y

f :: Int -> Int -> Int
f x y = if x > y then x else y

このプログラムを-O -ddump-str-signaturesつきでコンパイルすると以下の出力をえます。

[1 of 1] Compiling Hoge             ( Hoge.hs, Hoge.o )

==================== Strictness signatures ====================
Hoge.$trModule: m
Hoge.f: <S(S),1*U(U)><S(S),1*U(U)>m
Hoge.f1: <S(LLLLC(C(S))LLL),1*U(A,A,A,A,1*C1(C1(U)),A,A,A)><L,U><L,U>
Hoge.g: <L,U><L,U>



==================== Strictness signatures ====================
Hoge.$trModule: m
Hoge.f: <S(S),1*U(U)><S(S),1*U(U)>m
Hoge.f1: <S(LLLLC(C(S))LLL),1*U(A,A,A,A,1*C1(C1(U)),A,A,A)><L,U><L,U>
Hoge.g: <L,U><L,U>

同じような内容が２回出力されていますが気にしないてください。
Hoge.f: <S(S),1*U(U)><S(S),1*U(U)>mというのが解析結果を意味します。一つ目の<S(S),1*U(U)>の１番左の文字が第１引数の正格性を表していてSが正格、Lが非正格を意味ということです。つまり、fの両方の引数が正格であるということを意味しています。
一方でHoge.gの解析結果は<L,U><L,U>となっています。これは両方の引数が非正格であることを表します。fとgは同じ振る舞いをするはずですが解析結果が異なっています。これはGHCの正格性解析の不完全性を表しています。

この原因は関数f1の多相性にあります。

f1 :: Ord a => a -> a -> a
f1 x y = if x > y then x else y

f1が正格かどうかはx > yがx,yを正格に評価するかに依存します。
しかし、>は型クラスOrd上の関数であるのでこの時点では推論しようがありません。従って、保守的に非正格であると判定します。従ってf1はx, yの両方に非正格だと推論されます。

そのあとにgの正格性が推論されます。

g x y = f1 x y

gは関数f1を呼び出すのでf1の正格性から正格性を推論します。
f1は非正格だと推論されていたのでgも非正格となります。

foldlの正格性

話をfoldlに戻しましょう。

foldl k z0 xs
 == go xs z0
    where go [] eta = eta
          go (y:ys) eta = go ys (k eta y)

さて問題です。GHCはgoの正格性をどのように判定するでしょうか?

第１引数については正格だと判定します。なぜならパターンマッチによって
第１引数を必ず評価するからです。一方第二引数についてはどうでしょうか？

答えは「kの第１引数の正格性に依存する」です。kが多相化されている、あるいは変数である時など、正格性が自明でない場合は注意する必要があります。

一方foldl'の場合を考えましょう。

foldl' k z0 xs
 == go xs z0
    where go [] eta = eta
          go (y:ys) eta = eta `seq` go ys (k eta y)

この場合はgoは両方の引数について明らかに正格です。

それではfoldl'を使うべきなのでしょうか?
実はfoldl'と同等の関数をfoldlで実現できます。

foldl' k z0 xs  = foldl (\acc z -> acc `seq` k acc z) z0 xs

とすれば良いです。
右辺を展開してみると以下のようになります。

foldl (\acc z -> acc `seq` k acc z) z0 xs
 == go xs z0
    where go [] eta = eta
          go (y:ys) eta = go ys (eta `seq` k eta y)

foldl'を展開した結果とは微妙に異なりますが、正格性解析の結果は
foldl'の場合と同じようにgoは両方の引数に関して正格となります。

ここまで聞いた読者の中には
「引数が正格だからといって関数呼び出しはcall-by-needなのだから
やはりサンクがたまるのではないか？」と考えている人もいると思いますが
実は
GHCは正格な引数についてはcall-by-valueで関数を呼び出します。

従って以下のようなプログラムにコンパイルされます。

foldl (\acc z -> acc `seq` k acc z) z0 xs
 == go xs z0
    where go [] eta = eta
          go (y:ys) eta = case eta `seq` k eta y of 
            v -> go ys v

これはfoldl'の実装と全く同じ振る舞いをします。
従って歴史的な事情はどうあれ、現在のGHCではfoldl'のライブラリ関数としての重要性はあまり高くないと思われます。

補足：インライン展開

しかしながらfoldl関数がインライン展開されることはfoldlが効率よく動くための絶対条件です。foldlを呼び出す場合には３つの引数を必ず同時に渡すようにすべきです。

まとめ

foldlとfoldl'がどのようにコンパイルされるかを解説しました。
また、foldl' k z xsはfoldl (\acc v -> acc `seq` k acc v) z xsと同じ振る舞いをすることを紹介しました。

余談

正格性解析の罠となる関数が一つあります。それはDebug.Trace.trace及びDebug.Trace.traceShowです。

Debug.Trace.trace :: String -> a -> a
Debug.Trace.traceShow :: Show b => b -> a -> a

この関数は実際には第２引数を返すのにもかかわらず、両方の引数に関してなぜか非正格だとみなされます。
従ってある関数fの呼び出しをデバッグしたくてf x = trace "hoge" $ eなどとすると、eの中でどれだけxを評価していようと、xは非正格だと推論されます。
f !x = trace "hoge" $ eなどとすれば大丈夫です。