Motivation
In this question, a user asked whether it is possible to inline the following function:
-- simplified version
{-# INLINE nTimes #-}
nTimes :: Int -> (a -> a) -> a -> a
nTimes 0 f x = x
nTimes n f x = nTimes (n-1) f (f x)
Unfortunately, the answer seems no, since GHC sees a recursive function and gives up. Even if you use a compile-time constant, e.g. nTimes 1 (+1) x
, you don't end up with x + 1
, but with nTimes 1 (+1) x
.
While it's of course fine to refuse inlining if the number of loops is unknown, it's also a hassle if it is known.
Code
As you can see in the question above, I've proposed the following solution:
{-# LANGUAGE TemplateHaskell #-}
module Times where
import Control.Monad (when)
import Language.Haskell.TH
-- > item under review begins here
nTimesTH :: Int -> Q Exp
nTimesTH n = do
f <- newName "f"
x <- newName "x"
when (n <= 0) (reportWarning "nTimesTH: argument non-positive")
when (n >= 1000) (reportWarning "nTimesTH: argument large, can lead to memory exhaustion")
let go k | k <= 0 = VarE x
go k = AppE (VarE f) (go (k - 1))
return $ LamE [VarP f,VarP x] (go n)
-- < item under review ends here
This should, for any n
, create a function with patterns named f
and x
, and apply f
to x
with AppE
n
times:
$(nTimesTH 0) = \f x -> x
$(nTimesTH 1) = \f x -> f x
$(nTimesTH 2) = \f x -> f (f x)
$(nTimesTH 3) = \f x -> f (f (f x))
I can verify that the created function has the correct type:
$ ghci -XTemplateHaskell Times.sh
ghci> :t $(nTimesTH 0)
$(nTimesTH 0) :: r -> r1 -> r1
ghci> :t $(nTimesTH 1)
$(nTimesTH 1) :: (r1 -> r) -> r1 -> r
ghci> :t $(nTimesTH 2)
$(nTimesTH 2) :: (r -> r) -> r -> r
ghci> :t $(nTimesTH 3)
$(nTimesTH 3) :: (r -> r) -> r -> r
To all my knowledge, nTimesTH
works exactly as expected.
Given that this is my first time dabbling with Template Haskell, does this follow best practices? Also, I'm using VarE
, AppE
and so on. Language.Haskell.TH
also provides some combinators, so that one can write
let go k | k <= 0 = varE x
go k = appE (varE f) (go (k - 1))
lamE (map varP [f,x]) (go n)
Is this just personal preference, or is lamE
preferred? As far as I can see, the expression combinators use the canonic implementation, e.g. varE = return . VarE
, appE f x = liftA2 AppE f x
and so on.
Tests
Just for completeness the QuickCheck tests. Those aren't really part of the review, but here fore completeness:
module Times where
import Test.QuickCheck
-- .. rest of module as above
genTestSingle :: Int -> Q Exp
genTestSingle n = do
f <- newName "gTSf"
x <- newName "gTSx"
lamE [varP f, varP x] $
appsE [ [| (==) |], appsE [nTimesTH n, varE f, varE x]
, appsE [ [| nTimesFoldr n |], varE f, varE x]]
genAllTest :: Int -> Q Exp
genAllTest n = do
f <- newName "gATf"
x <- newName "gATv"
lamE [varP f, varP x] $ doE $ (flip map) [1..n] $ \i ->
noBindS $ appE [| quickCheck |] $ appsE [genTestSingle i, varE f, varE x]
module Main where
main = $(genAllTest 100) sin 40
nTimesTH n f x
with large valuesn
, iff
isn't inlineable orx
isn't also a compile-time constant. This will eat all your RAM. \$\endgroup\$go n
isiterate (AppE (VarE f)) (VarE x) !! max 0 n
. \$\endgroup\$