A software engineer website

Fizzbuzz kata: branchless version

Gautier DI FOLCO March 13, 2024 [Code practice] #haskell #code kata #coding dojo

A 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` display `Fizz`, if the number is a multiple of `5` display `Buzz`, is the number is a multiple of both `3` and `5` display `FizzBuzz`, 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
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:

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

fizzs :: [Maybe String]
fizzs = cycle [Nothing, Nothing, Just "Fizz"]
-- fizzs = [Nothing, Nothing, Just "Fizz", Nothing, Nothing, Just "Fizz", ..]

buzzs :: [Maybe String]
buzzs = cycle [Nothing, Nothing, Nothing, Nothing, Just "Buzz"]
-- buzzs = [Nothing, Nothing, Nothing, Nothing, Just "Buzz", Nothing, Nothing, Nothing, Nothing, Just "Buzz", ..]
``````

Note: they are 1-indexed

Then we have to rely on `Semigroup` which is defined as follows:

``````class Semigroup a where
(<>) :: a -> a -> a
``````

It has two interesting instances:

``````instance Semigroup a => Semigroup (Maybe a) where
Just x <> Just y = Just \$ x <> y
Just x <> Nothing = Just x
Nothing <> Just x = Just x
Nothing <> Nothing = Nothing

instance Semigroup String where -- 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`:

``````fizzbuzzStream :: [String]
fizzbuzzStream = zipWith fromMaybe numbers \$ zipWith (<>) fizzs buzzs
-- ["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz", ..]
``````

Finally we can simply get the matching string by accessing to the corresponding element in the stream:

``````fizzbuzz :: Int -> String
fizzbuzz n = fizzbuzzStream !! (n - 1)
``````

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.