编写递归模板haskell函数
是否可以将递归TH函数转换为将编译的等效形式？以下定义不起作用，因为要编译fact，首先必须编译fact。
fact :: ExpQ -> ExpQ
fact n = [|
case $n of
1 -> 1
_ -> $n * $(fact [| $n - 1 |]) |]这个简单的例子很容易解决(fact n = [| product [ 1.. $n] |])，但是在一般情况下，如果不能将给定的函数重写为循环，那么可以定义递归的TH函数吗？有没有一个例子可以这样做呢？
为了向未来的读者澄清:这个问题是专门关于编写递归的TH函数的，而不是关于‘我如何拼接阶乘函数’。
我的问题的答案非常简单：
{-# LANGUAGE TemplateHaskell #-}
import Control.Monad.Fix (fix)
import Language.Haskell.TH
fact = [| \f x -> $([|
case x of
1 -> 1
_ -> f $([| x - 1 |]) * x |]) |]
factorial = [| fix $fact |]可以编译fact，因为它不再是递归的，而[| fix $fact |]是在以后编译的，因此不再有无限的递归定义。
此版本的fact看起来与原始版本略有不同，但您可以编写与旧版本完全相同的新fact，并在以后进行转换：
fact' recurse n = [|
case $n of
1 -> 1
_ -> $n * $(recurse [| $n - 1 |]) |]
fact = [| \x -> $((\f -> [| \x -> $(fact (\x -> [| $f $x |]) [| x |]) |]) [| x |]) |]回答 2
Stack Overflow用户
发布于 2014-01-14 14:27:21
代码的根本问题不是它是递归的，而是它没有终止。n参数对fact的作用越来越大，因为[| $n - 1 ]|是一个表达式树，表示应用于n和1的(-)操作。
任何不终止的拼接都会以同样的方式挂起编译器，例如，在拼接时，下面的行为就像您的fact一样：
broken :: ExpQ -> ExpQ
broken n = return $ LitE (IntegerL (fromIntegral (length [1..])))保证递归从下到下的递归函数保证终止，并对适当的输入工作良好：
fact1 :: ExpQ -> ExpQ
fact1 n = do
nBody <- n
case nBody of
LitE (IntegerL 1) -> [|1|]
LitE (IntegerL nInt) | nInt > 1 ->
let nMinusOne = return $ LitE (IntegerL (nInt-1))
in [| $n * $(fact1 nMinusOne) |]但是，当然，如果输入不是适当的整数文字，它就会失败。
您还可以将递归转移到运行时，这样就不用使用更大的表达式树来进行递归调用，而是使用运行时计算和收缩Int。
fact2 :: ExpQ -> ExpQ
fact2 n =
[|
let factImpl n =
case n of
1 -> 1
_ -> n * factImpl (n-1)
in factImpl $n
|]当然，在这段代码中，我们没有对n的结构进行任何分析。但是，我们可以将它与fact1放在一起，以获得在某些情况下执行的编译时版本，并将其他版本推迟到运行时：
fact3 :: ExpQ -> ExpQ
fact3 n = do
nBody <- n
case nBody of
LitE (IntegerL 1) -> [|1|]
LitE (IntegerL nInt) ->
let nMinusOne = return $ LitE (IntegerL (nInt-1))
in [| $n * $(fact3 nMinusOne) |]
_ -> [|
let factImpl n =
case n of
1 -> 1
_ -> n * factImpl (n-1)
in factImpl $n
|]最终，在真正的代码中，您将需要应用这些技术的一些组合--确保编译时递归终止，并以某种方式将剩余的任何情况推迟到运行时评估。
Stack Overflow用户
发布于 2014-01-14 15:35:50
是的，您可以使用以下方法：
fact :: Int -> ExpQ
fact 0 = [| 1 |]
fact n = [| $(lift n) * $(fact $ n - 1) |]lift是Language.Haskell.TH.Lift中的一个函数，它将基本的haskell值转换为模板haskell值(如Int到ExpQ)。
请注意，您不需要生成案例代码，因为您知道编译时的编号。上述宏将扩展到一系列乘法。$(fact 4)将扩展到4*3*2*1。
请注意，在本例中，您可以做得更好。模板haskell表达式在编译时运行，因此模板haskell fact函数可以只返回它表示的文字值。例如$(fact 4)可以返回24 (而不是4*3*2*1)。这可以通过以下代码来完成：
fact2 :: Int -> ExpQ
fact2 n = lift (product [1..n])https://stackoverflow.com/questions/21125220
复制
![递归函数[通俗易懂]](https://ask.qcloudimg.com/http-save/yehe-8223537/3fcf1eb540f34848140ce229d6a1a1cc.gif)
相似问题
用haskell编写递归inRange函数
如何在haskell中编写递归函数
如何编写这个递归的Haskell函数？
在模板Haskell中定义递归函数
如何编写可变模板递归函数？
领取专属 10元无门槛券
AI混元助手 在线答疑
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
