foldl 为 left-associative folding。
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs
foldl (+) 0 [1..3] 等价于 (((0 + 1) + 2) + 3)。
foldl'foldl' 为 foldl 的 TRO 版本。
foldr 为 right-associative folding。
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x:xs) = f x (foldr f acc xs)
foldr (+) 0 [1..3] 等价于 (0 + (1 + (2 + 3)))
Helper functions。将 operator 限制为同一种类型，同时约去 accumulator。
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs
foldl1 _ [] = error
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 f (x:xs) = foldr f x xs
foldr1 _ [] = error
即，foldr1 将列表的第一个值作为 accumulator，将剩余部分作为 list，传给 foldr。foldl 同理。
reversereversel, reverser :: [a] -> [a]
reversel list = foldl (\acc x -> x : acc) [] list
reverser list = foldr (\x acc -> acc ++ [x]) [] list
先归纳出 foldr 的泛性质。如果一个函数 g s.t.
g [] = v
g (x:xs) = f x (g xs)
则 g list === foldr f v list.
再看 foldl 的定义：
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs
===>
foldl f v list = g list v
where
g [] v = v
g (x:xs) v = g xs (f v x)
===>
foldl f v list = g list v
where
g [] = id
g (x:xs) = \v -> g xs (f v x)
应有 g (x:xs) === k x (g xs)，我们计算 k：
g (x:xs) === k x (g xs)
g (x:xs) v === k x (g xs) v
g xs (f v x) === k x (g xs) v
(g xs) (f v x) === k x (g xs) v
g' (f v x) === k x g' v
k === \x g' v -> g' (f v x)
所以
foldl f v xs =
(foldr
(\x g' v -> g' (f v x))
id
xs
) v
作者：hsfzxjy
链接：
许可：CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途，非商业转载请注明出处。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。