Haskell compile-time function calculation

Question

I would like to pre-compute the values ​​for the function at compile time.

Example (real function is more complicated, did not try to compile):

base = 10 mymodulus n = n `mod` base -- or substitute with a function that takes -- too much to compute at runtime printmodules 0 = [mymodulus 0] printmodules z = (mymodulus z):(printmodules (z-1)) main = printmodules 64 

I know that mymodulus n will only be called with n < 64 , and I would like to pre-compute mymodulus for n values ​​of 0..64 at compile time. The reason is that mymodulus will be really expensive and will be reused repeatedly.

Answer 1

You must use Template Haskell . With TH, you can generate code programmatically at compile time. In this case, your mymodulus is actually a "template".

For example, we can rewrite your program as follows to compute your function statically. firstly, the main code, as usual, but instead of calling the module function, it calls a function whose body is a splice that will be generated at compile time:

 {-# LANGUAGE TemplateHaskell #-} import Table mymodulus n = $(genmodulus 64) main = mapM_ (print . mymodulus) [0..64] 

And the code to create the table is static:

 {-# LANGUAGE TemplateHaskell #-} module Table where import Language.Haskell.TH import Language.Haskell.TH.Syntax genmodulus :: Int -> Q Exp genmodulus n = return $ CaseE (VarE (mkName "n")) [ Match (LitP (IntegerL i)) (NormalB (LitE (IntegerL (i `mod` base)))) [] | i <- [0..fromIntegral n] ] where base = 10 

This describes the abstract syntax of the case expression that will be generated at compile time. We just generate a big switch:

  genmodulus 64 ======> case n of { 0 -> 0 1 -> 1 2 -> 2 3 -> 3 4 -> 4 ... 64 -> 4 } 

You can see which code is generated using -ddump-splice. I wrote the template code in a straightforward style. Someone more familiar with TH should be able to make the template code simpler.

Another option is to create a value table offline and simply import this data structure.

You can also say why you want to do this. I assume you have a very complex table driven function?

Answer 2

I don't know how to precompile it before searching the table (although you might be lucky with TH). An alternative is to create a runtime lookup table with something like

 mymodulus' x = lt ! x where lt = array (0, 64) [(i, mymodulus i) | i <- [0..64]] 

Answer 3

As I recall, there is a certain behavior associated with top-level definitions. If you try a simple example:

 primes = 2 : 3 : filter isPrime [5, 7 .. 1000000] isPrime x = walk (tail primes) where walk (y:ys) | (y*y > x) = True | (x `mod` y) /= 0 = walk ys walk _ = False main = do print $ last primes print . last $ init primes 

You will see that the first call (finishing touches) initiates the calculation of primes, and the second line will reuse these calculations.