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

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

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!

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.

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

FizzBuzz Reconstructed