Fibonacci in compile time

functional-dependency-fib.hs

{-# LANGUAGE FlexibleInstances, FunctionalDependencies, UndecidableInstances #-}
-- Esoteric programming with Haskell:
-- http://www.cse.chalmers.se/~hallgren/Papers/hallgren.pdf
-- https://repl.it/repls/AquaGainsboroSquares

module Main where

import System.IO

u = undefined

data Zero
data Succ n

class Eval n where eval :: n -> Int
instance Eval Zero where eval _ = 0
instance Eval n => Eval (Succ n) where eval n = 1 + eval (predcs n) 

class Add a b c | a b -> c where add :: a -> b -> c
instance Add Zero b b
instance Add a b c => Add (Succ a) b (Succ c)

class Fib a b | a -> b where
    fib :: a -> b
instance Fib Zero Zero
instance Fib One One
instance (Fib a b, Fib (Succ a) c, Add b c d) => Fib (Succ (Succ a)) d

class Pred a b | a -> b where predcs :: a -> b
instance Pred (Succ n) n

type One = Succ Zero
type Three = Succ (Succ (Succ Zero))
type Six = Succ (Succ (Succ (Succ (Succ (Succ Zero)))))
type Twelve = Succ (Succ (Succ (Succ (Succ (Succ Six)))))
type Thirteen = Succ Twelve

main :: IO ()
main = print . eval . fib $ (u::Twelve)