Haskell variant of template metaprogramming

Question

I'm new to Haskell. Given the whole premise of Haskell is that a function will always return the same value, I'd expect there to be some way of e.g. calculating fibonacci values of constants at compile time, like I can do in C++ with template metaprogrmming, but I can't see how to do it. Is there a way?

Answer 1

edit: Daniel Fischer points out that you can lift an ordinary expression into Template Haskell and evaluate the result at compile-time, subject to certain constraints on the output type, by having an ordinary function fib and then splicing

$(let x = fib 1000 in [|x|])

Original answer follows.

As pointed out in comments, Template Haskell is the way to go for this. For inductive functions like fibonacci, it's fairly straightforward. You write code similar to a standard definition, but returning an ExpQ value. Due to splicing restrictions, you'll need to use 2 modules.

{-# LANGUAGE TemplateHaskell #-} 
module TH where

import Language.Haskell.TH

fibTH :: Int -> ExpQ
fibTH 0 = [| 0 |]
fibTH 1 = [| 1 |]
fibTH n = [| $(fibTH (n-1)) + $(fibTH (n-2)) |]

and

{-# LANGUAGE TemplateHaskell #-}
module Main where

import TH

y :: Int
y = $(fibTH 10)

main = print y

To confirm that the work is performed at compile-time, we can compile with -ddump-simpl to see the core, which confirms it.

Main.y :: GHC.Types.Int
[GblId,
 Caf=NoCafRefs,
 Str=DmdType m,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=True,
         ConLike=True, WorkFree=False, Expandable=True,
         Guidance=IF_ARGS [] 10 20}]
Main.y = GHC.Types.I# 55

Answer 2

There's a great article by Don Stewart where he shows that using the LLVM backend with the right choice of flags will precompute certain functions at compile time and replace them with constants.