The fundamental problem with your code is not that it is recursive, but that it doesn't terminate. The n
argument to fact
just keeps getting bigger and bigger because [| $n - 1 ]|
is an expression tree representing the operation (-)
applied to n
and 1
.
Any non-terminating splice will hang the compiler in just the same way, for example the following behaves just like your fact
when spliced:
broken :: ExpQ -> ExpQ
broken n = return $ LitE (IntegerL (fromIntegral (length [1..])))
A recursive function where the recursion is guaranteed to bottom out is guaranteed to terminate and works fine for appropriate inputs:
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) |]
but of course it fails if the input isn't an appropriate integer literal.
You can also shift the recursion to runtime, so that instead of the recursive call being with an ever-bigger expression tree, it's with the runtime evaluated and shrinking Int
:
fact2 :: ExpQ -> ExpQ
fact2 n =
[|
let factImpl n =
case n of
1 -> 1
_ -> n * factImpl (n-1)
in factImpl $n
|]
Of course in this code we're not doing any analysis of the structure of n
. But we can put it together with fact1
to get a version that is compile-time executed in some cases and defers others to runtime:
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
|]
Ultimately in your real code, you will need to apply some combination of these techniques - make sure that your compile-time recursion terminates and defer any remaining cases to runtime evaluation somehow.