Haskell中使用foldr实现map函数的两种方式原理解析请求

嘿，作为Haskell和foldr的新手，刚接触这种写法确实容易绕晕，咱们一步步拆解，保证你能搞明白！

foldr的本质是从右往左“折叠”列表，它的基本结构是：

foldr step_function base_case list

• list是要处理的目标列表
• base_case是列表为空时直接返回的默认值
• step_function是一个需要两个参数的函数：第一个是列表里的当前元素，第二个是“列表剩余部分折叠后的结果”

举个简单的例子，用foldr实现求和：

sum' = foldr (+) 0

处理[1,2,3]的时候，foldr会展开成：
1 + (2 + (3 + 0))
是不是很好理解？从最后一个元素开始，一步步往前合并计算。

先看这个lambda表达式\x xs -> f x : xs，它就是foldr需要的step_function：

• x是当前正在处理的列表元素
• xs是列表后面所有元素已经通过map转换后的结果

咱们拿具体例子走一遍，比如map'' (+1) [1,2,3]：

1. 先处理最后一个元素3：此时xs是base_case的[]，计算(+1)3 : [] → [4]
2. 接着处理元素2：此时xs是刚才得到的[4]，计算(+1)2 : [4] → [3,4]
3. 最后处理元素1：此时xs是[3,4]，计算(+1)1 : [3,4] → [2,3,4]
   这完全就是map (+1) [1,2,3]的结果，对吧？

这个lambda干的事情就是：把当前元素用f转换后，加到“已经处理好的后续列表”前面。

这里的((:) . f)是Haskell的函数组合，用.把两个函数拼起来。先回忆函数组合的规则：(g . f) x = g (f x)，意思是先把x传给f，再把结果传给g。

那(:) . f具体是什么呢？

• (:)的类型是b -> [b] -> [b]，它是一个“接受一个b类型元素，返回一个新函数（这个新函数接受[b]列表，返回添加了该元素的新列表）”的函数
• f的类型是a -> b，负责把a类型的元素转成b类型

所以(:) . f的作用就是：先把元素x用f转换成b类型，再把这个结果传给(:)，得到一个新函数——这个新函数接受列表xs，返回f x : xs！

换句话说：

((:) . f) x xs = f x : xs

这和第二种实现里的lambda\x xs -> f x : xs完全等价！

还是用刚才的例子，map' (+1) [1,2,3]：

1. 处理3时，((:) . (+1)) 3等于(:) 4，这个函数接受[]就变成[4]
2. 处理2时，((:) . (+1)) 2等于(:) 3，接受[4]变成[3,4]
3. 处理1时，((:) . (+1)) 1等于(:) 2，接受[3,4]变成[2,3,4]
   和第二种实现的结果完全一样，只是写法更简洁了。

foldr的定义里明确规定：当输入的列表是空列表[]时，直接返回base_case参数。

比如你调用map' f []，就等于foldr ((:) . f) [] []，此时直接返回base_case的[]；调用map'' f []也是一样，直接返回[]——这完全符合map的预期：空列表映射后还是空列表。

• 两种map的实现本质完全相同，只是写法不同：第一种用函数组合.简化了代码，第二种用显式的lambda把逻辑写得更直白
• foldr处理列表时，从最后一个元素开始，把每个元素转换后加到“已处理的后续列表”前面，遇到空列表就返回初始的[]

内容的提问来源于stack exchange，提问作者Big geez