在模板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_

贷记给user2407038，他在评论中回答了该问题。

一般模式是使用附加的let构造：

recursive = let recursive_ = expression in recursive_

所以您可以在recursive_中引用expression。