An alternative solution to the FizzBuzz kata.

A common solution to the FizzBuzz kata is to write a loop from 1 to 100 and perform a modulo check for each number. Functional programming languages like Haskell don't have loops, so instead you'd typically solve the kata like this:

```isAMultipleOf :: Integral a => a -> a -> Bool
isAMultipleOf i multiplier = i `mod` multiplier == 0

convert :: (Integral a, Show a) => a -> String
convert i | i `isAMultipleOf` 3 && i `isAMultipleOf` 5 = "FizzBuzz"
convert i | i `isAMultipleOf` 3 = "Fizz"
convert i | i `isAMultipleOf` 5 = "Buzz"
convert i = show i

main :: IO ()
main = mapM_ putStrLn \$ convert <\$> [1..100]```

There's more than one way to skin this cat. In this article, I'll demonstrate one based on `Semigroup` resonance.

### Fizz stream #

The fundamental idea is to use infinite streams that repeat at different intervals. That idea isn't mine, but I've never seen it done without resorting to some sort of Boolean conditional or pattern matching.

You start with a finite sequence of values that represent the pulse of Fizz values:

`[Nothing, Nothing, Just "Fizz"]`

If you repeat that sequence indefinitely, you now have a pulse of Fizz values:

```fizzes :: [Maybe String]
fizzes = cycle [Nothing, Nothing, Just "Fizz"]```

This stream of values is one-based, since the first two entries are `Nothing`, and only every third is `Just "Fizz"`:

```*FizzBuzz> take 9 fizzes
[Nothing, Nothing, Just "Fizz", Nothing, Nothing, Just "Fizz", Nothing, Nothing, Just "Fizz"]```

If you're wondering why I chose a stream of `Maybe String` instead of just a stream of `String` values, I'll explain that now.

### Buzz stream #

You can define an equivalent infinite stream of Buzz values:

```buzzes :: [Maybe String]
buzzes = cycle [Nothing, Nothing, Nothing, Nothing, Just "Buzz"]```

The idea is the same, but the rhythm is different:

```*FizzBuzz> take 10 buzzes
[Nothing, Nothing, Nothing, Nothing, Just "Buzz", Nothing, Nothing, Nothing, Nothing, Just "Buzz"]```

Why not simply generate a stream of `String` values, like the following?

```*FizzBuzz> take 10 \$ cycle ["", "", "", "", "Buzz"]
["", "", "", "", "Buzz", "", "", "", "", "Buzz"]```

At first glance this looks simpler, but it makes it harder to merge the stream of Fizz and Buzz values with actual numbers. Distinguishing between `Just` and `Nothing` values enables you to use the Maybe catamorphism.

### Resonance #

You can now zip the `fizzes` with the `buzzes`:

```fizzBuzzes :: [Maybe String]
fizzBuzzes = zipWith (<>) fizzes buzzes```

You combine the values by monoidal composition. Any `Maybe` over a `Semigroup` itself gives rise to a `Monoid`, and since `String` forms a `Monoid` (and therefore also a `Semigroup`) over concatenation, you can zip the two streams using the `<>` operator.

```*FizzBuzz> take 20 fizzBuzzes
[Nothing, Nothing, Just "Fizz", Nothing, Just "Buzz", Just "Fizz", Nothing, Nothing, Just "Fizz",
Just "Buzz", Nothing, Just "Fizz", Nothing, Nothing, Just "FizzBuzz", Nothing, Nothing, Just "Fizz",
Nothing, Just "Buzz"]```

Notice how the stream of `fizzes` enters into a resonance pattern with the stream of `buzzes`. Every fifteenth element the values Fizz and Buzz amplify each other and become FizzBuzz.

### Numbers #

While you have an infinite stream of `fizzBuzzes`, you also need a list of numbers. That's easy:

```numbers :: [String]
numbers = show <\$> [1..100]```

You just use a list comprehension and map each number to its `String` representation using `show`:

```*FizzBuzz> take 18 numbers
["1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18"]```

Now you just need to figure out how to merge the `fizzBuzzes` with the `numbers`.

### Zip with catamorphism #

While you can trivially `zip` `fizzBuzzes` with `numbers`, it doesn't solve the problem of which value to pick:

```*FizzBuzz> take 5 \$ zip numbers fizzBuzzes
[("1", Nothing), ("2", Nothing), ("3", Just "Fizz"), ("4", Nothing), ("5", Just "Buzz")]```

You want to use the second element of each tuple when there's a value, and only use the first element (the number) when the second element is `Nothing`.

That's easily done with `fromMaybe` (you'll need to `import Data.Maybe` for that):

```*FizzBuzz> fromMaybe "2" Nothing
"2"
*FizzBuzz> fromMaybe "3" \$ Just "Fizz"
"Fizz"```

That's just what you need, so zip `numbers` with `fizzBuzzes` using `fromMaybe`:

```elements :: [String]
elements = zipWith fromMaybe numbers fizzBuzzes```

These `elements` is a list of the values the kata instructs you to produce:

```*FizzBuzz> take 14 elements
["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14"]```

`fromMaybe` is a specialisation of the Maybe catamorphism. I always find it interesting when I can solve a problem with catamorphisms and monoids, because it shows that perhaps, there's some value in knowing universal abstractions.

### From 1 to 100 #

The kata instructions are to write a program that prints the numbers from 1 to 100, according to the special rules. You can use `mapM_ putStrLn` for that:

```main :: IO ()
main = mapM_ putStrLn elements```

When you execute the `main` function, you get the desired output:

```1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16```

... and so on.

### Golf #

Haskell golfers may complain that the above code is unnecessarily verbose. I disagree, but you can definitely write the entire kata as a 'one-liner' if you want to:

```main :: IO ()
main =
mapM_ putStrLn \$
zipWith fromMaybe (show <\$> [1..100]) \$
zipWith
(<>)
(cycle [Nothing, Nothing, Just "Fizz"])
(cycle [Nothing, Nothing, Nothing, Nothing, Just "Buzz"])```

I've just mechanically in-lined all the values like `fizzes`, `buzzes`, etc. and formatted the code so that it fits comfortable in a 80x24 box. Apart from that, I don't think that this is an improvement, but it has the same behaviour as the above, more verbose alternative.

### Conclusion #

You can implement the FizzBuzz kata using the fundamental concepts catamorphism, semigroup and monoid. No `if-then-else` instructions or pattern matching is required. Instead, you use the string concatenation semigroup to enable resonance between two pulses, and the maybe catamorphism to combine with the list of numbers.

### Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or somewhere else with a permalink. Ping me with the link, and I may respond.

#### Published

Monday, 30 December 2019 10:44:00 UTC

#### Tags

"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!
Published: Monday, 30 December 2019 10:44:00 UTC