9

Fold(aka reduce) 被认为是一个非常重要的高阶函数。Map可以表示为fold（见这里）。但对我来说，这听起来比实际更学术。一个典型的用途可能是获取数字的总和、乘积或最大值，但这些函数通常接受任意数量的参数。那么为什么要(fold + 0 '(2 3 5))在(+ 2 3 5)工作正常时写。我的问题是，在什么情况下使用它最容易或最自然fold？

4

6 回答 6

13

关键fold是它更抽象。不是你可以做以前做不到的事情，而是你可以更轻松地完成它们。

使用 a fold，您可以概括在两个元素上定义的任何函数以应用于任意数量的元素。这是一个胜利，因为它通常更容易编写、测试、维护和修改应用两个参数的单个函数而不是列表。而且，编写、测试、维护等一个简单的函数总是比两个具有相似但不完全功能的函数更容易。

由于fold（以及就此而言，map、filter和朋友）具有明确定义的行为，因此使用这些函数理解代码通常比显式递归更容易理解。

基本上，一旦您拥有一个版本，您就可以“免费”获得另一个版本。最终，你最终会做更少的工作来获得相同的结果。

于 2011-03-16T21:28:07.240 回答
8

以下是一些reduce非常有效的简单示例。

求每个子列表的最大值之和

Clojure：

user=> (def x '((1 2 3) (4 5) (0 9 1)))
#'user/x
user=> (reduce #(+ %1 (apply max %2)) 0 x)
17

球拍：

> (define x '((1 2 3) (4 5) (0 9 1)))
> (foldl (lambda (a b) (+ b (apply max a))) 0 x)
17

从列表构造地图

Clojure：

user=> (def y '(("dog" "bark") ("cat" "meow") ("pig" "oink")))
#'user/y
user=> (def z (reduce #(assoc %1 (first %2) (second %2)) {} y))
#'user/z
user=> (z "pig")
"oink"

有关更复杂的 clojure 示例reduce，请查看我对 Project Euler 问题18和67的解决方案。

另请参阅：减少与应用

于 2011-03-16T21:27:20.663 回答
7

在 Common Lisp 中，函数不接受任何数量的参数。

在每个 Common Lisp 实现CALL-ARGUMENTS-LIMIT中都定义了一个常量，它必须是 50 或更大。

这意味着任何此类可移植编写的函数都应接受至少 50 个参数。但它可能只有 50 个。

存在此限制是为了允许编译器可能使用优化的调用方案，并且不提供可以传递无限数量的参数的一般情况。

因此，要在可移植的 Common Lisp 代码中真正处理大型（大于 50 个元素）列表或向量，有必要使用迭代构造、reduce、map 等。因此，也有必要不使用(apply '+ large-list)但使用(reduce '+ large-list).

于 2011-03-18T09:18:26.363 回答
5

使用 fold 的代码通常难以阅读。这就是为什么人们更喜欢 map、filter、exists、sum 等等——如果可用的话。这些天我主要在编写编译器和解释器。这是我使用折叠的一些方法：

  • 计算函数、表达式或类型的自由变量集
  • 将函数的参数添加到符号表中，例如，用于类型检查
  • 累积由一系列定义生成的所有合理错误消息的集合
  • 在启动时将所有预定义的类添加到 Smalltalk 解释器

所有这些用途的共同点是它们将有关序列的信息累积到某种集合或字典中。 非常实用。

于 2011-03-17T01:46:36.827 回答
4

  1. 您的示例(+ 2 3 4) 仅适用于您事先知道参数的数量。折叠适用于大小可以变化的列表。

  2. fold/reduce是“cdr-ing down a list”模式的一般版本。每个关于按顺序处理序列的每个元素并从中计算一些返回值的算法都可以用它来表示。它基本上是 foreach 循环的功能版本。

于 2011-03-16T22:36:38.733 回答
3

这是一个其他人尚未提及的示例。

通过使用具有像“fold”这样定义良好的小型接口的函数，您可以替换该实现而不会破坏使用它的程序。例如，您可以制作一个在数千台 PC 上运行的分布式版本，因此使用它的排序算法将成为分布式排序，等等。您的程序变得更健壮、更简单、更快。

你的例子是一个微不足道的例子：+已经接受了任意数量的参数，在很少的内存中快速运行，并且已经由编写你的编译器的人编写和调试过。这些属性通常不适用于我需要运行的算法。

于 2011-03-16T22:45:10.537 回答