以Haskell去重函数为例讲解Leftmost-Innermost与Outermost归约

归约本质是将函数调用（可约式Redex）替换为对应函数体、同时代入参数的过程，以下是两种常见归约策略的定义和执行示例：

基础概念 #

1. 最左最内（Leftmost-Innermost，值调用/严格求值） #

• 执行规则：每次优先归约最靠左、内部没有其他可约式的表达式，即先把所有参数完全求值为范式，再代入函数体执行
• 对应场景：严格求值语言的默认逻辑，Haskell中可通过严格标注!或seq函数强制触发该策略

2. 最外（Outermost，名调用/惰性求值） #

• 执行规则：每次优先归约最靠左、最外层的可约式，即先展开外层函数调用，参数仅在需要用到时才求值，未用到的参数直接丢弃
• 对应场景：Haskell默认的求值策略，实际实现中会通过Thunk共享避免重复计算

本次示例用到的函数定义如下：

removeone :: Eq a => a -> [ a ] -> [ a ]
removeone _ [] = [] 
removeone x ( y : ys ) 
   | x == y  =  removeone x ys
   | otherwise =  y : ( removeone x ys )

remdups :: Eq a => [ a ] -> [ a ]
remdups [] = []
remdups ( x : xs ) = x : remdups ( removeone x xs )

示例调用为：remdups [3,7,3,7,5,7]，预期输出为[3,7,5]

一、最左最内归约执行步骤 #

• 初始表达式：remdups [3,7,3,7,5,7]
• 参数已为范式，匹配remdups第二个分支展开：3 : remdups (removeone 3 [7,3,7,5,7])
• 优先归约最内层可约式removeone 3 [7,3,7,5,7]，完全求值后得到[7,7,5,7]，表达式变为：3 : remdups [7,7,5,7]
• 匹配remdups分支展开：3 : 7 : remdups (removeone 7 [7,5,7])
• 归约内层removeone 7 [7,5,7]得到[5]，表达式变为：3 : 7 : remdups [5]
• 匹配remdups分支展开：3 : 7 : 5 : remdups (removeone 5 [])
• 归约内层removeone 5 []得到[]，表达式变为：3 : 7 : 5 : remdups []
• 匹配remdups空列表分支返回[]，最终结果为[3,7,5]

二、最外归约执行步骤 #

• 初始表达式：remdups [3,7,3,7,5,7]
• 优先归约最外层可约式remdups，匹配分支展开：3 : remdups (removeone 3 [7,3,7,5,7])
• 现在最外层可约式为remdups (removeone 3 [7,3,7,5,7])，需要先确定参数是否为空，因此对removeone部分求值到弱首范式：7 : removeone 3 [3,7,5,7]，确认参数非空后展开remdups，表达式变为：3 : 7 : remdups (removeone 7 (removeone 3 [3,7,5,7]))
• 继续处理最外层的remdups调用，对参数部分求值直到得到弱首范式5 : removeone 7 (removeone 3 [7])，确认非空后展开remdups，表达式变为：3 : 7 : 5 : remdups (removeone 5 (removeone 7 (removeone 3 [7])))
• 继续处理最外层的remdups调用，对参数完全求值得到[]，匹配空列表分支返回[]，最终结果为[3,7,5]

两种策略的核心差异 #

• 最左最内策略提前完成所有参数求值，无重复计算开销，但如果参数未被函数用到会产生无用计算
• 最外策略按需求值参数，避免无用计算，但如果参数被多次引用会有重复计算风险，Haskell的Thunk共享机制解决了该问题

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