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

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

```haskell
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
```
[ソース](https://hackage.haskell.org/package/base-4.7.0.2/docs/src/GHC-List.html#foldl#foldl)

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


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

```haskell
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
```
[ソース](https://hackage.haskell.org/package/base-4.8.0.0/docs/Data-List.html#v:foldl)

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

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

```haskell
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`は次のように定義されています。

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

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

```haskell
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関数なので、これを簡約します。

```haskell
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変換](https://ghc.haskell.org/trac/ghc/wiki/CallArity))

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

```haskell
 == 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以前の定義と見比べてみましょう。

```haskell
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`を使って以下のように定義されています。

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

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

```haskell
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`を渡したならば、それ以外の引数がどうだったとしても関数呼び出しの結果は停止しないあるいは例外を発生させる」ということです。

例えば

```haskell
f :: Int -> Int -> Int
f x y = if x > y then x else y
```
は`x > y`の評価時に両方の引数を評価するので、両方の引数に関して正格です。
一方

```haskell
f :: Int -> Int -> Int
f x y = if x > 0 then x else y
```
は第１引数に関しては正格ですが、第２引数に関しては正格ではありません。
実際`f 1 undefined`は`1`に評価されるためです。

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

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

```haskell
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`つきでコンパイルすると以下の出力をえます。

```console
[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`の多相性にあります。

```haskell
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`の正格性が推論されます。

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

## foldlの正格性
話を`foldl`に戻しましょう。

```haskell
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'`の場合を考えましょう。

```haskell
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`で実現できます。

```haskell
foldl' k z0 xs  = foldl (\acc z -> acc `seq` k acc z) z0 xs
```
とすれば良いです。
右辺を展開してみると以下のようになります。

```haskell
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で関数を呼び出します。**

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

```haskell
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`です。

```haskell
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`などとすれば大丈夫です。