高阶函数foldl和foldr的实际例子是什么？ [英] What are practical examples of the higher-order functions foldl and foldr?

问题描述

典型的学术范例是总结一个清单。
是否有现实世界中使用fold的例子可以揭示它的用途？

解决方案

fold 可能是序列中最基本的操作。要求它的实用性就像在一个命令式语言中要求为循环使用一样。

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

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

  sum = fold（+）0 
 
 length = fold（λxn→1 + n ）0 
 
 reverse = fold（λxxs→xs ++ [x]）[] 
 
 map f = fold（λxys→fx：ys）[] 
 
 filter p = fold（λxxs→if px then x：xs else xs）[] 
  

fold操作符不是特定的列表，但可以统一的方式推广到'常规'数据类型。

所以，作为最基本的对各种数据类型的操作，它肯定有一些用处。能够识别何时可以将算法描述为折叠是一种有用的技巧，可以使代码变得更清晰。

---

参考文献：

• 关于折叠的普遍性和表达性的教程 用foldr书写foldl


• 折叠

The typical academic example is to sum a list. Are there real world examples of the use of fold that will shed light on its utility ?

解决方案

fold is perhaps the most fundamental operation on sequences. Asking for its utility is like asking for the utility of a for loop in an imperative language.

Given a list (or array, or tree, or ..), a starting value, and a function, the fold operator reduces the list to a single result. It is also the natural catamorphism (destructor) for lists.

Any operations that take a list as input, and produce an output after inspecting the elements of the list can be encoded as folds. E.g.

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) []

The fold operator is not specific to lists, but can be generalised in a uniform way to ‘regular’ datatypes.

So, as one of the most fundamental operations on a wide variety of data types, it certainly does have some use out there. Being able to recognize when an algorithm can be described as a fold is a useful skill that will lead to cleaner code.

---

References:

• A tutorial on the universality and expressiveness of fold
• Writing foldl in terms of foldr
• On folds

这篇关于高阶函数foldl和foldr的实际例子是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！