fizzbuzz :: [Int] -> [String]
fizzbuzz = map transform [1..100]
FizzBuzz Reconstructed
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
-
Using composition
-
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 transform
:
-
the rules of the game
-
a
toString
for rules
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 n
is 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
n
-
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 numberRule
for
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
Composing Rules
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 numberRule
.
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
Note
|
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
about the 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 joined
, which
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 [])
This toString
works for any rule, and since our combination of rules,
namely 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
Summary
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.
Note
|
Thanks!
Many thanks to Daniel Kröni for many inspiring discussions and suggestions. |
References
Froogle |
Lookup |
Kevlin Henney |
gives a similar example in terse JavaScript in this video: https://www.youtube.com/watch?v=FyCYva9DhsI around minute 21ff, calling it "too clever" |
Maciej Pirog |
FizzBuzz in Haskell by Embedding a Domain-Specific Language https://themonadreader.files.wordpress.com/2014/04/fizzbuzz.pdf |