#StackBounty: #haskell #template-meta-programming Execute a function n times, where n is known at compile time

Bounty: 50

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


Get this bounty!!!

Leave a Reply