通过替换折叠函数来消除显式递归

Question

通过替换折叠函数来消除显式递归

haskellrecursionfunctional-programmingrecursion-schemescomonad

3

我有这个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" 和 "application" 的显式递归，但我不确定应该选择哪种递归方案。哪些递归方案可用于消除此类和类似情况中的递归，并且你有没有好的方法来确定适用递归方案的情况？

- Ace shinigami

你可以总是（我认为）从一个F-代数中推导出类别论的卡塔莫菲斯。我写了一系列文章，其中包含多个示例，如果有帮助的话... - Mark Seemann

另外还有一个例子，请参见 https://dev59.com/V8Tra4cB1Zd3GeqP52Xy#72247301。 - Mark Seemann

@MarkSeemann 抱歉，我觉得我没有表达清楚我的问题。我的问题不是如何生成falgebra/catamorphism，而是在使用catamorphisms时仍然使用了显式递归。我的问题是是否有一种不同的递归方案可以让我避开这个问题？ - Ace shinigami

2个回答

2

延续 @li-yao-xia 的 evalSubsts 方法，让我们尝试在语言中添加 lambda 和应用。我们首先扩展 AST：

data AST
  ...
  | Lam Id AST
  | App AST AST

但是，我们如何在 evalSubst 中编写我们的 LamF 案例呢？

  go (LamF x e) s = ???

我们希望我们的lambda表达式是静态（词法）作用域，因此我们需要保留环境变量“s”，但是我们目前无法将环境应用于“e”，因为我们不知道“x”的值应该是什么。我们陷入了困境！

解决方法是要认识到，虽然AST是我们输入的一个很好的表示形式，但它并不适合输出。实际上，输入的Int和输出的Int恰好共享相同的结构有点巧合，对于lambda表达式，它们可能不应该如此。因此，我们可以创建一个新的输出表示形式：

data Val
  = IntV Int
  | LamV (Val -> Val)

type Sub = [(Id, Val)]

重点在于LamV是一个函数，而不仅仅是一些数据。有了这个，我们可以完成evalSubsts的定义：

evalSubsts :: AST -> Sub -> Val
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) _ = IntV n
  go (LamF x e) s = LamV $ \xVal -> e ((x, xVal) : s)
  go (AppF lam e) s =
    let (LamV f) = lam s in f (e s)
  go (PlusF e e') s =
    let (IntV n, IntV m) = (e s, e' s) in
    IntV (n + m)

- DDub

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Li-yao Xia · Accepted Answer

eval不能直接表示为范畴化函数，因为eval (Let x e e')将eval应用于subst(x, eval e) e'，而这不是Let x e e' (e或e')的子项。相反，考虑eval和替换的组合。如果您将替换subst推广到一次替换多个变量的情况下，可以得到以下等式：

(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的参数，您可以使用一个带有F-代数的cata，其中载体是一个函数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 理解为使用环境，将变量映射到值的求值器。因此，绑定变量而不是进行替换，只需在环境中插入其值，一旦到达 Var 节点，它就会被查找。