你怎么知道什么时候用左折叠，什么时候用右折叠? [英] How do you know when to use fold-left and when to use fold-right?

问题描述

我知道向左折叠会产生左倾树，向右折叠会产生右倾树，但是当我伸手去折叠时，我有时会发现自己陷入了令人头疼的想法中，试图确定哪个那种折叠是合适的.我通常最终会展开整个问题，并逐步执行 fold 函数的实现，因为它适用于我的问题.

I'm aware that fold-left produces left-leaning trees and fold-right produces right-leaning trees, but when I reach for a fold, I sometimes find myself getting bogged down in headache-inducing thought trying to determine which kind of fold is appropriate. I usually end up unwinding the entire problem and stepping through the implementation of the fold function as it applies to my problem.

所以我想知道的是:

• 确定向左折叠还是向右折叠有哪些经验法则?
• 鉴于我面临的问题，我如何快速决定使用哪种折叠方式?

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

There is an example in Scala by Example (PDF) of using a fold to write a function called flatten which concatenates a list of element lists into a single list. In that case, a right fold is the proper choice (given the way the lists are concatenated), but I had to think about it a bit to arrive at that conclusion.

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

Since folding is such a common action in (functional) programming, I'd like to be able to make these kinds of decisions quickly and confidently. So... any tips?

推荐答案

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

You can transfer a fold into an infix operator notation (writing in between):

这个例子使用累加器函数x

This example fold using the accumulator function x

fold x [A, B, C, D]

因此等于

A x B x C x D

现在您只需要推理运算符的结合性(通过放入括号！).

Now you just have to reason about the associativity of your operator (by putting parentheses!).

如果你有一个左结合运算符，你可以像这样设置括号

If you have a left-associative operator, you'll set the parentheses like this

((A x B) x C) x D

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

Here, you use a left fold. Example (haskell-style pseudocode)

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

如果您的运算符是右结合(右折叠)，则括号将设置为:

If your operator is right-associative (right fold), the parentheses would be set like this:

A x (B x (C x D))

示例:Cons-Operator

Example: Cons-Operator

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

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

In general, arithmetic operators (most operators) are left-associative, so foldl is more widespread. But in the other cases, infix notation + parentheses is quite useful.

这篇关于你怎么知道什么时候用左折叠，什么时候用右折叠?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！