Quick Followup


Quick Follow Up on FizzBuzz

Not too long ago, my old FizzBuzz post made it back onto Hacker News. Amongst the predictable noise about how I was overcomplicating things, a bunch of fun chatter emerged.

It’s really fun revisiting a blog post you wrote (and code you wrote) years ago. You get to go back and recognize not only how the community has evolved (around your code and responses to your blog) but also how your thinking has evolved as well.

After thinking on it, I was commenting on twitter about how I need to watch for opportunities to use the “Applicative instance of Reader” a lot more, particularly when it’s (->) a. Some folks found this tweet somewhat cryptic and asked me to expand on it.

I figured the best way to do that was to pick up on where I left off: FizzBuzz.

When last we left our hero, our code looked something like this:

{-# LANGUAGE MonadComprehensions, OverloadedStrings #-}

module Main where
import Prelude hiding (putStrLn)
import Data.Maybe (fromMaybe, listToMaybe, maybe)
import System.Environment (getArgs)
import Data.Text
import Data.Text.IO

fizzbuzz d i = fromMaybe (d i) $
                 ["fizz" | i `rem` 3 == 0] <>
                 ["buzz" | i `rem` 5 == 0] <>
                 ["bazz" | i `rem` 7 == 0]

main = do
  upTo <- fmap (maybe 100 read . listToMaybe) getArgs
  mapM putStrLn [ fizzbuzz (pack . show) i | i <- [1..upTo] ]
  return ()

And this was pretty good, if somewhat anachronistic (we don’t use MonadComprehensions so much in 2017). One thing that’s changed with my thinking is that I’m a lot more keen on using typeclasses that intelligently propagate monoid constraints. This means reusing existing monoid constraints that piggyback on the assumption that part of your type is a monoid.

Probably the most pithy expression of this idea was offered by pja on a Hacker News post:

(~>) :: (Integral a) => a -> String -> a -> Maybe String
(n ~> str) i = str <$ guard (i `mod` n == 0)

fizzbuzz = 3~>"Fizz" <> 5~>"Buzz"

main = mapM_ putStrLn $ catMaybes $ fizzbuzz <$> [1..100] 

To be honest, I think I could probably do without the “~>” operator here. I know what pja’s alluding to here, but we hardly need Yet Another Single Use Operator. Still, we can’t deny the use of guard here is great. It’s actually mimicking exactly what the MonadComprehensions extension in the original example did without magical syntax.

Still, the real gem here is a perfect illustration of how Haskell’s community has embraced monoids and the structure they provide even more. Let’s just rewrite this to be slightly less compact:

factorNamed :: (Integral a) => a -> String -> a -> Maybe String
factorNamed n str i = do
    guard (i `mod` n == 0)
    return str

fizzbuzz :: (Integral a) => a -> Maybe String
fizzbuzz = (factorNamed 3 "Fizz") <> (factorNamed 5 "Buzz")

main = mapM_ putStrLn $ catMaybes $ fizzbuzz <$> [1..100] 

Note that in the FizzBuzz function we only apply 2 arguments to a 3 argument function, so currying we end up with two a -> Maybe String functions. But since String is a Monoid, we have a really nice monoid instance for reader and Maybe that actually says, “If you have two functions (Monoid b) => a -> b, we can combine them as a monoid by taking the output of both functions given an a, and combining those bs as a monoid.

Maybe itself has a monoid instance, which is then invoked to combine its contents if values are present on both sides of the <>. I know that some very smart folks sometimes express anxiety about how typeclasses sometimes end up overly magical, but in this case it’s really satisfying to watch the pair of type classes correctly fire and “do what we mean” by combining two a -> Maybe b expressions when b is a monoid. To me, this kind of powerful compiler intervention is one of the reasons I like Haskell.

Just to make it clear what’s going on in the original code with some type signatures from GHCi:

-- A single Squiggle function is a a -> Maybe String
> :t (3 ~> "Fizz")
(3 ~> "Fizz") :: Integral a => a -> Maybe String

-- Using <>, we expect another similar function to combine to produce
-- our final function.
> :t ((3 ~> "Fizz") <>)
((3 ~> "Fizz") <>) :: Integral a => (a -> Maybe String) -> a -> Maybe String

And we can all perform a polite golf clap here, I suppose. Good show, etc., right? But actually, this code doesn’t do what FizzBuzz is supposed to do; it doesn’t print out numbers if it doesn’t detect a prime factor. That’s where another poster offered a nice modification using the “Applicative nature of Reader:”

(~>) :: (Integral a) => a -> String -> a -> Maybe String
(n ~> str) i = str <$ guard (i `mod` n == 0)

fizzbuzz :: (Integral a) a -> Maybe String
fizzbuzz = 3~>"Fizz" <> 5~>"Buzz"

-- This is the only line that changed
main = mapM_ putStrLn $ map (fromMaybe . show <*> fizzbuzz) [1..100]

So that’s a big jump, but it’s not too bad. Instead of catMaybes we’re using something slightly different. We’re now using map to transform the list [1..100], and the function we’re passing to map is this slightly dense (fromMaybe . show <*> fizzbuzz). I want to break that down, because that’s actually a really solid pattern for Applicative functors.

The first thing to make clear, (fromMaybe . show <*> fizzbuzz) is taking a number and either writing a FizzBuzz word, or producing the string of that number. It’s the core logic of FizzBuzz. The second thing to notice is that this means that fromMaybe . show <*> transforms our fizzbuzz function into the final logic. It can do so because both fromMaybe . show and fizzbuzz share a common shape, called Reader.

Well let’s remind ourselves what Reader is real quick: Reader a b instances try to express the idea of “a computation which produces a b with the context of an a.” The most common Reader instance is actually just the function a -> b.

So let’s split this statement in half along the <*> (which is read as “apply” for those who don’t know):

> :t fromMaybe
fromMaybe :: a -> Maybe a -> a

> :t (fromMaybe . show)
(fromMaybe . show) :: Show a => a -> Maybe String -> String

-- <*> -- 

> :t fizzbuzz
fizzbuzz :: Integral a => a -> Maybe String

Squint for a moment, remove the leading a ->’s from the type signature. What do we have?

(Maybe String -> String) <*> (Maybe String)

If we call <*> by another name as “applied as a function with”, then we in fact just have a function receiving an argument here. These “functions” are actually Readers, we need to use a smarter kind of function application.

In other words, if we remove the leading context argument, this is a function application. But we can’t remove the leading argument because we need it to compute both values. That’s where the Applicative comes in.

What the Applicative <*> operator does is actually make a new function that takes an a, feeds that a to the left and right sides of itself, then tries to treat the left side result as a function, offering the right side result as an argument. We end up with a function that captures all the behavior we want in a simple type:

> :t fromMaybe . show <*> fizzbuzz
fromMaybe . show <*> fizzbuzz
  :: (Integral a, Show a) => a -> String

So the final value of connecting all that is a Maybe String that’s contingent upon having an a. We map that over all the numbers and that’s the entire logic of of FizzBuzz.

Re-interpreting functions as Applicatives or Monads (or even functions) is really powerful, and unfortunately it’s not something a lot of tutorials focus on despite the fact that it simplifies a lot of things. I’m trying to force myself to get better at it, and in several cases it’s allowed me to cut lots of superfluous code out and actually make my code clearer at the same time.

What I really like about this is that we interpret our FizzBuzz factor functions both as monoids AND as an applicative functor, each on different lines as we saw fit. The net result was safer, but I also submit that even if you might double take it when you really think about what just happed, the idea of what’s going on there is crystal clear. My eyes slid over it, just accepting it, a few times before I realized what a nice example it was.