编写递归模板haskell函数

Question

是否可以将递归TH函数转换为将编译的等效形式？以下定义不起作用，因为要编译fact，您必须首先编译fact。

fact :: ExpQ -> ExpQ 
fact n = [| 
    case $n of 
     1 -> 1 
     _ -> $n * $(fact [| $n - 1 |]) |] 

这个简单的例子很容易解决（fact n = [| product [ 1.. $n] |]），但在一般情况下，如果它是不可能改写的给定功能作为一个循环，可以递归TH函数来定义？这是否有一个可行的例子？为了澄清未来的读者：这个问题是专门写关于递归 TH函数 - 而不是'如何拼接factorial函数'。

的回答我的问题竟然是非常简单的：

{-# 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 |]) |] 

Answer 1

与您的代码的根本问题不在于它是递归，但它不会终止。 fact的参数n只是越来越大，因为[| $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 
      |] 

最终，在你真正的代码，你将需要应用这些技术的一些组合 - 确保您的编译时递归终止，并以任何方式将任何剩余的案例推迟到运行时评估。

Answer 2

是的，你可以通过以下几点：

fact :: Int -> ExpQ 
fact 0 = [| 1 |] 
fact n = [| $(lift n) * $(fact $ n - 1) |] 

lift里面Language.Haskell.TH.Lift一个函数，它基本哈斯克尔值转换为模板哈斯克尔值（例如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])