列表说明：折叠功能

Question

我对Erlang语言的了解越来越多，最近遇到了一些问题。我读到有关foldl(Fun, Acc0, List) -> Acc1功能的信息。我使用了learnyousomeerlang.com教程，并且有一个示例（示例是关于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].

据我了解，lists:foldl在列表中的每个元素上执行rpn/2。但是据我所能理解的这个功能。我阅读了文档，但对我没有太大帮助。有人可以向我解释lists:foldl的工作原理吗？

Answer 1

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

1 + 2 + 3 + 4.

这是一种非常普通的编写方式。但是我写的是“加一个数字列表”，而不是“写数字之间加上加号”。我在散文中表达操作的方式与我所使用的数学符号之间存在根本上的区别。我们这样做是因为我们知道它是加法的等效表示法（因为它是可交换的），并且在我们的脑海中它立即减少为：

3 + 7.

然后

10.

那么有什么大不了的？问题在于我们无法从此示例中理解sumsum的想法。如果我写的是“从0开始，然后一次从列表中取出一个元素，并将其作为起始总和添加到起始值”，该怎么办？这实际上是求和的意思，在等式简化之前，并不是任意决定先添加哪两项。

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

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

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

上面的功能有问题；它是太具体了。它把三个想法编织在一起，而没有独立地指定它们：

• 迭代
• 累积
• 添加

很容易错过迭代和累加之间的差异，因为在大多数情况下，我们从不再考虑这一点。实际上，大多数语言意外地鼓励我们忽略这种差异，实际上，是通过在相同功能的每次迭代中使相同的存储位置更改其值。

仅由于本示例中加法的编写方式而容易错过加法的独立性，因为“ +”看起来像是“操作”，而不是函数。

如果我说过“从1开始，然后一次从列表中取出一个元素，然后将其乘以运行值怎么办？”我们仍然会以完全相同的方式进行列表处理，但是通过两个示例进行比较，很明显乘法和加法是两者之间的唯一区别：

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

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

这是完全相同的执行流程，但用于内部运算和累加器的起始值。

所以让我们将加法和乘法位放入函数中，以便我们可以将模式的那部分拉出来：

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

我们如何单独编写列表操作？我们需要传入一个函数-加法或乘法-并对值进行运算。另外，我们必须注意正在操作的事物的类型和操作的身份，否则我们将搞砸价值聚合的魔力。 “ add（0，X）”总是返回X，因此这个想法（0 + Foo）是附加身份操作。在乘法中，标识运算将乘以1。因此，我们必须将累加器从0开始进行加法运算，将其从1开始进行乘法运算（并为构建列表创建一个空列表，依此类推）。因此，我们不能使用内置的累加器值来编写函数，因为它仅对某些类型+操作对有效。

所以这意味着要写一个折叠，我们需要有一个列表参数，一个做事参数的函数以及一个累加器参数，例如：

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

有了这个定义，我们现在可以使用这种更通用的模式来编写sum / 1：

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

和prod / 1也：

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

它们在功能上与我们在上面写的相同，但是符号更清晰，我们不必编写一堆递归的细节，它们将迭代的思想与累积的思想纠缠在一起。一些特定运算（例如乘法或加法）的想法。对于RPN计算器，聚合列表操作的思想与选择性调度的概念结合在一起（根据遇到/匹配的符号选择要执行的操作）。 RPN示例相对简单且小巧（您可以一次将所有代码放入脑中，只有几行），但是直到您习惯了功能范式后，它所体现的过程才可能使您的头部受伤。在函数式编程中，仅基于列表操作和选择性分派，少量的代码就可以创建任意复杂的不可预测（甚至不断演变！）行为的过程。这与当今更常见的其他范式中使用的条件检查，输入验证和过程检查技术有很大不同。单次赋值和递归表示法有助于分析此类行为，因为每个迭代都是概念上独立的

时间片

，可以将其与系统的其余部分隔离开来。我说的是基本问题，但您可能会想想这是一个核心概念，因为您考虑why我们喜欢使用折叠和递归表示法之类的操作，而不是程序化的，多次赋值的循环。 我希望这能帮助我们避免困惑。

首先，您必须记住rpn的工作原理。如果要执行以下操作：2 * (3 + 5)，将使用输入"3 5 + 2 *"输入功能。这在您有25步输入程序时非常有用：o）

第一个调用的函数只是将该字符列表拆分为元素：

1> string:tokens("3 5 + 2 *"," ").
["3","5","+","2","*"]
2>

然后，它处理list：foldl / 3。对于此列表的每个元素，将使用输入列表的开头和当前累加器调用rpn / 2，并返回一个新的累加器。让我们一步一步走：

Step head  accumulator  matched rpn/2                           return value
1    "3"   []           rpn(X, Stack) -> [read(X) | Stack].    [3]
2    "5"   [3]          rpn(X, Stack) -> [read(X) | Stack].    [5,3]
3    "+"   [5,3]        rpn("+", [N1,N2|S]) -> [N2+N1|S];      [8]
4    "2"   [8]          rpn(X, Stack) -> [read(X) | Stack].    [2,8]
5    "*"   [2,8]        rpn("*",[N1,N2|S]) -> [N2*N1|S];       [16]

[最后，lists:foldl/3返回与[16]匹配的[R]，尽管rpn / 1返回R = 16

Answer 2