使用foldr书写foldl

在真实世界中Haskell ，第4章函数式编程

用foldr写foldl：

-- file: ch04/Fold.hs myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl fz xs = foldr step id xs z where step xga = g (fax) 

上面的代码使我困惑不已，有些叫做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 

但是我还是不能完全理解，这是我的问题：

1. 什么是idfunction？ 有什么作用？ 为什么我们需要在这里？
2. 在上面的例子中，id函数是lambda函数中的累加器吗？
3. foldr的原型是 foldr ::（a→b→b→b→a→b） ，第一个参数是一个需要两个参数的函数，而myFoldl实现中的step函数使用3个参数，我完全困惑！

有谁能帮助我？ 非常感谢！

Answer 1

一些解释是为了！

什么是idfunction？ 有什么作用？ 为什么我们需要在这里？

id是标识函数 ， id x = x ，当用函数组合函数 (.)构build函数链时，它被用作零的等价值。 你可以在Prelude中find它。

在上面的例子中，id函数是lambda函数中的累加器吗？

累加器是一个通过反复function应用程序正在build立的function。 没有明确的lambda，因为我们命名accumulator， step 。 如果你想要，你可以写一个lambdaexpression式：

 foldl fa bs = foldr (\bgx -> g (fxb)) id bs a 

或者如格雷厄姆·赫顿 （ Graham Hutton）所写 ：

---

---

foldr的原型是foldr ::（a→b→b）→b→a→b

Haskell程序员会说foldr的types是(a -> b -> b) -> b -> [a] -> b 。

第一个参数是一个需要两个参数的函数，但myFoldl的实现中的step函数使用了三个参数，我完全搞糊涂了

这是令人困惑和神奇的！ 我们玩一个技巧，用一个函数代替累加器，然后将函数应用到初始值，以产生结果。

格雷厄姆·赫顿（Graham Hutton）解释了在上面的文章中把foldl变成foldr的技巧。 我们首先写下一个foldl的recursion定义：

 foldl :: (a -> b -> a) -> a -> [b] -> a foldl fv [] = v foldl fv (x : xs) = foldl f (fvx) xs 

然后通过f上的静态参数转换重构它：

 foldl :: (a -> b -> a) -> a -> [b] -> a foldl fv xs = g xs v where g [] v = v g (x:xs) v = g xs (fvx) 

现在我们来重写g以便向内浮动v ：

 foldl fv xs = g xs v where g [] = \v -> v g (x:xs) = \v -> g xs (fvx) 

这与将g作为一个参数的函数相同，返回一个函数：

 foldl fv xs = g xs v where g [] = id g (x:xs) = \v -> g xs (fvx) 

现在我们有g ，一个recursion地遍历列表的函数，应用一些函数f 。 最后的值是身份函数，每一步都会产生一个函数。

但是 ，我们在列表上已经有了一个非常相似的recursion函数， foldr ！

---

---

这看起来像我们的g函数非常相似的recursionscheme。 现在我们使用所有可用的魔法（又名Bird，Meertens和Malcolm），我们应用了一个特殊的规则， 折叠的普遍性质 ，它是一个处理列表的函数g两个定义之间的等价关系，表示为：

---

---

所以，褶皱的普遍属性指出：

  g = foldr kv 

其中g必须等价于两个方程，对于一些k和v ：

  g [] = v g (x:xs) = kx (g xs) 

从我们之前的foldldevise中，我们知道v == id 。 对于第二个方程，我们需要计算 k的定义：

  g (x:xs) = kx (g xs) <=> g (x:xs) v = kx (g xs) v -- accumulator of functions <=> g xs (fvx) = kx (g xs) v -- definition of foldl <= g' (fvx) = kxg' v -- generalize (g xs) to g' <=> k = \xg' -> (\a -> g' (fvx)) -- expand k. recursion captured in g' 

其中，将我们计算出的k和v的定义代入foldl，定义如下：

 foldl :: (a -> b -> a) -> a -> [b] -> a foldl fv xs = foldr (\xg -> (\a -> g (fvx))) id xs v 

recursiong被foldr组合器replace，并且累加器变成通过在列表的每个元素处f的组合链构build的函数，以相反的顺序（所以我们向左而不是向右折叠）。

这肯定是有些先进的，所以为了深刻理解这种转变， 褶皱的普遍属性 ，使转化成为可能，我推荐Hutton的教程。

---

参考

• Haskell Wiki：foldr和foldr
• 关于fold的普遍性和expression性的教程 ，Graham Hutton，J. Functional Programming 9（4）：355-372，1999年7月。
• Malcolm，G. 代数数据types和程序转换。 ，格罗宁根大学博士论文。

Answer 2

考虑foldr的types：

 foldr :: (b -> a -> a) -> a -> [b] -> a 

而types的step是像b -> (a -> a) -> a -> a 。 由于步骤已经过渡到foldr ，我们可以得出结论，在这种情况下，折叠具有类似于(b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a) 。

不要被不同签名中的不同含义混淆， 这只是一个typesvariables。 另外，请记住，函数箭头是正确的关联，所以a -> b -> c和a -> (b -> c) 。

所以，是的， foldr的累加器值是typesa -> a的函数 ，初始值是id 。 这是有道理的，因为id是一个不起任何作用的函数 – 当添加列表中的所有值时，您将以零作为初始值开始的原因是一样的。

至于采取三个参数的step ，请尝试像这样重写：

 step :: b -> (a -> a) -> (a -> a) step xg = \a -> g (fax) 

这是否使得更容易看到发生了什么？ 它需要一个额外的参数，因为它正在返回一个函数，写这两个方法是等价的。 注意foldr之后的额外参数： (foldr step id xs) z 。 括号中的部分是折叠本身，它返回一个函数，然后将其应用于z 。

Answer 3

这是我的certificate， foldl可以用foldr来表示，除了step函数引入的意大利名字以外，我发现它很简单。

命题是foldl fz xs相当于

 myfoldl fz xs = foldr step_f id xs z where step_f xga = g (fax) 

在这里要注意的第一件重要的事情是，第一行的右侧实际上被评估为

 (foldr step_f id xs) z 

因为foldr只需要三个参数。 这已经暗示了foldr将不会计算一个值，而是一个curried函数，然后将其应用于z 。 有两个案例来调查，以确定myfoldl是否是foldl ：

1. 基本情况：空列表

     myfoldl fz [] = foldr step_f id [] z (by definition of myfoldl) = id z (by definition of foldr) = z foldl fz [] = z (by definition of foldl) 

2. 非空列表

     myfoldl fz (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) (fzx) (-> remove parentheses) = foldr step_f id xs (fzx) = myfoldl f (fzx) xs (definition of myfoldl) foldl fz (x:xs) = foldl f (fzx) xs 

由于在第一行和最后一行在两种情况下都具有相同的forms，因此它可以用于将列表向下折叠，直到xs == [] ，在这种情况下，保证相同的结果。 所以通过归纳， myfoldl == foldl 。

Answer 4

^{（快速浏览我的答案[1] ， [2] ， [3] ， [4] ，以确保您了解Haskell的语法，高阶函数，currying，函数组合，$运算符，中缀/前缀运算符， ）}

普遍性的折叠

折叠只是某种recursion的编纂。 而普遍性属性只是说，如果recursion符合某种forms，可以按照一些正式规则转化为折叠。 相反，每一个折叠都可以转化为这种recursion。 再一次，一些recursion可以翻译成折叠，给出完全相同的答案，一些recursion不能，并有一个确切的程序来做到这一点。

基本上，如果你的recursion函数在列表中看起来像在左边 ，你可以把它转换成右边的一个，用f和v代替实际存在的东西。

 g [] = v ⇒ g (x:xs) = fx (g xs) ⇒ g = foldr fv 

例如：

 sum [] = 0 {- recursion becomes fold -} sum (x:xs) = x + sum xs ⇒ sum = foldr 0 (+) 

这里v = 0和sum (x:xs) = x + sum xs相当于sum (x:xs) = (+) x (sum xs) ，因此f = (+) 。 另外2个例子

 product [] = 1 product (x:xs) = x * product xs ⇒ product = foldr 1 (*) length [] = 0 length (x:xs) = 1 + length xs ⇒ length = foldr (\_ a -> 1 + a) 0 

行使：

1. 像上面的函数一样，recursion地实现map ， filter ， reverse ， concat和concatMap 。

2. 根据上面的公式将这五个函数转换为foldr，即在右边的折叠公式中replacef和v 。

通过foldr折叠

如何编写一个从左到右总结数字的recursion函数？

 sum [] = 0 -- given `sum [1,2,3]` expands into `(1 + (2 + 3))` sum (x:xs) = x + sum xs 

find的第一个recursion函数在开始累加之前就已经完全展开了，这不是我们所需要的。 一种方法是创build一个具有累加器的recursion函数，在每一步中立即累加数字（阅读关于recursion的更多关于recursion策略的内容）：

 suml :: [a] -> a suml xs = suml' xs 0 where suml' [] n = n -- auxiliary function suml' (x:xs) n = suml' xs (n+x) 

好的，停下来！ 在GHCi中运行这个代码，并确保你明白它是如何工作的，然后小心谨慎地进行。 suml不能用fold来重新定义，但suml'可以。

 suml' [] = v -- equivalent: vn = n suml' (x:xs) n = fx (suml' xs) n 

suml' [] n = n从函数定义，对吧？ 而且通用属性公式中v = suml' [] 。 一起这给vn = n ，一个立即返回它收到的任何函数： v = id 。 我们来计算f ：

 suml' (x:xs) n = fx (suml' xs) n -- expand suml' definition suml' xs (n+x) = fx (suml' xs) n -- replace `suml' xs` with `g` g (n+x) = fxgn 

因此， suml' = foldr (\xgn -> g (n+x)) id ，因此， suml = foldr (\xgn -> g (n+x)) id xs 0 。

 foldr (\xgn -> g (n + x)) id [1..10] 0 -- return 55 

现在我们只需要概括一下，用一个variables函数replace+ ：

 foldl fa xs = foldr (\xgn -> g (n `f` x)) id xs a foldl (-) 10 [1..5] -- returns -5 

结论

现在阅读Graham Hutton 关于折叠的普遍性和expression性的教程 。 拿一些笔和纸，尽量弄清他写的所有东西，直到你自己得到大部分的折叠。 如果你不明白什么，不要stream汗，你可以随时回来，但也不要拖延。

Answer 5

没有math的皇家之路，甚至没有通过哈斯克尔。 让

 hz = (foldr step id xs) z where step xg = \a -> g (fax) 

什么是hz ？ 假设xs = [x0, x1, x2] 。
应用foldr的定义：

 hz = (step x0 (step x1 (step x2 id))) z 

应用步骤的定义：

 = (\a0 -> (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (f a0 x0)) z 

replace为lambda函数：

 = (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (fz x0) = (\a2 -> id (f a2 x2)) (f (fz x0) x1) = id (f (f (fz x0) x1) x2) 

应用id的定义：

 = f (f (fz x0) x1) x2 

应用foldl的定义：

 = foldl fz [x0, x1, x2] 

是皇家之路还是什么？