[Haskell] foldlをfoldrを使って定義する

Real World Haskell P.100より

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

20分くらい理解できなかったわ……

括弧でくくると、

myFoldl f z xs = (foldr step id xs) z
  where step x g a = g (f a x)

つまり蓄積変数は(a->a)となる関数になっていて、
foldrで畳み込んだ結果の関数に初期値zを適用すると結果として型aの値を得られる。
（この時点で鈍い頭痛が）

foldrの適用関数(step)の第一引数は、foldrの第三引数のリストの要素の型であり、
step関数の第二引数と、結果の型はこのfoldr蓄積変数の型なので、
step関数の型は b -> (a->a) -> a -> aとなる。
（頭がZINZIN）

というわけで、foldrの型をもとのfoldlで宣言している型変数で置き換えると、
(b -> (a->a) -> (a->a)) -> (a->a) -> [b] -> (a->a)
になる。a->aをa'で置き換えると (b->a'->a') -> a' -> [b] -> a'。

んで、a->aの部分適用関数に結果を蓄積していく経緯は、、、
よくわからないので定義で展開してみる。

(foldr step id [x1, x2, x3]) = step x1 (step x2 (step x3 id)))
　　　　　　　　　　　= step x1 (step x2 (\z -> id (f z x3)))
                                          = step x1 ( \z' -> (\z -> f z x3) (f z' x2))
                                          = step x1 ( \z' -> f (f z' x2) x3)
                                          = \z'' -> (\z' -> f (f z' x2) x3) (f z'' x1)
                                          = \z'' -> f (f (f z'' x1) x2) x3)

をお、これは確かにfoldlの動作になっている！

step関数が3引数になっていて3番目の引数を関数fの第一引数に畳んでいくことで、
演算の順序を入れ替えつつ、初期値も畳み込み結果の最後に適用するようにしていくカンジ？
（頭痛薬ください）

しっかしよくこんなの思いついたよなあ。

タグ：Haskell