在函数式语言中实际使用fold/reduce

Question

Fold(又名reduce)被认为是一个非常重要的高阶函数.Map可以表示fold(见这里).但这对我来说听起来比实际更具有学术性.典型的用途可能是获得总和,产品或数字的最大值,但这些函数通常接受任意数量的参数.那么为什么写的(fold + 0 '(2 3 5))时候(+ 2 3 5)工作正常.我的问题是,在什么情况下使用最简单或最自然fold？

Answer 1

关键fold是它更抽象.这并不是说你可以做你以前做过的事情,而是你可以更容易地做到.

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

由于fold(为此事,map,filter,和朋友)具有良好定义的行为,它往往更容易理解使用这些功能不是明确的递归码.

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

Answer 2

以下是一些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的解决方案.

另请参阅:reduce vs. apply

Answer 3

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

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

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

Answer 4

在Common Lisp函数中,不接受任何数量的参数.

每个Common Lisp实现CALL-ARGUMENTS-LIMIT都有一个常量,它必须是50或更大.

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

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

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