Написание рекурсивных шаблонов 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 ]| представляет собой дерево выражений, представляющее операцию (-), применяемую к 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, которая преобразует основные значения 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])