functional-programming - 高阶函数 foldl 和 foldr 的实际例子是什么？

Question

典型的学术例子是总结一个列表。是否有使用 fold 的真实世界示例来说明其效用？

Answer 1

fold可能是序列上最基本的操作。询问它的实用性就像询问for命令式语言中循环的实用性。

给定一个列表（或数组、树或..）、一个起始值和一个函数，fold运算符将列表简化为单个结果。它也是列表的自然变形（析构函数）。

任何将列表作为输入并在检查列表元素后产生输出的操作都可以编码为折叠。例如

sum      = fold (+) 0

length   = fold (λx n → 1 + n) 0

reverse  = fold (λx xs → xs ++ [x]) []

map f    = fold (λx ys → f x : ys) []

filter p = fold (λx xs → if p x then x : xs else xs) []

折叠运算符不是列表特有的，但可以以统一的方式推广到“常规”数据类型。

因此，作为对多种数据类型的最基本操作之一，它确实有一些用处。能够识别何时可以将算法描述为折叠是一项有用的技能，它将导致代码更清晰。

---

参考：

• fold 的通用性和表现力教程
• 用 foldr 写 foldl
• 在折叠处

Answer 2

很多 foldLeft 示例列出了以下函数：

• 和
• 产品
• 数数
• 平均的
• 最后的
• 倒数第二
• 包含
• 得到
• 串起来
• 逆转
• 独特
• 设置
• 双倍的
• 插入排序
• 枢轴（快速排序的一部分）
• 编码（计算连续元素）
• 解码（生成连续元素）
• 组（成偶数大小的子列表）

Answer 3

我蹩脚的答案是：

• foldr用于将问题减少到原始情况，然后重新组装（表现为非尾递归）
• foldl用于减少问题并在每一步组装解决方案，在原始情况下，您已经准备好解决方案（作为尾递归/迭代）

这个问题立即让我想起了 Ralf Lämmel Going Bananas的一次演讲（因为 rfold 运算符符号看起来像香蕉（| 和 |））。将递归映射到折叠甚至一个折叠到另一个折叠有很多说明性的例子。

经典论文（一开始很难）是使用香蕉的函数式编程，镜头，。以其他操作员的外观命名的信封和铁丝网。