FizzBuzz Plus Ultra

Previously I shared Uri Wilensky and Seymour Papert¹’s concept of restructuration. Here I want to contrast a most common implementation of the FizzBuzz game, with one that represents the domain differently and that, I hope to demonstrate, is superior to the first one because of this. More generally, my hope is to show the impact that representations can have on our ability to solve problems.

Let’s start by stating the problem. Suppose you have a client, Zeno, that comes to you an says:

As someone who wants to win the FizzBuzz game at all cost, I would like a tool that generates for me a FizzBuzz game sequence of arbitrary length, so I can memorize it and beat everyone at the game.

We understand the FizzBuzz game sequence as follows:

• The FizzBuzz game sequence consists of a sequence of integer numbers, except where the number is a multiple of 3 or 5.
• If the numbers is a multiple of 3, we should see a Fizz instead of the number.
• If the numbers is a multiple of 5, we should see a Buzz instead of the number.
• If the numbers is a multiple of 5 \cdot 3, we should see a FizzBuzz instead of the number.

Let’s start with what I’ll call the standard FizzBuzz implementation, in Haskell:²

fizzbuzz :: Int -> String
fizzbuzz n | n `mod` 15 == 0  = "FizzBuzz"
           | n `mod` 3  == 0  = "Fizz"
           | n `mod` 5  == 0  = "Buzz"
           otherwise          = show n

fizzbuzzs n = take n $ map fizzbuzz [1..]

fizzbuzz computes the single value of the game sequence that corresponds to integer n. fuzzbuzzs (plural) computes the values for all integers from 1 to n.

This is simple and works as expected. But now Zeno comes and says

This was great, I’ve beaten everyone at the game with this tool! However, my friends figured me out and they now want to arbitrarily choose any two factors.

Ok, no problem; we just need to parameterize those factors:

fizzbuzz_v2 :: Int -> Int -> Int -> String
fizzbuzz_v2 f1 f2 n
  | n `mod` (f1 * f2) == 0 = "FizzBuzz"
  | n `mod` f1 == 0 = "Fizz"
  | n `mod` f2 == 0 = "Buzz"
  | otherwise = show n

fizzbuzzs_v2 n = take n $ map fizzbuzz_v2 [1 ..]

Easy enough. Zeno now comes back and tells us that his friends now want to replace the Fizzs and the Buzzs with arbitrary labels (i.e., words). So we now just parameterize the labels as well.

fizzbuzz_v3 :: (Int, String) -> (Int, String) -> Int -> String
fizzbuzz_v3 (f1, s1) (f2, s2) n
  | n `mod` (f1 * f2) == 0 = s1 ++ s2
  | n `mod` f1 == 0 = s1
  | n `mod` f2 == 0 = s2
  | otherwise = show n

fizzbuzzs_v3 n = take n $ map (fizzbuzz_v3 (3, "Fizz") (5, "Buzz")) [1 ..]

But, Zeno has yet another request.

Ok, my friends and I are now pros, and we want to do three factors, not just two.

Hm, ok this starts to get a bit more interesting. I can think of two obvious routs.

1. We keep our function for the two-factor case and we just add a new function for the three-factor case.
2. We can start thinking about generalizing this to any number of factors.

If Zeno has asked us to support three factors, it seems likely he’ll come back for four later on, and then five, and so on. So my inclination at this point is to go ahead and generalize. But, let’s just first implement fizzbuzz3 for the three-factor case to see what this would look like following our current approach:

fizzbuzz3 :: (Int, String) -> (Int, String) -> (Int, String) -> Int -> String
fizzbuzz3 (f1, s1) (f2, s2) (f3, s3) n
  | n `mod` (f1 * f2 * f3) == 0 = s1 ++ s2 ++ s3
  | n `mod` (f1 * f2) == 0 = s1 ++ s2
  | n `mod` (f1 * f3) == 0 = s1 ++ s3
  | n `mod` (f2 * f3) == 0 = s2 ++ s3
  | n `mod` f1 == 0 = s1
  | n `mod` f2 == 0 = s2
  | n `mod` f3 == 0 = s3
  | otherwise = show n

fizzbuzzs3 n = take n $ map (fizzbuzz3 (3, "Fizz") (5, "Buzz") (2, "Bazz")) [1 ..]

Not as pretty any more. And guess what, Zeno indeed now wants four. This approach is getting pretty silly because for m factors we’ll need to have 2^m match checks, and as many functions as factors in the game. What we want at this point is a single function that can take any number of (Int, String) values:

fizzbuzz :: [(Int, String)] -> Int -> String

Following the pattern of the functions we’ve written so far, this more general function should:

1. Build the power set P(S) of the set \{(\mathbb{N}^+, \mathbf{String})\} of (number, string) pairs. e.g., for set S=\{(3, Fizz), (5, Buzz)\} the power set is P(S)=\{\{\},\{(3, Fizz)\}, \{(5, Buzz)\}, \{(3, Fizz), (5, Buzz)\} \}
2. Sort the power set and list by decreasing size, e.g., F=[ \{(3, Fizz), (5, Buzz)\}, \{(3, Fizz)\}, \{(5, Buzz)\}, \{\} ]
3. For each element F_i of the list, compute n\; \mathrm{mod} the product of all the factors in F_i. e.g., for F_0, compute n\;\mathrm{mod}\; (3\cdot 5).
   1. If 0, then concatenate F_i’s \mathbf{String} labels, and return that.
   2. Otherwise, return n.

This looks like it should work. But I’m not crazy about the approach. It seems unnecessarily complicated. Describing the algorithm in pure natural language was non-trivial for me, and I felt compelled to add the minimal mathematical notation to simplify the communication. However, let’s just implement this for completeness.

We need a function to compute the power set. Our set will actually just be a generic list ([a]) for now.

powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x : xs) = [x : mbr | mbr <- powerset xs] ++ powerset xs

We also need a function to sort the power set elements by decreasing size.

lsort :: [[a]] -> [[a]]
lsort = sortOn (Data.Ord.Down . length)

Now our main function to convert a list of (\mathbb{N}^+, \mathbf{String}) tuples into a FizzBuzz value (i.e., a number of a combination of labels).³

fizzbuzzN :: [(Int, String)] -> Int -> String
fizzbuzzN ls n = fromMaybe (show n) (firstModulo $ lsort (powerset ls))
  where
    ifModulo m [] = Nothing
    ifModulo m ls =
      let 
        factor = product $ map fst ls
        label = concatMap snd ls
      in if mod m factor == 0 then Just label else Nothing
    firstModulo ls = join $ find isJust $ map (ifModulo n) ls

• ifModulo is the function that computes the modulo on the product of the factors in each of the elements of the power set, and returns either the label or Nothing in a Maybe String type.
• firstModulo applies ifModulo to each element of the power set, and finds and returns the first result with a label.
• fromMaybe chooses between the number n and the result of firstModulo. If firstModulo is not Nothing it returns the label, otherwise it returns n.

That’s it. Let’s run this:

*Main> [fizzbuzzN [(3, "Fizz"), (5, "Buzz")] n | n <- [1..15]]
["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

Ok… The implementation, as expected from the above description, has a complexity beyond what seems necessary. There must be a better way; better in the sense that it can be either simpler or more powerful or both (yes, I want my cake and eat it too ;-). Let’s find it. First, let’s step back, forget for a moment about our current approach, and describe again with an agnostic mind what the game is about.

• The foundation of the game is counting, so it’s built on the sequence of natural numbers.
• On every multiple of 3 we say Fizz.
• On every multiple of 5 we say Buzz.
• When an overlap exists, every time an overlap exists, we say both Fizz and Buzz (In our version of the game we assume a fixed order for combinations, Fizz then Buzz.)
• Then, if a number is not a multiple of any of our factors (3 and 5), then we just say the number.

The emphasis on the word every is meant to highlight the fact that each of these statements happen unconditionally. This is an important (though subtle) difference between this description and the one of our original implementation. Notice that in our original implementation, saying either Fizz, or Buzz, or both, or a number n, was always conditioned on a modulo calculation.⁴

From this new description, it looks like the only condition we have is to decide whether we give a number or a label at a given time n. So if combination of labels in unconditional, how do we perform this combination at the right places? The modulo operation on natural numbers implies an infinite periodic function. We can think of the n \; \mathrm{mod}\; 3 as an infinite measuring tape with a Fizz label every three points, and nothing otherwise. Likewise we can think of the n \; \mathrm{mod}\; 5 as a measuring tape with a Buzz label every five points, and nothing otherwise. It looks like we can just overlay these tapes and be done. ⁵ These tapes are independent streams; independent structures that carry information about themselves and only themselves.

Ok, let’s implement this. We first define a Stream type as a function from Natural to Label. The types Natural and Label are just aliases to Int and String respectively; we define them because they provide better semantics:

type Natural = Int
type Label = String
type Stream = Natural -> Label

Let’s now define a function to generate periodic streams. For the empty slots, we’ll just return an empty string (for now).

period :: Int -> Label -> Stream
period m str n = if mod n m == 0 then str else ""

For convenience, let’s also define a Stream of natural numbers.

naturals :: Stream
naturals n = show $ [0 ..] !! n

And now we need a combination function

combine :: Stream -> Stream -> Stream
combine f g n = f n ++ g n

combine invokes f on n and g on n and simply concatenates the results. Because we know our streams are made of labels or empty strings, the concatenation will always work as desired. i.e., it will always either

1. Return "" if both f n and g n are "".
2. Return some label if either f n or g n have a label.
3. Return the concatenation of labels when both f n and g n have labels.

Let’s see how these work together

*Main> fizz = period 3 "Fizz"
*Main> [fizz n | n <- [1..15]]
["","","Fizz","","","Fizz","","","Fizz","","","Fizz","","","Fizz"]
*Main> buzz = period 5 "Buzz"
*Main> [buzz n | n <- [1..15]]
["","","","","Buzz","","","","","Buzz","","","","","Buzz"]
*Main> [combine fizz buzz n | n <- [1..15]]
["","","Fizz","","Buzz","Fizz","","","Fizz","Buzz","","Fizz","","","FizzBuzz"]

Not bad! Now we need a way to replace those ""’s with numbers

leftElseRight :: Stream -> Stream -> Stream
leftElseRight f g n = if f n /= "" then f n else g n

This should be straightforward; if evaluating f n does not yield "", then return f n, otherwise return g n. Now we just need to insert those natural numbers in the "" slots to get our final FizzBuzz sequence.

*Main> [leftElseRight (combine fizz buzz) naturals n | n <- [1 .. 15]]
["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

Want another stream? No problem:

*Main> bazz = period 2 "Bazz"
*Main> [leftElseRight (fizz `combine` buzz `combine` bazz) naturals n | n <- [1 .. 3*5*2]]
["1","Bazz","Fizz","Bazz","Buzz","FizzBazz","7","Bazz","Fizz","BuzzBazz","11","FizzBazz","13","Bazz","FizzBuzz","Bazz","17","FizzBazz","19","BuzzBazz","Fizz","Bazz","23","FizzBazz","Buzz","Bazz","Fizz","Bazz","29","FizzBuzzBazz"]

Easy-peasy lemon-squeezy ;-).

Let’s summarize the new implementation.

1. Modularity:
   1. Instead of a fixed function (or set of functions) to compute FizzBuzz sequences, we have a tiny set of combinator functions that allow us to generate and combine any number of sequences is novel ways.
   2. We have separated our concerns into these combinator functions. Specifically, we’ve separated stream construction, from combination, from replacement logic. In our original approach, everything was combined.
2. Data structures: Instead of a single logic-driven function, we identified and exposed streams as the foundational building blocks of the game. This aligns with Eric Steven Raymond⁶’s Rule of Representation, which says: Fold knowledge into data, so program logic can be stupid and robust.

Unlike our first approach, where we’ll have to modify our code to add new functionality (features), in this second model the built-in modularity allows us to add new functionality by composing the combinators (and creating new ones) rather than modifying them.

I think this is what Juval Löwy⁷ means when he says

Features are always and everywhere aspects of integration, not implementation.