foldlをfoldrで実装する

# foldlをfoldrで実装する

## はじめに

@ruiccさんの[スペースリーク、その傾向と対策](http://qiita.com/ruicc/items/bfa659c2ef9e1f75f7e1)のコメント欄において、@maoeさんが「最近のbaseではfoldlの実装にfoldrを使っている」という内容のコメントをされていました。
[そのリンク先](https://github.com/ghc/packages-base/commit/b63facef165b957183b65604ef99b2b8574747a5)では、次のような形で`foldl`を定義しています。

```haskell
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でも[少し触れています](http://book.realworldhaskell.org/read/functional-programming.html)が、なぜそのように書けるのか詳細については触れていません。
Real World Haskellでは、次のような定義になっています。

```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つの引数を与えているように見えて紛らわしいので、このように書き換えましょう。

```haskell
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` となる中置演算子`??`を使って

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

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

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

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

```hs

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

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

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

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

```hs

(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)の定義式をながめてみましょう。

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

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

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

はすけるたのしい。