理解foldl的归约过程：leftmost outermost求值策略应用疑问

核心概念说明 #

首先明确你提到的几个求值策略定义：

• innermost（最内层求值）：优先归约最内层、最右侧的可约表达式，每次先把参数完全计算完成后再代入函数
• outermost（最外层求值）：优先归约最外层、最左侧的可约表达式，先代入函数定义再按需计算参数，你提到的leftmost outermost就是Haskell默认采用的惰性求值策略，也叫按需调用。

本次涉及的代码定义 #

foldl的类型签名与实现如下：

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ e [] = e
foldl f e (x:xs) = foldl f (f e x) xs

需要归约的调用表达式为：

foldl (\acc x -> acc ++ [negate x]) [] [5,2,1]

完整归约过程（按leftmost outermost规则执行） #

按照Haskell默认的惰性求值规则，每一步会优先归约最左侧最外层的foldl调用，不会提前计算累积的函数参数，过程如下：

1. 初始表达式匹配foldl第三个参数非空的分支，x=5，xs=[2,1]，展开后得到：

   foldl (\acc x -> acc ++ [negate x]) ((\acc x -> acc ++ [negate x]) [] 5) [2,1]
   

2. 继续匹配非空分支，x=2，xs=[1]，展开后得到：

   foldl (\acc x -> acc ++ [negate x]) ((\acc x -> acc ++ [negate x]) ((\acc x -> acc ++ [negate x]) [] 5) 2) [1]
   

3. 继续匹配非空分支，x=1，xs=[]，展开后得到：

   foldl (\acc x -> acc ++ [negate x]) ((\acc x -> acc ++ [negate x]) ((\acc x -> acc ++ [negate x]) ((\acc x -> acc ++ [negate x]) [] 5) 2) 1) []
   

4. 此时第三个参数为空，匹配foldl的第一个分支，直接返回累积的thunk（未计算的表达式），开始从最内层依次计算：
   • 第一步计算最内层lambda调用：(\acc x -> acc ++ [negate x]) [] 5 = [] ++ [-5] = [-5]
   • 代入后计算上一层：(\acc x -> acc ++ [negate x]) [-5] 2 = [-5] ++ [-2] = [-5,-2]
   • 再代入计算最外层：(\acc x -> acc ++ [negate x]) [-5,-2] 1 = [-5,-2] ++ [-1] = [-5,-2,-1]

最终归约结果为[-5,-2,-1]。

补充说明 #

如果采用innermost策略求值，每一步展开foldl前会先计算括号内的f e x结果，归约过程会更短，但不符合Haskell默认的求值逻辑。

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