17 August 2023

Previously I shared Uri Wilensky
and Seymour Papert^{1}’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:^{2}

```
fizzbuzz :: Int -> String
| n `mod` 15 == 0 = "FizzBuzz"
fizzbuzz n | n `mod` 3 == 0 = "Fizz"
| n `mod` 5 == 0 = "Buzz"
otherwise = show n
= take n $ map fizzbuzz [1..] fizzbuzzs n
```

`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
= take n $ map fizzbuzz_v2 [1 ..] fizzbuzzs_v2 n
```

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
= take n $ map (fizzbuzz_v3 (3, "Fizz") (5, "Buzz")) [1 ..] fizzbuzzs_v3 n
```

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.

- We keep our function for the two-factor case and we just add a new function for the three-factor case.
- 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
= take n $ map (fizzbuzz3 (3, "Fizz") (5, "Buzz") (2, "Bazz")) [1 ..] fizzbuzzs3 n
```

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:

- 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)\} \}
- Sort the power set and list by decreasing size, e.g., F=[ \{(3, Fizz), (5, Buzz)\}, \{(3, Fizz)\}, \{(5, Buzz)\}, \{\} ]
- 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).
- If 0, then concatenate F_i’s \mathbf{String} labels, and return that.
- 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 [] : xs) = [x : mbr | mbr <- powerset xs] ++ powerset xs powerset (x
```

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

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

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).^{3}

```
fizzbuzzN :: [(Int, String)] -> Int -> String
= fromMaybe (show n) (firstModulo $ lsort (powerset ls))
fizzbuzzN ls n where
= Nothing
ifModulo m [] =
ifModulo m ls let
= product $ map fst ls
factor = concatMap snd ls
label in if mod m factor == 0 then Just label else Nothing
= join $ find isJust $ map (ifModulo n) ls firstModulo 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.^{4}

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. ^{5} 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
= if mod n m == 0 then str else "" period m str n
```

For convenience, let’s also define a `Stream`

of natural
numbers.

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

And now we need a combination function

```
combine :: Stream -> Stream -> Stream
= f n ++ g n combine f 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

- Return
`""`

if both`f n`

and`g n`

are`""`

. - Return some label if either
`f n`

or`g n`

have a label. - 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
= if f n /= "" then f n else g n leftElseRight f 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.

- Modularity:
- 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.
- 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.

- Data structures: Instead of a single logic-driven function, we
identified and exposed
*stream*s as the foundational building blocks of the game. This aligns with Eric Steven Raymond^{6}’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^{7} means when he
says

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

“Restructurations: Reformulations of Knowledge Disciplines Through New Representational Forms,”

*Constructionism*17, no. 2010 (2010): 1–15.↩︎All code is in Haskell, compiled with GHC 8.10.↩︎

Note the following imports needed for utility functions used here:

↩︎`import Control.Monad (join) import Data.List import Data.Maybe (fromMaybe, isJust) import Data.Ord`

Further, in our original implementation, the order in which we calculated the different modulo operations mattered. e.g., computing n \; \mathrm{mod}\; 3 and returning Fizz before computing n \; \mathrm{mod}\; (3\cdot5) and returning FizzBuzz would be incorrect because the second n\;\mathrm{mod}\; (3\cdot5) calculation would never be reached, and FizzBuzz would never be returned.↩︎

This is what Mark Seeman calls the

*resonance*approach, previously mentioned in list comprehensions.↩︎“The Art of Unix Programming” (Boston: Addison-Wesley, 2004).↩︎

*Righting Software: A Method for System and Project Design*(Addison-Wesley, 2019).↩︎