This morning, I saw this blog by @cercerilla on twitter. I was fascinated by her implementation but I couldn’t believe how many lines of code it took to write such a simple program! The Fizz Buzz problem can be implemented on the term level with only a few lines of code:
1 

One of the main problems of typelevel programming in Haskell is that you cannot implement higherorder functions on the type level (see saturation restriction). Therefore, we cannot abstract as much as we do on the term level using traverse
and [1..100]
. There is an accepted proposal unsaturated type families but it still not merged into GHC.
Are we doomed to write a lot of boilerplate code as in @cercerilla
example? The answer is no, there is a workaround to this problem called defunctionalization. Defunctionalization translates higherorder functions into firstorder functions:
 Instead of working with functions, work with symbols representing functions.
 Build your final functions and values by composing and combining these symbols.
 At the end of it all, have a single
apply
function interpret all of your symbols and produce the value you want.
This idea of defunctionalization is implemented in the singletons and in firstclassfamilies.
Below we present the implementation of Fizz Buzz on the typelevel using the singletons
library(you can achieve a similar result using fcf
package). The implementation is many times smaller than the one implemented using ad hoc higherorder combinators and easier to understand since most of the complexity is moved away to the singletons’ library.
1 

Typelevel programming in Haskell is still a difficult task since the support for higherorder abstractions is still not available in the language. With the use of libraries such as singletons
we can make this task less difficult reusing many higherorder abstractions on the type level.