Fizzbuzz is a notorious programming problem to give during interviews. It’s designed to weed out people that can’t program at all. The problem formulation is:
Print the numbers 1 to 100. If the number is a multiple of 3, then print “Fizz” instead of the number. If the number is a multiple of 5, then print “Buzz” instead of the number. If the number is divisible by both 3 and 5, then print “FizzBuzz” instead.
The basic implementation of the problem looks like this:
class Fizz {
public static void fizzBuzz() {
for (int i = 1; i <= 100; i++) {
if (i % 3 == 0 && i % 5 == 0) {
System.out.println("FizzBuzz");
} else if (i % 3 == 0) {
System.out.println("Fizz");
} else if (i % 5 == 0) {
System.out.println("Buzz");
} else {
System.out.println(i);
}
}
}
}
Which we can translate directly to Haskell:
fizzBuzz :: IO ()
fizzBuzz =
forM_ [1..100] (\i ->
if i `mod` 3 == 0 && i `mod` 5 == 0 then
putStrLn "FizzBuzz"
else if i `mod` 3 == 0 then
putStrLn "Fizz"
else if i `mod` 5 == 0 then
putStrLn "Buzz"
else
print i
)
If the candidate is capable of answering it easily, then the spec gets increased:
Now if it is divisible by 7, print “Quux”. If it’s divisible by a combination, then it needs to print all the words.
Uh oh! These prime factors are no fun.
There’s going to be an additional if case for each prime factor, and then you’ll need an additional if case for each possible combination.
It’s much simpler if we can handle the logic without worrying about the duplication.
class Fizz {
public static void fizzBuzz() {
for (int i = 1; i < 101; i++) {
StringBuilder s = new StringBuilder();
if (i % 3 == 0) {
s.append("Fizz");
}
if (i % 5 == 0) {
s.append("Buzz");
}
if (i % 7 == 0) {
s.append("Quux");
}
if (s.length() == 0) {
s.append(i);
}
System.out.println(s.toString());
}
}
}
We’ve reduced the logic duplication by accumulating state. In Haskell, we’d use the State monad:
fizzBuzz :: (MonadIO m, MonadState String m) => m ()
fizzBuzz =
forM_ [1..100] (\i -> do
put ""
when (i `mod` 3 == 0) (modify (++"Fizz"))
when (i `mod` 5 == 0) (modify (++"Buzz"))
when (i `mod` 7 == 0) (modify (++"Quux"))
str <- get
when (null str) (put (show i))
get >>= liftIO . putStrLn
)
This implementation has the unfortunate problem of being somewhat inefficient:
those ++ calls are $O(n)$, and we’ll have to traverse the whole string each time we add something to the end.
This solves the “extensibility” problem, but there’s another issue: the printing is tied in with the generation of the strings. Let’s convert this to a map – that will both solve the performance issue noted above as well as making it less difficult to observe what’s happening. In Java, we’ve got:
class Fizz {
public static String fizzLogic(int i) {
StringBuilder s = new StringBuilder();
if (i % 3 == 0) {
s.append("Fizz");
}
if (i % 5 == 0) {
s.append("Buzz");
}
if (i % 7 == 0) {
s.append("Quux");
}
if (s.length() == 0) {
s.append(i);
}
return s.toString();
}
public static List<String> fizzBuzz() {
return IntStream
.range(1, 101)
.mapToObj(Fizz::fizzLogic)
.collect(ArrayList::new, ArrayList::add, ArrayList::addAll);
}
}
And, in Haskell:
fizzBuzz :: [Integer] -> [String]
fizzBuzz = map fizzLogic
fizzLogic :: Integer -> String
fizzLogic i =
if i `mod` 3 == 0 && i `mod` 5 == 0 then
"FizzBuzz"
else if i `mod` 3 == 0 then
"Fizz"
else if i `mod` 5 == 0 then
"Buzz"
else
show i
Alas! Now that we’re back to a single expression, we have to consider all the cases again as single if blocks.
The Java implementation is nicer! What gives?!
Well, hlint is telling us to refactor that to use guards rather than if, so let’s do that and see if anything jumps out at us.
fizzLogic :: Integer -> String
fizzLogic i
| i `mod` 3 == 0 && i `mod` 5 == 0 = "FizzBuzz"
| i `mod` 3 == 0 = "Fizz"
| i `mod` 5 == 0 = "Buzz"
| otherwise = show i
Now that it’s laid out like this… I think I see a pattern! Let me align it a little differently:
fizzLogic :: Integer -> String
fizzLogic i
| i `mod` 3 == 0 && i `mod` 5 == 0 = "Fizz" ++ "Buzz"
| i `mod` 3 == 0 = "Fizz" ++ ""
| i `mod` 5 == 0 = "" ++ "Buzz"
| otherwise = show i
Do you see it? It’s one of our favorite things: a monoid! Actually, it’s a whole bunch of monoids.
A monoid is a neat little idea from abstract algebra that shows up almost everywhere. A monoid is a collection of three things:
Boolean values and && form a monoid, where the set is {True, False}, the operation is &&, and the identity is True.
Strings and ++ form a monoid, where "" (the empty string) is the identity element.
Integers, +, and 0 form a monoid, as do the integers, *, and 1.
They’re everywhere!
Getting back to fizzing and buzzing, let’s codify the general form of the rule. We get an integer, and we might return a string. If we return multiple strings, we concatenate them all. If we don’t, then we just print the number.
We seem to have a set of rules that may or may not fire. If more than one rule fires, we combine the results of the rule. If none fire, then we need a default value.
Let’s represent this in Haskell:
type FizzRule = Integer -> Maybe String
rule :: Integer -> String -> FizzRule
rule n m i =
case i `mod` n of
0 -> Just m
_ -> Nothing
fizz = rule 3 "Fizz"
buzz = rule 5 "Buzz"
Alright, so now we have a [FizzRule].
How do we use that?
There are quite a few neat things we can do.
sequence is a promising candidate:
sequence :: Monad m => [m a] -> m [a]
-- or, the more generic:
sequenceA :: (Applicative f, Traversable t)
=> t (f a) -> f (t a)
As it happens, a -> b forms a monad and an applicative!
So we if specialize sequence to functions (and then again to Integer -> Maybe String), we get:
sequence :: [a -> b] -> (a -> [b])
sequence :: [Integer -> Maybe String] -> Integer -> [Maybe String]
This is pretty close!
Now we want to combine the [Maybe String] into a Maybe [String].
This is, again, sequence, since Maybe is a monad.
Finally, we want to concatenate those inner strings.
We can use fmap over the Maybe with mconcat:
mconcat :: Monoid m => [m] -> m
combineRules :: [Integer -> Maybe String] -> Integer -> Maybe String
combineRules rules i = fmap mconcat (sequence (sequence rules i))
Nice! This kind of polymorphic power is what’s so neat about Haskell. Those type classes are doing a bunch of work for us under the hood, and we don’t really have to worry about it.
What if I told you a lot of that work was unnecessary? We can punt almost all of this to our fancy monoid instances with a single function:
fold :: (Foldable t, Monoid m) => t m -> m
Here’s where things get fun:
fizzBuzz :: [FizzRule] -> [Integer] -> [String]
fizzBuzz rules = map f
where
f i = fromMaybe (show i) (ruleSet i)
ruleSet = fold rules
The magic happens in fold rules.
Let’s inspect the type signature of fold:
fold :: (Foldable t, Monoid m) => t m -> m
We’ve got a [FizzRule] or [Integer -> Maybe String].
So Foldable t ~ [] and Monoid m ~ Integer -> Maybe String.
The monoid instance that comes into play here is:
instance Monoid m => Monoid (a -> m) where
mempty = const mempty
mappend f g = \x -> f x `mappend` g x
So we require yet another monoid instance for the result of the function. The instance that comes into play here is:
instance Monoid a => Monoid (Maybe a) where
mempty = Nothing
mappend (Just a) (Just b) = Just (mappend a b)
mappend (Just a) Nothing = Just a
mappend Nothing (Just a) = Just a
mappend Nothing Nothing = Nothing
Along with the Monoid instance for String, which is mappend = (++) and mempty = "".
So we’ve folded three levels of Monoidal structure together.
All that work came for free with the fold function.
Note that we’ve come across a really powerful concept here: fold rules can be used to take a bunch of distinct rules, run them across the same input, and collect their responses.
Fizzbuzz is a somewhat trivial implementation, but the generalized concept is really useful.
If you’re feeling frisky, you can get a little more type class magic going by using the Functor and Applicative instance for functions. This lets us write:
fizzBuzz :: (Functor f, Foldable t)
=> t (Integer -> Maybe String)
-> f Integer
-> f String
fizzBuzz rules = fmap (fromMaybe <$> show <*> ruleSet)
where
ruleSet = fold rules
What?
The Functor instance for functions is just function composition.
Compare the type signature of (.) :: (b -> c) -> (a -> b) -> (a -> c) with:
instance Functor ((->) r) where
fmap :: (a -> b) -> (r -> a) -> (r -> b)
fmap f g = f . g
Now, we get to the Applicative instance…
instance Applicative ((->) r) where
pure = const
f <*> g = \x -> f x (g x)
The pattern f <$> g <*> h with explicit parentheses is (f <$> g) <*> x.
When we expand that out, we get \x -> f (g x) (h x), which is how we get fromMaybe <$> show <*> ruleSet.
I don’t know about you, but when I was working on this, my brain just about exploded. There’s one last fun bit of abstract nonsense…
The joke in functional programming is:
“A monad is just a monoid in the category of endofunctors, what’s the problem?”
Everyone laughs because wait what. But – as it happens, we get a little bit of a hint as to the deeper meaning!
The Foldable class is the toFreeMonoid class.
One of the member functions is foldMap:
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
which maps each element of the structure to a monoid and then mappends them all together into a final monoid value.
Now, suppose we specialize foldMap such that Foldable t ~ [] and Monoid m ~ [b]… This is the resulting signature:
foldMap :: (a -> [b]) -> [a] -> [b]
Which should look really familiar: that’s very nearly the type signature of >>=!
In fact, that’s precisely the type signature of =<< specialized to lists:
-- or :: (a -> [b]) -> [a] -> [b]
(=<<) :: (a -> m b) -> m a -> m b
(=<<) = flip (>>=)
Fizzbuzz has a neat monoidal solution that directly relates to rules engines. I accidentally discovered another neat connection between monoids, folds, and monads. You never know where this kind of thing might take you!