## 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:

The Fundamental Question of Functional Programming

This task is a function from what to what?

FizzBuzz is a function from a sequence of integers to a sequence of strings.

FizzBuzz is a mapping
``````fizzbuzz :: [Int] -> [String]
fizzbuzz = map transform [1..100]``````

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.

Type for transform
``transform :: Int -> String``

This leaves us with two considerations for implementing `transform`:

• the rules of the game

• a `toString` for rules

### Model with Types

• 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

The Function Type for a Rule
``type Rule = Int -> [String] -> [String]``

A first step at modelling the fizz-rule could be

Preliminary fizz rule
``````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"):

Parameterized Fizz and Buzz Rule
``````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"``````
Missing parameters?

It looks as if the parameters and arguments for `n` and `old` would be missisng in `fizzRule` and `buzzRule`. We have discarded them to make the code even more compelling (cmp. point-free).

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.

The "number" rule with case discrimination
``````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 are functions so let’s combine them
``````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!

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.

The type of toString
``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.

Apply a rule and get the result as a 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 is simple
``````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.

The full solution
``````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.

This is a function from what to what?

Asking the fundamental question of functional programming "this is a function from what to what" will change your way of programming regardless what language you use.

 Note Thanks! Many thanks to Daniel Kröni for many inspiring discussions and suggestions.

### References

 Froogle Lookup `joined` by type: http://hoogle.haskell.org:8081/?hoogle=%5BString%5D%20-%3E%20String 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