Fizzbuzz kata: branchless version

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

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.