Haskell自定义Expr语法evalStep函数遇App(Var v)e2问题咨询

你遇到的App (Var v) e2情况，本质是当前evalStep的实现存在两个核心问题：缺少对应用表达式（App）的通用步进逻辑，以及部分分支的实现不符合单步求值的要求。

1. 为什么会出现这个情况？ #

当前你的evalStep只处理了App左边已经是Lambda的情况，完全没考虑左边是Var、BinaryOp等其他表达式的场景。当测试用例中出现App (Var v) e2时，代码会直接走到最后的error分支抛出异常，这显然不符合单步求值的预期逻辑。

另外，你的Lambda分支还有笔误：evalStep (Lambda argName argName argType body)重复了argName参数，这会导致编译错误，而且按照λ演算的常规定义，Lambda本身是值（无法再步进求值），不需要递归处理其body。

2. 修复后的关键分支实现 #

修复Lambda分支 #

Lambda作为值，直接返回自身即可：

evalStep (Lambda argName argType body) = Lambda argName argType body

添加App的通用步进逻辑 #

以传值调用策略为例（先求值函数，再求值参数，最后应用），需要分情况处理：

evalStep (App e1 e2) =
  case evalStep e1 of
    -- 如果函数部分还能步进，先步进函数
    e1' | e1' /= e1 -> App e1' e2
    -- 函数已经是值，检查是否是Lambda
    Lambda argName argType body ->
      case evalStep e2 of
        -- 参数还能步进，先步进参数
        e2' | e2' /= e2 -> App (Lambda argName argType body) e2'
        -- 参数已是值，执行替换
        _ -> substituteVar argName e2 body
    -- 函数是值但不是Lambda，抛出运行时错误
    val -> error $ "Cannot apply non-function value: " ++ show val

修复Let表达式的单步逻辑 #

当前的Let分支直接一次性完成替换，不符合单步求值的要求，应该先步进求值绑定的表达式，直到它变成值再替换：

evalStep (Let var e1 e2) =
  case evalStep e1 of
    e1' | e1' /= e1 -> Let var e1' e2
    _ -> substituteVar var e1 e2

3. 关于App (Var v) e2的后续处理 #

• 如果Var v是自由变量（未在任何上下文中绑定）：这属于运行时错误，因为你试图调用一个未绑定到函数的变量，此时上述修复后的代码会抛出明确的错误提示。
• 如果Var v是绑定变量但未被替换成Lambda：这说明你的绑定逻辑（比如Let或其他作用域处理）存在问题，需要检查substituteVar函数是否正确处理了变量替换，或者是否在单步求值过程中遗漏了绑定变量的替换时机。

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