使用foldr书写foldl
在真实世界Haskell中 ，第4章函数式编程
用foldr写下foldl：
-- file: ch04/Fold.hs
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)
上面的代码让我很困惑，有些叫做dps的人用一些有意义的名字来重写它，使它更清晰一些：
myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL
where stepR lastL accR accInitL = accR (stepL accInitL lastL)
一个人杰夫G然后做了一个很好的工作，通过提供一个例子，并逐步显示潜在的机制：
myFoldl (+) 0 [1, 2, 3]
= (foldR step id [1, 2, 3]) 0
= (step 1 (step 2 (step 3 id))) 0
= (step 1 (step 2 (a3 -> id ((+) a3 3)))) 0
= (step 1 (a2 -> (a3 -> id ((+) a3 3)) ((+) a2 2))) 0
= (a1 -> (a2 -> (a3 -> id ((+) a3 3)) ((+) a2 2)) ((+) a1 1)) 0
= (a1 -> (a2 -> (a3 -> (+) a3 3) ((+) a2 2)) ((+) a1 1)) 0
= (a1 -> (a2 -> (+) ((+) a2 2) 3) ((+) a1 1)) 0
= (a1 -> (+) ((+) ((+) a1 1) 2) 3) 0
= (+) ((+) ((+) 0 1) 2) 3
= ((0 + 1) + 2) + 3
但我仍然不能完全理解，这是我的问题：
有没有人可以帮助我？ 非常感谢！
一些解释是为了！
什么是id功能？ 什么是角色？ 我们为什么需要这里？
id是标识函数， id x = x ，当用函数组合函数(.)构建一系列函数时，它被用作零的等价值。 你可以在Prelude中找到它。
在上面的例子中，id函数是lambda函数中的累加器吗？
累加器是通过重复功能应用程序构建的功能。 没有明确的lambda，因为我们将累加器命名为step 。 如果你想要的话，你可以写一个lambda表达式：
foldl f a bs = foldr (b g x -> g (f x b)) id bs a
或者正如格雷厄姆赫顿所写：
foldr的原型是foldr ::（a→b→b）→b→a→b
Haskell程序员会说foldr的类型是(a -> b -> b) -> b -> [a] -> b 。
第一个参数是一个需要两个参数的函数，但myFoldl实现中的step函数使用3个参数，我完全困惑
这是令人困惑和神奇的！ 我们玩弄一个技巧，用一个函数代替累加器，然后将函数应用于初始值以产生结果。
Graham Hutton解释了在上面的文章中将foldl变成foldr的技巧。 我们首先写下foldl的递归定义：
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x : xs) = foldl f (f v x) xs
然后通过f上的静态参数转换重构它：
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v xs = g xs v
where
g [] v = v
g (x:xs) v = g xs (f v x)
现在让我们重写g以便向内浮动v ：
foldl f v xs = g xs v
where
g [] = v -> v
g (x:xs) = v -> g xs (f v x)
这与将g为一个参数的函数相同，它返回一个函数：
foldl f v xs = g xs v
where
g [] = id
g (x:xs) = v -> g xs (f v x)
现在我们有g ，一个递归遍历列表的函数，应用一些函数f 。 最终的值是身份函数，并且每一步都会产生一个函数。
但是，我们在列表上已经有了一个非常类似的递归函数， foldr ！
这看起来像我们的g函数非常类似的递归方案。 现在诀窍：使用所有可用的魔术（又名Bird，Meertens和Malcolm），我们应用了一个特殊规则， 折叠的通用属性 ，它是处理列表的函数g两个定义之间的等价关系，表示为：
所以，褶皱的普遍属性指出：
g = foldr k v
其中g必须等价于两个方程，对于某些k和v ：
g [] = v
g (x:xs) = k x (g xs)
从我们早期的foldl设计中，我们知道v == id 。 对于第二个等式，我们需要计算 k的定义：
g (x:xs) = k x (g xs)
<=> g (x:xs) v = k x (g xs) v -- accumulator of functions
<=> g xs (f v x) = k x (g xs) v -- definition of foldl
<= g' (f v x) = k x g' v -- generalize (g xs) to g'
<=> k = x g' -> (a -> g' (f v x)) -- expand k. recursion captured in g'
其中，用我们计算的k和v的定义代替foldl的定义如下：
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v xs =
foldr
(x g -> (a -> g (f v x)))
id
xs
v
递归g被foldr组合器替换，并且累加器变成通过在列表的每个元素处f的合成链构建的函数，以相反的顺序（所以我们向左而不是向右）。
这绝对是先进的，所以为了深刻理解这种转变，褶皱的普遍属性，这使得转化成为可能，我推荐Hutton的教程，下面链接。
参考
考虑foldr的类型：
foldr :: (b -> a -> a) -> a -> [b] -> a
而step的类型就像b -> (a -> a) -> a -> a 。 由于step已经传递给foldr ，所以我们可以得出结论，在这种情况下，fold的类型就像(b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a) 。
不要的不同含义混淆a不同的签名; 它只是一个类型变量。 另外，请记住，函数箭头是正确的关联，所以a -> b -> c与a -> (b -> c) 。
所以，是的， foldr的累加器值是类型a -> a的函数，初始值是id 。 这是有道理的，因为id是一个不起任何作用的函数 - 当添加列表中的所有值时，您将以零作为初始值开始的原因是一样的。
至于采取三个参数的step ，请尝试像这样重写它：
step :: b -> (a -> a) -> (a -> a)
step x g = a -> g (f a x)
这是否使得更容易看到发生了什么？ 它需要一个额外的参数，因为它正在返回一个函数，并且它的两种写法是等价的。 请注意foldr之后的额外参数： (foldr step id xs) z 。 括号中的部分是折叠本身，它返回一个函数，然后将其应用于z 。
这是我的证明foldl可以用foldr来表示，除了step函数引入的名称意大利面之外，我发现它很简单。
命题是foldl fz xs等价于
myfoldl f z xs = foldr step_f id xs z
where step_f x g a = g (f a x)
首先要注意的是，第一行的右侧实际上被评估为
(foldr step_f id xs) z
因为foldr只需要三个参数。 这已经暗示了foldr将计算出的不是一个值，而是一个curried函数，然后将其应用于z 。 有两种情况需要调查以确定myfoldl是否是foldl ：
基本情况：空列表
myfoldl f z []
= foldr step_f id [] z (by definition of myfoldl)
= id z (by definition of foldr)
= z
foldl f z []
= z (by definition of foldl)
非空列表
myfoldl f z (x:xs)
= foldr step_f id (x:xs) z (by definition of myfoldl)
= step_f x (foldr step_f id xs) z (-> apply step_f)
= (foldr step_f id xs) (f z x) (-> remove parentheses)
= foldr step_f id xs (f z x)
= myfoldl f (f z x) xs (definition of myfoldl)
foldl f z (x:xs)
= foldl f (f z x) xs
由于在2中，第一行和最后一行在两种情况下都具有相同的形式，因此它可以用于将列表向下折叠，直到xs == [] ，在这种情况下，1.保证相同的结果。 所以通过归纳， myfoldl == foldl 。