# 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 `Symbol`

s, type-level strings that support string literals, and `Nat`

s, 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.

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.

Use operators like `+`

at the type-level.

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.

`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`

.

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)}'`

.

`CmpNat`

returns `Ordering`

, convert `'EQ`

to ‘’True’ and `'GT`

and `'LT`

to `'False`

.

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 `Nat`

s, 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 `Nat`

s 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.