在模板 Haskell 中定义递归函数

Question

我想为（最初很简单的）ADT 实现通用递归运算符。（简单意味着仅使用其参数类型为已定义类型的构造函数。）总体思路是能够使用像 $(recop ''Alg) 这样简单的东西。手动记下给定类型的递归运算符很容易。

data D = E | C D D

recD :: t -> ((D, t) -> (D, t) -> t) -> D -> t
recD rE rC = let r = recD rE rC in \case
    E         -> rE
    C pC0 pC1 -> rC (pC0, r pC0) (pC1, r pC1)

我想为此使用模板。我的问题是递归调用，例如r pC0。我没有递归调用就让它工作了。

newNames :: String -> Int -> Q [Name]
newNames stem n = sequence [ newName (stem ++ show i) | i <- [1::Int .. n] ]
match' :: PatQ -> ExpQ -> MatchQ
match' pat exp = match pat (normalB exp) []

recop :: Name -> ExpQ
recop name = do
    TyConI (DataD _ algName [] {-_-} ctors _) <- reify name
    let ctorNames = [ ctorName | NormalC ctorName _ <- ctors ] :: [Name]
    let ctorTypes = [ [ typ | (_, typ) <- bts ] | NormalC _ bts <- ctors ] 
    rs <- newNames ("r" ++ nameBase algName) (length ctorNames)
    pss <- sequence [ newNames ("p" ++ nameBase algName ++ nameBase ctorName) (length ctorTypes) | (ctorName, ctorTypes) <- zip ctorNames ctorTypes ]
    let pats = zipWith conP ctorNames (map varP <$> pss) :: [PatQ]
    let prs = zipWith (\p r -> tupE [varE p, r]) ps "recursive calls"
    lamE (varP <$> rs) $ lamCaseE [ match' pat $ foldl appE (varE r) prs | (r, pat, ps) <- zip3 rs pats pss ]

我不知道如何填补 "recursive calls" 的洞。我不知道并怀疑这不容易做到。

Answer 1

您的操作方式与您在具体代码中的操作方式完全相同；您生成 let r = .. in .. 并引用 r 来构造递归调用。现在，您只是在构建 \case { .. } 部分。请记住，您可以将 recD 重写为

recD =
  let
    recD_ = \rE rC ->
      let r = recD_ rE rC
      in ...
  in recD_

感谢在评论中回答问题的用户 2407038。

一般模式是使用额外的 let 构造：

recursive = let recursive_ = expression in recursive_

所以你可以参考expression中的recursive_。

在模板 Haskell 中定义递归函数

Define a Recursive Function in Template Haskell

recursion

haskell

template-haskell