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 aSymbol
, a type-level string, into aString
.
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.