移除AST求值中let与Application的显式递归：适用递归方案及识别方法

我定义了如下AST数据结构：

data AST = Integer Int
         | Let String AST AST
         | Plus AST AST
         | Minus AST AST
         | Times AST AST
         | Variable String
         | Boolean Bool
         | If AST AST AST
         | Lambda String AST Type Type
         | Application AST AST
         | And AST AST
         | Or AST AST
         | Quot AST AST
         | Rem AST AST
         | Negate AST
         | Eq AST AST
         | Leq AST AST
         | Geq AST AST
         | Neq AST AST
         | Lt AST AST
         | Gt AST AST

以及如下求值代码：

eval :: AST -> AST
eval = cata go where
    go :: ASTF (AST) -> AST
    go (LetF var e e') = eval $ substVar (var, e) e'
    go (PlusF (Integer n) (Integer m)) = Integer (n + m)
    go (MinusF (Integer n) (Integer m)) = Integer (n - m)
    go (TimesF (Integer n) (Integer m)) = Integer (n * m)
    go (QuotF (Integer n) (Integer m)) = Integer (quot n m)
    go (RemF (Integer n) (Integer m)) = Integer (rem n m)
    go (IfF (Boolean b) e e') = if b then e else e'
    go (ApplicationF (Lambda var e _ _) e') = eval $ substVar (var, e') e
    go (AndF (Boolean b) (Boolean b')) = Boolean (b && b')
    go (OrF (Boolean b) (Boolean b')) = Boolean (b || b')
    go (NegateF (Boolean b)) = Boolean (not b)
    go (EqF e e') = Boolean (e == e')
    go (NeqF e e') = Boolean (e /= e')
    go (LeqF (Integer n) (Integer m)) = Boolean (n <= m)
    go (GeqF (Integer n) (Integer m)) = Boolean (n >= m)
    go (LtF (Integer n) (Integer m)) = Boolean (n < m)
    go (GtF (Integer n) (Integer m)) = Boolean (n > m)
    go astf = embed astf

目前我使用catamorphism（cata）实现求值逻辑，但Let和Application分支仍存在显式调用eval的递归。我希望移除这些显式递归，但不确定应选用哪种递归方案。请问此类场景适用哪些递归方案？以及如何识别适用该方案的场景？

适用的递归方案 #

1. 动态态射（Dynamorphism） #

这是最适配你当前场景的方案。它把结构展开（生成新AST）和折叠求值结合在一起，完美匹配Let和Application的处理逻辑：先通过substVar完成变量替换得到新AST，再自动对这个新AST执行求值流程，完全不需要显式调用eval。

2. 参数态射（Paramorphism） #

它是catamorphism的扩展，不仅能拿到子节点的求值结果，还能访问子节点的原始AST结构。如果你的变量替换逻辑需要用到原始节点的信息，可以考虑用它，但相比之下dynamorphism更直接对应“生成新结构再求值”的核心需求。

3. 单子化Catamorphism #

如果把求值逻辑包装成单子（比如Identity或State），也能通过monadic cata隐式处理递归，但这种方式相对繁琐，不如前两种方案直接高效。

Dynamorphism实现思路示例

Dynamorphism的核心是让函数先处理当前节点生成新结构，再自动递归处理新结构。伪代码示意如下：

eval = dynamo go where
    go (LetF var e e') = substVar (var, e) e'  -- 返回替换后的新AST，dynamo自动递归求值
    go (ApplicationF (Lambda var e _ _) e') = substVar (var, e') e
    -- 其他分支逻辑和原go函数完全一致

这样就彻底移除了显式的eval调用，递归流程由dynamorphism接管。

如何识别适用场景 #

可以通过以下特征判断是否需要这类递归方案：

• 处理节点时需要生成新的递归结构，并对新结构重复求值：比如你这里的变量替换，替换后得到全新的AST，需要重新走一遍完整的求值流程，而非基于已求值的子节点直接计算结果。
• Catamorphism的固定顺序无法满足需求：Catamorphism是先求值所有子节点，再处理当前节点的固定流程，但你的场景中，当前节点的处理结果是新的AST，需要再次启动整个求值逻辑，这种动态递归是catamorphism覆盖不到的。
• 存在“变换-求值”的循环逻辑：先对结构做变换（如变量替换），再对变换后的结构求值，这种模式就是dynamorphism的典型应用场景。

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