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

Question

典型的学术示例是总结一个列表.是否有现实世界中使用折叠的例子可以阐明其实用性？

Answer 1

fold也许是序列上最基本的操作.要求它的实用性就像for在命令式语言中要求循环的效用.

给定列表(或数组,或树,或......),起始值和函数,fold运算符将列表缩减为单个结果.它也是列表的自然catamorphism(析构函数).

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

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

折叠运算符不是列表的特定,但可以统一的方式推广到"常规"数据类型.

因此,作为各种数据类型上最基本的操作之一,它肯定有一些用处.能够识别算法何时可以被描述为折叠是一种有用的技能,将导致更清晰的代码.

参考文献:

• 关于折叠的普遍性和表现力的教程
• 根据foldr编写foldl
• 折叠