Haskell compile time function calculation

code-generation, compiler-construction, haskell, metaprogramming, static

Solution

You should use Template Haskell. With TH you can generate code programmatically, at compile time. Your mymodulus is effectively a "template" in this case.

For example, we can rewrite your program as follows, to compute your function statically. first, the main code as usual, but instead of calling your modulus 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 generate the table statically:

{-# 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, which will be generated at compile time. We simply generate a big switch:

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

You can see what code is generated with -ddump-splices. I've written the template code in direct style. Someone more familiar with TH should be able to make the pattern code simpler.

Another option would be to generate a table of values offline, and just import that data structure.

You might also say why you wish to do this. I assume you have a very complex table-driven function?

Problem

I would like to precalculate values for a function at compile-time. Example (real function is more complex, didn't try compiling): ``` 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 be called only with `n < 64` and I would like to precalculate `mymodulus` for `n` values of `0..64` at compile time. The reason is that `mymodulus` would be really expensive and will be reused multiple times.

Original source