如何用foldr实现foldl（从左折叠）？

首先需要纠正你提供的foldl实现中的两个问题：

1. 递归调用时错误传入原列表lst而非剩余列表tl，这会导致无限循环；
2. 函数f的参数顺序不符合标准foldl的左结合逻辑（标准foldl是累积值与当前元素结合，即f acc hd而非f hd acc）。

正确的基础foldl实现应为：

let rec foldl f lst acc = match lst with
  | [] -> acc
  | hd::tl -> foldl f tl (f acc hd)

核心思路 #

foldl是左结合的累积操作（计算顺序为((acc0 f x1) f x2) f x3），而foldr是右结合（计算顺序为x1 f (x2 f (x3 f acc0))）。要通过foldr模拟foldl，需要让foldr构建一个函数链，最终将初始累积值按左结合顺序传入执行。

具体实现代码 #

let foldl_via_foldr f lst acc =
  let rec foldr f lst acc = match lst with 
    | [] -> acc
    | hd::tl -> f hd (foldr f tl acc)
  in
  foldr (fun x g -> fun a -> g (f a x)) lst (fun x -> x) acc

代码解释 #

• foldr遍历每个元素x时，会生成一个包装函数：它接受累积值a，先执行foldl的核心操作f a x（累积值与当前元素结合），再将结果传递给下一个函数g；
• foldr的初始累积值是恒等函数fun x -> x，用于终止函数链；
• 最后传入初始累积值acc，函数链会按((acc f x1) f x2) f x3的左结合顺序执行，完全模拟foldl的行为。

验证示例 #

以减法操作(-)为例：

• 标准foldl (-) [1;2;3] 0的结果为((0-1)-2)-3 = -6；
• 用foldl_via_foldr (-) [1;2;3] 0计算时，foldr会生成函数fun a -> ((a-1)-2)-3，传入0后得到同样的-6，符合预期。

内容的提问来源于stack exchange，提问作者J.B