The Zen of Python teaches us that "there should be one-- and preferably only one --obvious way to do it." Yeah, so this one definitely doesn't apply to Haskell, where we typically have many approaches to any given problem, with fervent proponents of each. Such is the nature of a language that has its roots in academia: we try various things and see which ones work best.

That's why you are about to see not one, not two, but three ways to do compile-time evaluation in Haskell (there may be more, but let's not get too esoteric).

To get started, we will need a computationally expensive function to use as our example. As everybody probably knows by now, the primary use case for Haskell is to compute Fibonacci numbers (or is it factorial?), so let's stick to tradition. Here's a terribly slow implementation of fib:

fib :: Natural -> Natural
fib 0 = 0
fib 1 = 1
fib k = fib (k - 2) + fib (k - 1)

main = print (fib 42)

When compiled with -O2, this program runs for about 10 seconds on my machine before it prints the answer, which is 267914296. The reason it takes so long is that there's a lot of redundant recomputation, and the intermediate results are not memoized. Just what we need to see how well GHC can do the same thing at compile time.

Template Haskell

Haskell has extremely powerful metaprogramming facilities in the form of Template Haskell. While not particularly ergonomic, it gets the job done and provides the ability to execute arbitrary code at compile time.

The idea behind Template Haskell is to write programs that generate other programs, represented by their abstract syntax tree (AST). Since our use case is simple, there are only two moving parts we need to understand:

1. A value can be converted to the corresponding AST by using the lift function
2. The resulting AST can be inserted into our program using a splice, denoted $(...)

Basically, it's a matter of replacing fib 42 with $(lift (fib 42)). Unfortunately, when we try to do this, we see the following error:

EvalWithTemplateHaskell.hs:13:22: error:
• GHC stage restriction:
    'fib' is used in a top-level splice, quasi-quote, or annotation,
    and must be imported, not defined locally
• In the untyped splice: $(lift (fib 42))

Fortunately, this is easy (although annoying) to fix. If we move the definition of fib into a separate module, it can be used in a splice without any issues:

main = print $(lift (fib 42))

Now building this program takes 10 seconds, but at runtime it prints the result instantly. That's because at splice time (when Template Haskell is executed), it was converted to this:

main = print 267914296

Type families

A completely different approach is to use type-level programming. Let's rewrite fib as a closed type family:

type family Fib n where
  Fib 0 = 0
  Fib 1 = 1
  Fib k = Fib (k - 2) + Fib (k - 1)

Here we also make use of the DataKinds extension to work with type-level numbers. Now we can get the result we want in the type of a value. For example:

ghci> fib21 = Proxy :: Proxy (Fib 21)
ghci> :t fib21
fib21 :: Proxy 10946

Unfortunately, when I tried this with Fib 42, GHCi consumed all my RAM and died. In any case, we're not done here: we are supposed to get an executable that prints the result. That's where the KnownNat class and its method natVal come into play.

main = print (natVal (Proxy @(Fib 42)))

Interestingly, this time it compiled very quickly, using very little memory. I even got it to compute Fib 202100, which is a number with over 40 thousand digits. Clearly, there's some sort of reduction cache involved, as otherwise our naive implementation would have taken forever.

So we went from an out-of-memory crash to an automatic asymptotic improvement... by doing something entirely unrelated to the type family itself. Oh my, type checking performance is flaky. I wish we had a good cost model for type-level features, but currently getting the compile times lower is a dark art.

That said, we did end up with a much better result than we had with Template Haskell :-)

Functional dependencies

Type families aren't the only way to trick the type checker into performing computation for you. There are also functional dependencies. Their primary use case is to improve type inference for multi-parameter type classes, but there's no limit to the ingenuity with which programmers abuse their compiler, so here we go.

class Fib (n :: Nat) (r :: Nat) | n -> r
instance Fib 0 0
instance Fib 1 1
instance {-# OVERLAPPABLE #-}
  ( Fib (k - 1) f1,
    Fib (k - 2) f2,
    EQUALS r (f1 + f2) ) => Fib k r

And here are a few supporting definitions:

class EQUALS (a :: Nat) (b :: Nat) | a -> b, b -> a
instance EQUALS a a

fibVal :: forall n r. (KnownNat r, Fib n r) => Proxy n -> Natural
fibVal Proxy = natVal (Proxy @r)

This time Fib is neither a function nor a type family, but a multi-parameter type class! Its first parameter n is the input, its second parameter r is the output, and this is established by the functional dependency n -> r.

The instances serve the role of defining equations. Since they are unordered but not disjoint, we have to make use of the {-# OVERLAPPABLE #-} pragma to lower the priority of the most general instance.

The computation happens during constraint solving. This time, we don't get lucky and trying to compute the 42nd Fibonacci number runs out of memory and fails. As a consolation prize, we can still compute the 21st Fibonacci number:

main = print (fibVal (Proxy @21))

This takes about 3 seconds to compile and prints the result instantly.

Conclusion

Compile-time evaluation in Haskell is easily achieved with Template Haskell. Sometimes type families do a better job, but their performance is unreliable. Functional dependencies are the most esoteric approach, but it also works in limited circumstances.

Let us know which approach looks more interesting and promising to you, and we will cover it in more detail in our next blog post!

Serokell

@serokell

Which one of the three ways would you like to have a more detailed post on?

14:00 PM - 05 Jan 2021