Semigroup resonance FizzBuzz by Mark Seemann
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.
