编写递归模板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函数 - 而不是'如何拼接阶乘函数'.

我的问题的答案非常简单:

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

代码的根本问题不在于它是递归的,而是它不会终止.因为是一个表达树,表示应用于和的操作,因此不断变得越来越大的n论点.fact[| $n - 1 ]|(-)n1

任何非终止拼接都会以相同的方式挂起编译器,例如以下行为就像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
           |]

最终在您的实际代码中,您将需要应用这些技术的某些组合 - 确保您的编译时递归终止并将任何剩余的情况推迟到运行时评估.