foldl
定義
code:1.hs
foldl :: (a -> b -> a) -> a -> b -> a foldl f e [] = e
foldl f e (x:xs) = foldl f (f e x) xs
fold left
code:hs
1 : (2 : (3 : []))) -- 通常のリスト
(((0 + 1) + 2) + 3) -- foldl (+) 0 1,2,3 使用例
code:hs
sum' xs = foldl (+) 0 xs
関連
1.hsより一般化されているmrsekut.icon
code:hs
foldl :: (a -> b -> a) -> a -> t b -> a
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
foldrの定義と見比べてみると、いくつか余分なものを加えた形に見える code:hs
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z
https://gyazo.com/6dc5c306c6b5f7a1e47021a83246eeee
「foldrとfoldlの間にある双対定理」と「Dual型によって定義されるmappendの双対」の二つの双対が使われています もっかい読みたいmrsekut.icon
リストから数値や逆順のリストを出力する関数と相性が良い ref パフォーマンス的に
例えば、sumとかlengthとかreverseとか
reverseは配列生成じゃんmrsekut.icon
foldl' f (f e x) xsの()の部分が先に計算され、
「末尾の処理」はfoldl' f ■ xsとなっているため、これは末尾再帰
パフォーマンスの話
だから正格評価になっている？
foldlはこわれているのでなおす
基本的にfoldlではなく、foldl'を使うという話もある