函数式语言中折叠/归约的实际使用
Fold（又名reduce）被认为是非常重要的高阶函数。 Map 可以用 fold 来表示 (请参阅此处）。但对我来说，这听起来更学术而不是实用。典型的用途可能是获取数字的总和、乘积或最大值，但这些函数通常接受任意数量的参数。那么当 (+ 2 3 5) 工作正常时为什么要写 (fold + 0 '(2 3 5)) 呢？我的问题是，在什么情况下使用 fold 最简单或最自然？
Fold (aka reduce) is considered a very important higher order function. Map can be expressed in terms of fold (see here). But it sounds more academical than practical to me. A typical use could be to get the sum, or product, or maximum of numbers, but these functions usually accept any number of arguments. So why write (fold + 0 '(2 3 5)) when (+ 2 3 5) works fine. My question is, in what situation is it easiest or most natural to use fold?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
fold的要点在于它更加抽象。这并不是说你可以做以前做不到的事情，而是你可以更轻松地做这些事情。使用
fold，您可以概括在两个元素上定义的任何函数，以应用于任意数量的元素。这是一个胜利，因为编写、测试、维护和修改应用两个参数的单个函数通常比列表更容易。而且编写、测试、维护等总是更容易。一个简单的函数而不是两个具有相似但不完全功能的函数。由于
fold（以及就此而言，map、filter和朋友）具有明确定义的行为，因此使用以下代码通常更容易理解代码这些函数比显式递归更重要。基本上，一旦您拥有一个版本，您就可以“免费”获得另一个版本。最终，您只需做更少的工作即可获得相同的结果。
The point of
foldis that it's more abstract. It's not that you can do things that you couldn't before, it's that you can do them more easily.Using a
fold, you can generalize any function that is defined on two elements to apply to an arbitrary number of elements. This is a win because it's usually much easier to write, test, maintain and modify a single function that applies two arguments than to a list. And it's always easier to write, test, maintain, etc. one simple function instead of two with similar-but-not-quite functionality.Since
fold(and for that matter,map,filter, and friends) have well-defined behaviour, it's often much easier to understand code using these functions than explicit recursion.Basically, once you have the one version, you get the other "for free". Ultimately, you end up doing less work to get the same result.
这里有一些简单的例子，其中
reduce效果非常好。查找每个子列表的最大值之和
Clojure：
Racket：
从列表构建映射
Clojure：
查看具有
reduce< 的更复杂的 clojure 示例/code>，查看我对 Project Euler 问题的解决方案18 & 67。另请参阅：减少与应用
Here are a few simple examples where
reduceworks really well.Find the sum of the maximum values of each sub-list
Clojure:
Racket:
Construct a map from a list
Clojure:
For a more complicated clojure example featuring
reduce, check out my solution to Project Euler problems 18 & 67.See also: reduce vs. apply
在 Common Lisp 中，函数不接受任何数量的参数。
每个 Common Lisp 实现中都定义了一个常量 CALL-ARGUMENTS -LIMIT，必须为 50 或更大。
这意味着任何此类可移植编写的函数都应接受至少 50 个参数。但它可能只是 50。
此限制的存在是为了允许编译器可能使用优化的调用方案，并且不提供可以传递无限数量的参数的一般情况。
因此，要在可移植的 Common Lisp 代码中真正处理大型（大于 50 个元素）列表或向量，有必要使用迭代结构、reduce、map 等。因此，也有必要不使用
(apply '+ large-list)而使用(reduce '+ large-list)。In Common Lisp functions don't accept any number of arguments.
There is a constant defined in every Common Lisp implementation CALL-ARGUMENTS-LIMIT, which must be 50 or larger.
This means that any such portably written function should accept at least 50 arguments. But it could be just 50.
This limit exists to allow compilers to possibly use optimized calling schemes and to not provide the general case, where an unlimited number of arguments could be passed.
Thus to really process large (larger than 50 elements) lists or vectors in portable Common Lisp code, it is necessary to use iteration constructs, reduce, map, and similar. Thus it is also necessary to not use
(apply '+ large-list)but use(reduce '+ large-list).使用折叠的代码通常难以阅读。这就是为什么人们更喜欢使用 map、filter、exists、sum 等（如果可用）。这些天我主要编写编译器和解释器；以下是我使用折叠的一些方法：
所有这些用途的共同点是它们将有关序列的信息积累到某种集合或中>字典。 非常实用。
Code using fold is usually awkward to read. That's why people prefer map, filter, exists, sum, and so on—when available. These days I'm primarily writing compilers and interpreters; here's some ways I use fold:
What all these uses have in common is that they're accumulating information about a sequence into some kind of set or dictionary. Eminently practical.
您的示例
(+ 2 3 4) 仅有效，因为您事先知道参数的数量。折叠适用于大小可能变化的列表。fold/reduce是“cdr-ing down a list”模式的通用版本。每个关于按顺序处理序列中的每个元素并从中计算一些返回值的算法都可以用它来表达。它基本上是 foreach 循环的功能版本。Your example
(+ 2 3 4) only works because you know the number of arguments beforehand. Folds work on lists the size of which can vary.fold/reduceis the general version of the "cdr-ing down a list" pattern. Each algorithm that's about processing every element of a sequence in order and computing some return value from that can be expressed with it. It's basically the functional version of the foreach loop.这是一个其他人还没有提到的例子。
通过使用具有小型且定义明确的接口（例如“fold”）的函数，您可以替换该实现，而不会破坏使用它的程序。例如，您可以制作一个在数千台 PC 上运行的分布式版本，因此排序算法使用它的将成为分布式排序，等等。您的程序将变得更强大、更简单、更快。
您的示例是一个简单的示例：
+已经接受任意数量的参数，在很小的内存中快速运行，并且已经由编写编译器的人编写和调试。这些属性通常不适用于我需要运行的算法。Here's an example that nobody else mentioned yet.
By using a function with a small, well-defined interface like "fold", you can replace that implementation without breaking the programs that use it. You could, for example, make a distributed version that runs on thousands of PCs, so a sorting algorithm that used it would become a distributed sort, and so on. Your programs become more robust, simpler, and faster.
Your example is a trivial one:
+already takes any number of arguments, runs quickly in little memory, and has already been written and debugged by whoever wrote your compiler. Those properties are not often true of algorithms I need to run.