你怎么知道什么时候使用折叠和何时使用折叠权？ [英] How do you know when to use fold-left and when to use fold-right?

问题描述

我知道折叠左边会产生左倾的树木，而右边的右边会产生右倾的树木，但是当我达到折叠的时候，我有时会发现自己陷入了头痛的困境中，试图确定一种折叠是适当的。我通常最终解开整个问题，并逐步执行fold函数，因为它适用于我的问题。

所以我想知道的是：

• 拇指确定是折叠还是折叠？


• 如何在给定问题的情况下快速决定使用哪种类型的折叠？

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

由于折叠在（功能性）编程中是一种常见的行为，我希望能够迅速而自信地做出这些决定。所以......任何提示？

解决方案

您可以将折叠转换为中缀运算符表示法p>

这个例子使用累加器函数fold 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 //  - 是左关联的
  

如果您的操作符是右键菜单，
$ b

  A x（B x （C x D））
  

示例：Cons-Operator

  foldr（:) [] [1，2，3] == 1：（2：（3：[]））== 1：2：3：[ ] == [1，2，3] 
  

一般来说，算术运算符 - 关联的，所以 foldl 更广泛。但在其他情况下，中缀记法+圆括号非常有用。

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.

So what I want to know is:

• What are some rules of thumb for determining whether to fold left or fold right?
• How can I quickly decide which type of fold to use given the problem I'm facing?

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):

This example fold using the accumulator function x

fold x [A, B, C, D]

thus equals

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

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))

Example: Cons-Operator

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

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屋！