haskell - 通过替换变态来消除显式递归

Question

我有这个 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

我觉得应该删除“let”和应用程序的显式递归，但我不确定我应该使用哪种递归方案。在这种情况和类似情况下，可以使用哪种递归方案来消除递归，您有什么好的方法来确定该递归方案适用的情况吗？

Answer 1

eval 不能直接表示为变态，因为 eval (Let x e e') 将 eval 应用于 subst (x , eval e) e'，它不是 Let x e e'(e 或 e')的子项。相反，请考虑 eval 和替换的组合。如果将替换 subst 概括为用 substs 一次替换多个变量，则可以得到以下等式:

(eval . substs s) (Let x e e')
= eval (Let x (substs s e) (substs s e'))
= (eval . subst (x, (eval . substs s) e) . substs s) e'

-- by (subst xe . substs s) = substs (xe : s)

= (eval . substs ((x, (eval . substs s) e) : s)) e'

我们确实有一个形式为 (eval . substs _) 的函数应用于子项 e 和 e'。为了说明 substs 的参数，您可以将 cata 与 F 代数一起使用，其中载体是函数 ASTF (Sub -> AST) -> Sub -> AST，然后您可以将不同的替换 Sub 传递给每个子项。

{-# LANGUAGE TemplateHaskell, TypeFamilies #-}

import Data.Functor.Foldable (cata)
import Data.Functor.Foldable.TH (makeBaseFunctor)
import Data.Maybe (fromJust)

type Id = String
data AST
  = Let Id AST AST
  | Var Id
  | Int Int
  | Plus AST AST

type Sub = [(Id, AST)]

makeBaseFunctor ''AST

evalSubsts :: AST -> Sub -> AST
evalSubsts = cata go where
  go (LetF x e e') s = e' ((x, e s) : s)
  go (VarF x) s = fromJust (lookup x s)
  go (IntF n) _ = Int n
  go (PlusF e e') s =
    let (Int n, Int m) = (e s, e' s) in
    Int (n + m)
  -- Or this:
  -- go (PlusF e e') = liftA2 plus e e'
  --   where plus (Int n) (Int m) = Int (n + m)

eval :: AST -> AST
eval e = evalSubsts e []

另一种理解 evalSubsts 的方式是作为使用环境的评估器，将变量映射到值。然后绑定(bind)一个变量，而不是做一个替换，只是将它的值插入环境中，一旦你到达 Var 节点就会被查找。