列表说明：折叠功能 [英] Explanation of lists:fold function

问题描述

我越来越多地学习Erlang语言，并且最近遇到了一些问题。我读了关于 foldl（Fun，Acc0，List） - > Acc1 功能。我使用了learnyousomeerlang.com教程，并且有一个例子（例子是关于在Erlang中使用Reverse Polish Notation Calculator）：

 ％function that删除所有的空白处，并且当is_list（L） - >时，执行
 rpn（L） 
 [Res] =列表：foldl（fun rpn / 2，[]，string：tokens（L，）），
 Res。 
 
％将字符串转换为整数或浮点值的函数
 read（N） - > 
大小写字符串：to_float（N）
返回{error，no_float}其中没有float可用
 {error，no_float}  - > list_to_integer（N）; 
 {F，_}  - > F 
结束。 
 
％rpn管理所有操作
 rpn（+，[N1，N2 | S]） - > [N2 + N1 | S]; 
 rpn（ - ，[N1，N2 | S]） - > [N2-N1 | S]; 
 rpn（*，[N1，N2 | S]） - > [N2 * N1 | S]; 
 rpn（/，[N1，N2 | S]） - > [N2 / N1 | S]; 
 rpn（^，[N1，N2 | S]） - > [数学：POW（N2，N1）| S]; 
 rpn（ln，[N | S]） - > [数学：日志（N）| S]; 
 rpn（log10，[N | S]） - > [数学：日志10（N）| S]; 
 rpn（X，Stack） - > [读（X）|堆栈。 
  

据我了解列表：foldl 对列表中的每个元素执行 rpn / 2 。但就我所能理解的这个功能而言。我阅读了文档，但它对我没什么帮助。有人能解释我如何列出：foldl 的作品？

解决方案

假设我们想将数字列表加在一起：

  1 + 2 + 3 + 4. 
  

这是一个很正常的写法。但是我写了一起添加数字列表，而不是在数字之间加上数字。在我用散文表达手术的方式和我使用的数学符号之间有一些根本性的不同。我们这样做是因为我们知道它是一个等价的加法符号（因为它是可交换的），在我们的脑海中它立即减少到：

然后

  10。 
  

那么有什么大不了的？问题是我们无法理解这个例子中的 summation 的概念。如果我写了从0开始，然后从列表中取一个元素并将其作为运行总和添加到起始值呢？这实际上是求和是关于什么的，它并不是随意决定先减少两个东西，直到方程式减少为止。

  sum （列表） - > sum（List，0）。 
 
 sum（[]，A） - >一个; 
 sum（[H | T]，A） - > sum（T，H + A）。 
  

如果您到目前为止与我在一起，那么您已经准备好了解折叠。

上面的函数有问题;它是太具体。它将三个想法辫在一起，没有单独指定任何东西：

• 迭代


• 累积



$ b

很容易错过迭代和累积之间的差异，因为大多数时候我们都不会给这个第二个想法。大多数语言意外地鼓励我们错过这种差异，实际上，通过让相同的存储位置在类似函数的每次迭代中改变它的值。





很容易错过独立性因为+看起来像是一个操作，而不是一个函数。



如果我说Start与1，然后从列表中取一个元素，并乘以运行值？我们仍然会以完全相同的方式进行列表处理，但有两个例子可以比较，很显然，乘法和加法是两者之间的唯一区别：



  prod（List） - > prod（List，1）。 
 
 prod（[]，A） - >一个; 
 prod（[H | T]，A） - >产品（T，H * A）。 
  

这与执行流程完全相同，但对于内部操作和累加器的起始值。





因此，让我们将加法和乘法位加入函数中，这样我们就可以将模式的这一部分拉出来：



  add（A，B） - > A + B 
 mult（A，B） - > A * B. 
  

我们如何才能自行编写列表操作？我们需要传递一个函数 - 加法或乘法 - 并使其在数值上运行。此外，我们必须关注我们正在操作的事物的类型和操作的身份，否则我们会搞砸魔术那就是价值聚合。 add（0，X）总是返回X，所以这个想法（0 + Foo）是加法身份操作。在乘法运算中，身份运算乘以1.因此，我们必须将累加器的0加1和乘1（以及构建列表空列表等）的累加器启动。所以我们不能用内置的累加器值来编写函数，因为它只适用于某些类型+操作对。





所以这意味着要写一个我们需要一个列表参数，一个做事情参数的函数和一个累加器参数，如下所示：



  fold（ []，_，累加器） - > 
累加器; 
 fold（[H | T]，Operation，Accumulator） - > 
 fold（T，操作，操作（H，累加器））。 
  

使用这个定义，我们现在可以使用这个更一般的模式写出sum / 1：

  fsum（List） - >折叠（List，fun add / 2,0）。 
  

还有prod / 1：



  fprod（List） - > （List，fun prod / 2，1）。 
  

它们在功能上与我们上面所写的相同，符号更加清晰，我们不必编写大量递归细节，将迭代思想与增殖思想和乘法或加法等特定操作的想法相混淆。





对于RPN计算器，聚合列表操作的概念与选择性调度的概念（根据遇到/匹配的符号挑选要执行的操作）相结合。 RPN的例子相对简单而且很小（你可以把所有的代码都放在头上，它只是几行），但是在你习惯了功能范例之后，它所表现出的过程会让你的头部受伤。在函数式编程中，仅仅基于列表操作和选择性调度，少量代码可以创建一个任意复杂的不可预知（甚至是演化！）行为过程;这与目前更常见的其他范例中使用的条件检查，输入验证和过程检查技术截然不同。对这种行为的分析很大程度上是由单一赋值和递归符号来辅助的，因为每次迭代都是一个概念上独立的时间片，可以在系统的其他部分独立进行设计。我在基本问题之前谈论了一点，但这是一个核心想法，您可能希望考虑一下为什么我们喜欢使用折叠和递归符号等操作而不是程序性，分配循环。





我希望这个帮助比混淆。




I learning more and more about Erlang language and have recently faced some problem. I read about foldl(Fun, Acc0, List) -> Acc1 function. I used learnyousomeerlang.com tutorial and there was an example (example is about Reverse Polish Notation Calculator in Erlang):

%function that deletes all whitspaces and also execute
rpn(L) when is_list(L) ->
  [Res] = lists:foldl(fun rpn/2, [], string:tokens(L," ")),
  Res.

%function that converts string to integer or floating poitn value
read(N) ->
  case string:to_float(N) of
    %returning {error, no_float} where there is no float avaiable
    {error,no_float} -> list_to_integer(N);
    {F,_} -> F
  end.

%rpn managing all actions
rpn("+",[N1,N2|S]) -> [N2+N1|S];
rpn("-", [N1,N2|S]) -> [N2-N1|S];
rpn("*", [N1,N2|S]) -> [N2*N1|S];
rpn("/", [N1,N2|S]) -> [N2/N1|S];
rpn("^", [N1,N2|S]) -> [math:pow(N2,N1)|S];
rpn("ln", [N|S])    -> [math:log(N)|S];
rpn("log10", [N|S]) -> [math:log10(N)|S];
rpn(X, Stack) -> [read(X) | Stack].

As far as I understand lists:foldl executes rpn/2 on every element on list. But this is as far as I can understand this function. I read the documentation but it does not help me a lot. Can someone explain me how lists:foldl works?

解决方案

Let's say we want to add a list of numbers together:

1 + 2 + 3 + 4.

This is a pretty normal way to write it. But I wrote "add a list of numbers together", not "write numbers with pluses between them". There is something fundamentally different between the way I expressed the operation in prose and the mathematical notation I used. We do this because we know it is an equivalent notation for addition (because it is commutative), and in our heads it reduces immediately to:

3 + 7.

and then

10.

So what's the big deal? The problem is that we have no way of understanding the idea of summation from this example. What if instead I had written "Start with 0, then take one element from the list at a time and add it to the starting value as a running sum"? This is actually what summation is about, and its not arbitrarily deciding which two things to add first until the equation is reduced.

sum(List) -> sum(List, 0).

sum([], A)    -> A;
sum([H|T], A) -> sum(T, H + A).

If you're with me so far, then you're ready to understand folds.

There is a problem with the function above; it is too specific. It braids three ideas together without specifying any independently:

• iteration
• accumulation
• addition

It is easy to miss the difference between iteration and accumulation because most of the time we never give this a second thought. Most languages accidentally encourage us to miss the difference, actually, by having the same storage location change its value each iteration of a similar function.

It is easy to miss the independence of addition merely because of the way it is written in this example because "+" looks like an "operation", not a function.

What if I had said "Start with 1, then take one element from the list at a time and multiply it by the running value"? We would still be doing the list processing in exactly the same way, but with two examples to compare it is pretty clear that multiplication and addition are the only difference between the two:

prod(List) -> prod(List, 1).

prod([], A)    -> A;
prod([H|T], A) -> prod(T, H * A).

This is exactly the same flow of execution but for the inner operation and the starting value of the accumulator.

So let's make the addition and multiplication bits into functions, so we can pull that part of the pattern out:

add(A, B)  -> A + B.
mult(A, B) -> A * B.

How could we write the list operation on its own? We need to pass a function in -- addition or multiplication -- and have it operate over the values. Also, we have to pay attention to the identity of the type and operation of things we are operating on or else we will screw up the magic that is value aggregation. "add(0, X)" always returns X, so this idea (0 + Foo) is the addition identity operation. In multiplication the identity operation is to multiply by 1. So we must start our accumulator at 0 for addition and 1 for multiplication (and for building lists an empty list, and so on). So we can't write the function with an accumulator value built-in, because it will only be correct for some type+operation pairs.

So this means to write a fold we need to have a list argument, a function to do things argument, and an accumulator argument, like so:

fold([], _, Accumulator) ->
    Accumulator;
fold([H|T], Operation, Accumulator) ->
    fold(T, Operation, Operation(H, Accumulator)).

With this definition we can now write sum/1 using this more general pattern:

fsum(List) -> fold(List, fun add/2, 0).

And prod/1 also:

fprod(List) -> fold(List, fun prod/2, 1).

And they are functionally identical to the one we wrote above, but the notation is more clear and we don't have to write a bunch of recursive details that tangle the idea of iteration with the idea of accretion with the idea of some specific operation like multiplication or addition.

In the case of the RPN calculator the idea of aggregate list operations is combined with the concept of selective dispatch (picking an operation to perform based on what symbol is encountered/matched). The RPN example is relatively simple and small (you can fit all the code in your head at once, its just a few lines), but until you get used to functional paradigms the process it manifests can make your head hurt. In functional programming a tiny amount of code can create an arbitrarily complex process of unpredictable (or even evolving!) behavior, based just on list operations and selective dispatch; this is very different from the conditional checks, input validation and procedural checking techniques used in other paradigms more common today. Analyzing such behavior is greatly assisted by single assignment and recursive notation, because each iteration is a conceptually independent slice of time which can be contemplated in isolation of the rest of the system. I'm talking a little ahead of the basic question, but this is a core idea you may wish to contemplate as you consider why we like to use operations like folds and recursive notations instead of procedural, multiple-assignment loops.

I hope this helped more than confused.

这篇关于列表说明：折叠功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！