FizzBuzz

There is a children’s game that is sometimes used as a simple programming task and it goes like so:

  • count the numbers 1, 2, 3, …​

  • instead of every third number say "fizz"

  • instead of every fifth number say "buzz"

  • when fizz and buzz fall together, say "fizzbuzz".

While this is a rather trivial task, it can anyway bring some insight about functional design and modularity - if we only dare to question our conventional approach and are bold enough to leave our comfort zone.

The pieces

There are many ways to solve the task and we will follow a path that may seem a bit unfamiliar when you come from imperative, object oriented programming: we will combine infinite productions.

First, we need an infinite production of numbers. In Frege that is used so often that it has it’s own idiom:

All numbers
[1..]

Second, we need a pattern like "every third item" for the fizzes. We model this as an endless repetition of strings, which are all empty, except every third one is "fizz".

The infinite fizz pattern
fizzes = cycle ["", "", "fizz"]

By now, you will have guessed what the buzzes pattern looks like.

The infinite buzz pattern
buzzes = cycle ["", "", "", "", "buzz"]

These are all the pieces we need. Note how naturally they follow from the specification.

Combining rules

Now we have to combine the parts. First, we have to create a pattern that combines fizzes and buzzes such that we get a pattern like
"", "", "fizz", "", "buzz", "fizz", "", …​

It can be created by simply concatenating fizzes and buzzes item-wise, to create a new, endless production:

fizzes:  "", "", "fizz", "", "",     "fizz", "", ...
buzzes:  "", "", "",     "", "buzz", "",     "", ...
(++)  :  "", "", "fizz", "", "buzz", "fizz", "", ...
The infinite fizz-buzz pattern
pattern = zipWith (++) fizzes buzzes

One can view this pattern as a new rule that is constructed as a combination of the previous primitive rules.

For the Geeks

We make use of the fact that concatenating the empty string at the front or at the rear leaves a string unchanged. Strings actually form a Monoid under concatenation with "" as the neutral element. The operation is also associative, which would be required if we combined three or more rules.

We now have an infinite fizzbuzz pattern.

Combine with numbers

Now we can superimpose the pattern on the infinite list of numbers to get the final infinite production.

The final fizzbuzz solution
fizzes   = cycle ["", "", "fizz"]
buzzes   = cycle ["", "", "", "", "buzz"]
pattern  = zipWith (++) fizzes buzzes
fizzbuzz = zipWith combine pattern [1..] where
    combine word number = if null word
                             then show number
                             else word
Note
 The use of 'null' in the code above does not refer to the null pointer reference but to a function called 'null' which returns true if it’s argument is an empty list (eg. a blank string).

These infinite productions are very versatile to use. We have already seen twice how to combine them, but they can also be easily filtered and selected from for printing.

Showing parts of the infinite production
main _ = do
    println $ take 5 $ drop 200 fizzbuzz

--  ["fizz", "202", "203", "fizz", "buzz"]

Considerations

When searching the web, you will find solutions like the one below, which has actually been the #1 hit.

Imperative FizzBuzz
public class FizzBuzz{
    public static void main(String[] args){
        for(int i= 1; i <= 100; i++){
            if(i % 15 == 0){
                System.out.println("FizzBuzz");
            }else if(i % 3 == 0){
                System.out.println("Fizz");
            }else if(i % 5 == 0){
                System.out.println("Buzz");
            }else{
                System.out.println(i);
            }
        }
    }
}

While the imperative solution will be more familiar to many readers (and until recently that would have included myself) there are hard facts that reveal how intertwined the imperative solution is compared to the simple, modular one in Frege.

Conditionals

Programming errors are more likely to appear the more conditionals are in the code. In nested conditionals the probability of errors increases exponentially (at least for me).
Imperative: 4 conditionals, 3 of them nested (complexity 3)
Frege: 1 conditional (complexity 0)

Operators

The more operators there are in my code, the more likely errors creep in. With combination of operators the probability of errors increases exponentially (at least for me).
Imperative: 7 (it would be 10 when using i % 3 == 0 && i % 5 == 0)
Frege: 1

Sequencing

What can go wrong if I get the sequence of operations wrong?
Imperative: I must first handle the % 15 case, then the % 3 and %5 cases, then the number case. Any other sequence is wrong!
Frege: any ordering of the lines is equally correct! (Referential transparency).

Maintainability

  • What pieces of the code do you have to change to show some other part of the fizzbuzz sequence?
    Imperative: have to rework the loop
    Frege: change one number

  • How much code do you have to touch when not printing to stdout but to stderr?
    Imperative: 4 lines
    Frege: 1 line

  • How much code do you have to touch when a rule changes? What if there are new multiples that need to be included?
    Imperative: everything must be reworked (and correct sequencing will be tricky)
    Frege: small, localized change

Specification

How well is the specification reflected in the implementation?
Imperative: very indirectly (where is modulo 15 in the spec?)
Frege: exact one-to-one correspondence

Incremental Development

The Frege solution can be developed incrementally: one line at a time. We never have to go back to change an old line. We don’t even have to recompile! This is big, because we cannot possibly introduce bugs in the code that we build upon.
The imperative solution must be touched and recompiled with every increment.

Testability

The Frege solution allows testing of every single line.
The imperative solution is hard to test at all because the side effect is wired in. But even if that would be resolved, one could only test the whole solution in total.

In his seminal paper "Why functional programming matters", John Hughes makes the point that one main benefit is improved modularity by separating production of data from its usage and combining simple pieces of logic.
The fizzbuzz task is a compelling evidence for that claim. Every single line of the functional code constitutes a module. The imperative solution is a monolith.

References

Why FP matters

http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf
Simplicity

Rich Hickey, RailsConf Keynote 2012 https://www.youtube.com/watch?v=rI8tNMsozo0
RxJava

An interesting solution by Tim Yates https://gist.github.com/timyates/0d6b47e429023630a750
Java 8

The Scalarian has correctly pointed out that with Java 8 there is a much less imperative solution https://github.com/thescalarian/FregeGoodness/blob/patch-1/src/docs/asciidoc/fizzbuzz.adoc
FizzBuzz Solutions

C2 Wiki, Fizzbuzz Trek by Kevlin Henney, Better Java Solutions by Oliver Gierke and others
Carlo Pescio

A criticial review Draft

results matching ""

    No results matching ""