Haskell中基于foldr实现的map'函数语法含义解析

首先明确foldr的核心逻辑：它从列表的末尾向左折叠，接受三个参数：

• 一个二元函数(a -> b -> b)：第一个参数是原列表的当前元素，第二个参数是折叠剩余列表得到的结果，返回新的折叠结果
• 初始值b：处理空列表时返回的结果
• 要折叠的列表[a]

回到你的代码：

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\y ys -> (f y):ys) [] xs

拆解lambda函数(\y ys -> (f y):ys) #

这里的两个参数：

• y：是原列表xs的当前元素，不是你理解的ys的元素
• ys：是foldr处理xs中y之后的剩余子列表得到的结果——也就是已经通过map' f转换完成的子列表

这个lambda的作用很直接：把函数f应用在当前元素y上得到f y，再把这个结果放在已转换好的子列表ys的前面，生成新的列表。

用实际例子帮你梳理执行过程 #

比如调用map' (+1) [1,2,3]，展开foldr的执行步骤：

foldr (\y ys -> (y+1):ys) [] [1,2,3]
-- 先递归处理[2,3]，再处理第一个元素1
= (1+1) : foldr (\y ys -> (y+1):ys) [] [2,3]
-- 递归处理[3]，再处理元素2
= 2 : ( (2+1) : foldr (\y ys -> (y+1):ys) [] [3] )
-- 递归处理空列表，再处理元素3
= 2 : 3 : ( (3+1) : foldr (\y ys -> (y+1):ys) [] [] )
-- 空列表返回初始值[]
= 2 : 3 : 4 : []
= [2,3,4]

纠正你的理解错误 #

你之前认为y是ys的第一个元素，这混淆了两个参数的来源：

• y始终来自原输入列表xs，是还未被转换的原始元素
• ys是已经完成转换的子列表，它是foldr递归处理剩余列表后得到的最终结果，和原输入的剩余子列表不是同一个对象

内容的提问来源于stack exchange，提问作者Mean. Ah