Fizzbuzz kata: branchless version
Gautier DI FOLCO March 13, 2024 [Code practice] #haskell #code kata #coding dojoA well known code kata is the fizzbuzz, it can be described as follows:
For any strictly positive number, if the number is a multiple of
3
displayFizz
, if the number is a multiple of5
displayBuzz
, is the number is a multiple of both3
and5
displayFizzBuzz
, otherwise display display the number.
We can express this specification with the following tests:
describe "FizzBuzz" $ do
forM_ [(1, "1"), (2,"2")] $ \(param, result) ->
it (show param <> " should be " <> result) $
fizzbuzz param `shouldBe` result
it "All multiple of three start with 'Fizz'" $
property $ \n ->
n > 0 ==> isInfixOf "Fizz" $ fizzbuzz (3 * n)
it "All multiple of five ends with 'Buzz'" $
property $ \n ->
n > 0 ==> isSuffixOf "Buzz" $ fizzbuzz (5 * n)
One of the constraint we often use at Software Crafters Lyon in branchless (actually it is if-less, but it is more OOP/procedural-oriented, which does not cover pattern-matching).
To make the FizzBuzz compliant we have to see it as an infinite stream where,
one every 3
elements starts with Fizz
, one every 5
elements ends with Buzz
,
otherwise we have the number.
Let's declare each stream:
= show <$> [1..]
fizzs = cycle [Nothing, Nothing, Just "Fizz"]
-- fizzs = [Nothing, Nothing, Just "Fizz", Nothing, Nothing, Just "Fizz", ..]
buzzs = cycle [Nothing, Nothing, Nothing, Nothing, Just "Buzz"]
-- buzzs = [Nothing, Nothing, Nothing, Nothing, Just "Buzz", Nothing, Nothing, Nothing, Nothing, Just "Buzz", ..]
numbers
Note: they are 1-indexed
Then we have to rely on Semigroup
which is defined as follows:
It has two interesting instances:
Just x <> Just y = Just $ x <> y
Just x <> Nothing = Just x
Nothing <> Just x = Just x
Nothing <> Nothing = Nothing
-- Actually it is defined on any lists (`[a]`)
(<>) = (++) -- lists/strings concatenation
That being said, we can zip our fizzs
and buzzs
:
zipWith (<>) fizzs buzzs
-- [Nothing, Nothing, Just "Fizz", Nothing, Just "Buzz", Just "Fizz", Nothing, Nothing, Just "Fizz", Just "Buzz", Nothing, Just "Fizz", Nothing, Nothing, Just "FizzBuzz", ..]
-- [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , ..]
Then, in order to do a proper stream, we have to default the Nothing
with
fromMaybe
:
= zipWith fromMaybe numbers $ zipWith (<>) fizzs buzzs
-- ["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz", ..]
fizzbuzzStream
Finally we can simply get the matching string by accessing to the corresponding element in the stream:
= fizzbuzzStream !! (n - 1)
fizzbuzz n
Branch-less is an interesting constraint when the type is opaque (e.g. Applicative
,
Monad
) because you are able to add code without changing the type.
In all other cases, GHC checks that all branches of sum types are covered.