RWHの4章にfoldlをfoldrによって書く例が載っていたのだけど、ぱっと見ただけではわからなかったので良く考えてみた。
Real World Haskell―実戦で学ぶ関数型言語プログラミングBryan O'Sullivan,John Goerzen,Don Stewart
オライリージャパン / ￥ 3,990 ()
在庫あり。
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)
これは結局
foldr step id xs
によって出来た関数に本来の初期値であるzを与えていると。
例えば
myFoldl (+) 0 [1..3]
だと
foldr (+) id [1..3]
により
\x -> (+3) $ (+2) $ (+1) (id x)
が出来てこれに元の初期値0が与えられて(3+(2+(1+0)))となる。
参考