Haskell实现addAll：foldr合并表达式列表的错误排查

任务说明 #

定义addAll函数，将表达式列表合并为单个无冗余的表达式，要求使用foldr实现列表归约。

数据定义与错误代码 #

data Expr
  = Op BinOp Expr Expr
  | NumLit Int
  | ExpX Int
  deriving (Eq, Show)

data BinOp = AddOp | MulOp
  deriving (Eq, Show)

addAll :: [Expr] -> Expr
addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty
 where
    empty = NumLit 3

编译错误信息 #

src/Simplify.hs:31:16: error: [GHC-83865]
• 无法匹配预期类型‘Expr’与实际类型‘t0 (t1 a0) -> t1 a0’
• 可能原因：‘foldr’参数不足
在表达式：foldr (\ x acc -> if null acc then x else add x acc) empty中
在‘addAll’的定义中：
addAll exprs
= foldr (\ x acc -> if null acc then x else add x acc) empty
where
empty = NumLit 3
|
31 | addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

src/Simplify.hs:31:56: error: [GHC-83865]
• 无法匹配预期类型‘t1 a0’与实际类型‘Expr’
• 在表达式：add x acc中
在表达式：if null acc then x else add x acc中
在‘foldr’的第一个参数中，即‘(\ x acc -> if null acc then x else add x acc)’
• 相关绑定：
acc :: t1 a0（绑定于src/Simplify.hs:31:25）
x :: t1 a0（绑定于src/Simplify.hs:31:23）
|
31 | addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty
| ^^^^^^^^^

终端输出：
Error: [Cabal-7125]
Failed to build Simplify-0.1.0.0 (which is required by exe:mark from Simplify-0.1.0.0 and test:SimplifyTest from Simplify-0.1.0.0).

错误分析与修正方案 #

错误点解析 #

1. foldr参数缺失：foldr的类型是(a -> b -> b) -> b -> [a] -> b，必须传入三个参数：归约函数、初始值、待归约列表。原代码漏传了exprs，导致GHC无法推导正确类型。
2. 错误使用null：null仅适用于列表类型，但acc是Expr类型，无法用null判断。foldr会自动处理空列表场景，直接使用初始值即可。
3. 未定义add函数：原代码中调用的add函数不存在，需要用Op AddOp构造加法表达式，同时实现无冗余逻辑（比如合并数值字面量、跳过0值等）。

修正后的代码 #

data Expr
  = Op BinOp Expr Expr
  | NumLit Int
  | ExpX Int
  deriving (Eq, Show)

data BinOp = AddOp | MulOp
  deriving (Eq, Show)

addAll :: [Expr] -> Expr
addAll = foldr addExpr (NumLit 0)
  where
    -- 无冗余加法：合并数值、跳过0值
    addExpr :: Expr -> Expr -> Expr
    addExpr (NumLit 0) acc = acc
    addExpr x (NumLit 0) = x
    addExpr (NumLit a) (NumLit b) = NumLit (a + b)
    addExpr x acc = Op AddOp x acc

代码说明 #

• 使用foldr addExpr (NumLit 0)完成归约，初始值设为NumLit 0（加法单位元，不影响结果）。
• addExpr函数实现无冗余逻辑：
  • 如果其中一个操作数是NumLit 0，直接返回另一个操作数；
  • 如果两个都是数值字面量，直接相加合并为一个NumLit；
  • 其他情况用Op AddOp构造加法表达式。

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