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:
One of the main problems of type-level programming in Haskell is that you cannot implement higher-order functions on the type level (see saturation restriction). Therefore, we cannot abstract as much as we do on the term level using
[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 higher-order functions into first-order 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
applyfunction interpret all of your symbols and produce the value you want.
Below we present the implementation of Fizz Buzz on the type-level 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 higher-order combinators and easier to understand since most of the complexity is moved away to the singletons’ library.
Type-level programming in Haskell is still a difficult task since the support for higher-order 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 higher-order abstractions on the type level.