A Preliminary Attempt at Type-Level FizzBuzz

FizzBuzz is a test to assess basic programming knowledge. Having done a bit of type-level programming GHC Haskell, I thought it would be a fun exercise to write FizzBuzz at the type-level.

We will use Symbols, type-level strings that support string literals, and Nats, type-level natural numbers that support unsigned integer literals.

The Language Extensions

We need a number of language extensions enabled because type-level programming is not a part of the Haskell standard.

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE PolyKinds #-}

Kinds are the types of types, DataKinds allows types defined with data to be used at the type-level. We need this to do operations on Nat and Symbol. PolyKinds allows support for type-level functions that take more than one parameter.

{-# LANGUAGE TypeOperators #-}

Use operators like + at the type-level.

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}

TypeFamilies allows us to define type-level functions, a function that takes a type and returns a type, and we need UndecidableInstances to call a type-level function within a type-level function.

import Data.Proxy (Proxy(..))
import GHC.TypeLits (CmpNat, Mod, symbolVal, KnownSymbol)

• Proxy passes a type as a value.
• CmpNat compares natural numbers at the type-level, returns Ordering (EQ, LT, GT).
• symbolVal is a function that converts a Symbol, a type-level string, into a String.

type family IfThenElse cond a b where
  IfThenElse 'True a _ = a
  IfThenElse _     _ b = b

You will quickly find that there are very few basic functions available for type-level programming. There is not even an if-else control structure at the type-level. 'True is a Bool constructor promoted the type-level.

type family NatToSym x where
  NatToSym 0 = "0"
  NatToSym 1 = "1"
  NatToSym 2 = "2"
  NatToSym 3 = "3"
  -- to 100

Neither is there a function to convert Nat to Symbol so we need to write them by hand. For FizzBuzz we only need 1-100. I did this quickly with seq 0 100 | awk '{printf(" NatToSym %s = \"%s\"\n", $1, $1)}'.

type family OrderToBool x where
  OrderToBool 'EQ = 'True
  OrderToBool _   = 'False

CmpNat returns Ordering, convert 'EQ to ‘’True’ and 'GT and 'LT to 'False.

type family ModRemainderIsZero x y where
  ModRemainderIsZero x y = OrderToBool (CmpNat (Mod x y) 0)

This checks if the remainder of Mod is zero or not.

type family FizzBuzz x where
  FizzBuzz x =
    IfThenElse (ModRemainderIsZero x 5)
      (IfThenElse (ModRemainderIsZero x 3) "FizzBuzz" "Buzz")
      (IfThenElse (ModRemainderIsZero x 3) "Fizz" (NatToSym x))

At the type-level we do not have guards or let-binding, but it should be pretty straightforward. Compare this to FizzBuzz in a value-level Haskell function.

fizzbuzz :: Int -> String
fizzbuzz x
  | modRemainderIsZero 15 = "FizzBuzz"
  | modRemainderIsZero 3 = "Fizz"
  | modRemainderIsZero 5 = "Buzz"
  | otherwise = show x
  where
    modRemainderIsZero = (0 ==) . mod x

It would be nice to be able to write a Map function and apply it to a type-level list of Nats, but a type-level function (closed type family) cannot be curried. My other idea was to apply (\x -> maybe (pure ()) (\y -> print $ symbolVal (Proxy :: Proxy (FizzBuzz y))) (someNatVal x)) on [0..100], but someNatVal converts a Integer to SomeNat, which does not allow us to extract the Nat value and convert it to a Symobl. It seems like GHC needs to know the Nat type at compile time. This led me to write out each line with seq 0 100 | awk '{printf(" printSymbolVal (Proxy :: Proxy (FizzBuzz %s))\n", $1)}'

printSymbolVal :: (KnownSymbol a) => Proxy a -> IO ()
printSymbolVal proxy = print $ symbolVal proxy

main :: IO ()
main = do
  printSymbolVal (Proxy :: Proxy (FizzBuzz 1))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 2))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 3))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 4))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 5))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 6))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 7))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 8))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 9))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 10))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 11))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 12))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 13))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 14))
  printSymbolVal (Proxy :: Proxy (FizzBuzz 15))

The original goal was to solve it in a more succint way, create a range of Nats at the type-level, apply FizzBuzz to each Nat and concatenate the result into a single Symbol, but the Map part was not feasible do to the lack of currying support for closed type families.