fizzbuzz :: [Int] -> [String] fizzbuzz = map transform [1..100]
There is no problem that - when you look at it closely enough - doesn’t become even weirder and less comprehensible.
FizzBuzz has turned out to be a much more interesting programming challenge than originally expected. It looks so simple on the outside but it expands into a prolific solution space.
Our previous solutions (fizzbuzz and revisited) have many benefits but they share a downside that we silently ignored so far: they do not perform well for large numbers like the FizzBuzz values from one million upwards. The old solutions had to iterate to the one million before emitting values.
We will resolve this issue with a reconstruction that shows even more characteristics of functional thinking:
The fundamental question of functional programming
Modeling with types
Following the types
We take another step up the ladder of functional programming proficiency.
The Fundamental Question of Functional Programming
When solving a programming challenge the functional way, there is one fundamental question to ask:
This task is a function from what to what?
FizzBuzz is a function from a sequence of integers to a sequence of strings.
Now we have the fundamental question again:
transform is a function from what to what?
It transforms the integer 1 to the String result "1", 3 to "fizz", 5 to "buzz", 15 to "fizzbuzz", etc. with respect to the rules of the game.
transform :: Int -> String
This leaves us with two considerations for implementing
the rules of the game
Model with Types
Let’s start with the rules that we have to apply:
if n is divisible by 3, add "fizz" to the result
if n is divisible by 5, add "buzz" to the result
if no other rules apply then
show nis the only result
In other words: a rule is a function. And again the question: a function from what to what?
we need the number to work on, let’s call it
we need the results of the previously applied rules (a list of Strings)
we return a new result list
type Rule = Int -> [String] -> [String]
A first step at modelling the fizz-rule could be
fizzRule :: Rule fizzRule n old = if n `rem` 3 > 0 then old else old ++ ["fizz"]
But, well, we need to do the same for "buzz", so we remove the duplication by using parameters for the divisor (3 or 5) and the result word ("fizz" or "buzz"):
divBy:: Int -> String -> Rule divBy divisor word n old = if n `rem` divisor > 0 then old else old ++ [word] fizzRule:: Rule fizzRule = divBy 3 "fizz" buzzRule :: Rule buzzRule = divBy 5 "buzz"
Now comes the first litmus test for our approach. Can we come up with a
using a number when no other rule applies?
It’s easy. We only have to follow the types.
Since a rule is a function from the number and the list of old results to a new result list, we simply provide such a function.
numberRule :: Rule numberRule n  = [show n] numberRule _ result = result
The rules work fine in isolation but for the FizzBuzz challenge, we have to combine the rules. Here is where the functional approach really shines. Rules are functions and functions are dead-simple to compose (cmp. function composition notation).
We can pass the result from a function call to the
fizzRule as an argument to the
buzzRule and that again to the
Nested calls like
numberRule n (buzzRule n (fizzRule n  )) would do the trick
but it is visually nicer to use the
(.) function composition operator.
rules :: Rule rules n = numberRule n . buzzRule n . fizzRule n
How cool is that?
When we compose two rules, what do we get? - Another rule!
Follow the Types
With the composition of all rules under our belt, we can start thinking
toString functionality that we need to apply to the
result of having all rules applied to a number.
Again, we ask the fundamental question: "
toString is a function from what to what?"
We need a rule and show its result as a String.
We need a number where the rule is applied to.
We return a String.
toString :: Rule -> Int -> String
The implementation almost writes itself. We have no other choice than applying the rule to the number and an initially empty result list in order to get a list of result strings.
From that list of strings, we make a single string by concatenation.
Chances are that there is already is a function that does this.
It would need to have the type
[String] → String.
If you look up Froogle for such a function you will find
takes another String parameter to use for separation.
Since we need no separation, we provide an empty String.
toString :: Rule -> Int -> String toString rule n = joined "" (rule n )
toString works for any rule, and since our combination of rules,
rules, is itself a rule, it works for that whole combination as well.
Putting it all together
With the combination of all
rules and the
toString being available, we can
finally implement the
transform that we started with,
It is - as you might remember - of type
Int → String.
transform :: Int -> String transform n = toString rules n
This leaves us with the following solution. I removed the type declarations. Remember that they are optional while still retaining full type safety.
type Rule = Int -> [String] -> [String] divBy divisor word n old = if n `rem` divisor > 0 then old else old ++ [word] fizzRule = divBy 3 "fizz" buzzRule = divBy 5 "buzz" numberRule n  = [show n] numberRule _ result = result rules n = numberRule n . buzzRule n . fizzRule n toString rule n = joined "" (rule n ) transform n = toString rules n main _ = for (map transform [1..100]) println
The new solution
retains all benefits of the previous solutions
handles large numbers with no performance hit
makes new rules even easier to create and combine with existing ones (one might even call it an embedded domain-specific language)
allows rules as functions, which makes them extremely versatile
You are hopefully convinced (again) that functions are cool and function types even more so.
Many thanks to Daniel Kröni for many inspiring discussions and suggestions.
FizzBuzz in Haskell by Embedding a Domain-Specific Language https://themonadreader.files.wordpress.com/2014/04/fizzbuzz.pdf