編寫遞歸模板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])