language-agnostic - 您如何知道何时使用左折叠和右折叠？

Question

我知道左折叠会产生左倾树，右折叠会产生右倾树，但是当我伸手去折叠时，有时我会发现自己陷入了令人头疼的想法中，试图确定哪一个是右倾树。折叠方式合适。我通常最终会解开整个问题，并逐步完成适用于我的问题的折叠函数的实现。

所以我想知道的是:

• 确定向左折叠还是向右折叠的经验法则是什么？
• 鉴于我面临的问题，如何快速决定使用哪种类型的折叠？

Scala by Example中有一个例子(PDF) 使用折叠编写一个名为 flatten 的函数，该函数将元素列表的列表连接成单个列表。在这种情况下，正确的折叠是正确的选择(考虑到列表的连接方式)，但我必须考虑一下才能得出这个结论。

由于折叠是(函数式)编程中的常见操作，因此我希望能够快速而自信地做出此类决策。那么...有什么建议吗？

Answer 1

您可以将折叠转换为中缀运算符表示法(写在中间):

此示例使用累加器函数进行折叠 x

fold x [A, B, C, D]

因此等于

A x B x C x D

现在您只需推理运算符的结合性(通过添加括号!)。

如果您有一个左关联运算符，您将像这样设置括号

((A x B) x C) x D

在这里，您使用左折叠。示例(haskell 风格的伪代码)

foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative

如果您的运算符是右关联的(右折叠)，则括号将如下设置:

A x (B x (C x D))

示例:Cons-Operator

foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3]

一般来说，算术运算符(大多数运算符)都是左结合的，因此 foldl 更为普遍。但在其他情况下，中缀符号+括号非常有用。