列表的解释：fold函数

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是如何工作的？

- Marcin Majewski

---

这个问题实际上比Erlang更为普遍，涉及到程序员不熟悉函数式编程范式时常见的绊脚石。这个特定示例的易读性让我想知道，如果用更一般的方式重新表述这个问题，它是否会对更多人有用。 - zxq9

Answer 1

假设我们想要将一些数字加在一起：

1 + 2 + 3 + 4.

这是一种比较普通的表达方式。但我写的是“将一系列数字相加”，而不是“在数字之间写上加号”。我用散文表达运算和使用的数学符号之间有根本性的区别。我们这样做是因为我们知道它是加法的等效符号（因为它是可交换的），并且在我们的头脑中它立即化简为：

3 + 7.

然后

10.

那么这有什么大不了的呢？问题在于从这个例子中我们无法理解“求和”的概念。如果我换一种写法，比如说“从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示例相对简单且小型（你可以一次性将所有代码都放在脑海中，只有几行），但是在你习惯函数式范例之前，它所表现出来的过程可能会让你头疼。在函数式编程中，少量的代码就可以创建一个基于列表操作和选择性分发的任意复杂、不可预测（甚至是演化的！）过程；这与今天更常见的其他范式中使用的条件检查、输入验证和过程检查技术非常不同。单赋值和递归符号大大地帮助了分析这种行为，因为每个迭代都是一个概念上独立的时间片，可以独立于系统的其余部分进行思考。我在回答基本问题之前稍微提前了一点，但这是一个核心思想，你可以在考虑为什么我们喜欢使用类似折叠和递归符号而不是过程化、多赋值循环时思考一下。

希望这比让你困惑更有帮助。

- zxq9

Answer 2

首先，您需要记住逆波兰表达式的工作原理。如果您想执行以下操作：2 * (3 + 5)，则应使用输入"3 5 + 2 *"调用函数。在以前需要输入25个步骤时，这非常有用 :o)

第一个函数简单地将此字符列表拆分为元素：

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

然后它处理列表：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。

- Pascal

---

这是一个很好的逐步指南，介绍了确切的foldl + rpn案例。我希望在这两个案例中（我的是通用的，这个是具体的），原始问题解决了“噢，哈！”时刻。 - zxq9