Continuing in the vein of cool Haskell examples I find on the internet, this post is going to be about a particularly epic fizzbuzz implementation that I saw in a three-year-old Reddit thread. Now, the OP in that thread had a serviceable but run of the mill fizzbuzz implementation, but what caught my eye was the top-voted comment. The author (who has since, sadly, deleted their account, or I would have credited them here) had accomplished fizzbuzz in a mere 2 lines of code! Here is the snippet copied verbatim:
let (m ~> str) x = str <$ guard (x `mod` m == 0)
in map (fromMaybe . show <*> 3 ~> "fizz" <> 5 ~> "buzz")
Seeing this was one of those moments where you just say “oh man, I have to understand how this works!”. Luckily there were a few people in that thread who had already hashed out explanations, so I could already get the gist of what was going on. This post is going to be an attempt to explain the above two lines to myself.
Let’s go
The fizzbuzz two-liner is a single expression with a let binding that defines
an operator called ~>. We shall put the let binding to one side for the
moment and concentrate just on the core expression:
map (fromMaybe . show <*> 3 ~> "fizz" <> 5 ~> "buzz")
OK so we’re using the function map, which has the signature map :: (a -> b) -> [a] -> [b], and we’ve applied it to a single argument, meaning that the
bit in parentheses must be a function a -> b. Now, the core of fizzbuzz is all
about turning integers into strings (arbitrary integers into their string
representation, multiples of 3 into “fizz” etc.) so we can probably assume that we
will be mapping over a list of integers and producing a list of strings.
We can test this hypothesis by loading the two-liner into GHCi (We have to add the imports – which I got by hoogling the function names that GHCi didn’t know about).
λ> import Control.Monad (guard)
λ> import Data.Monoid ((<>))
λ> import Data.Maybe (fromMaybe)
λ> let (m ~> str) x = str <$ guard (x `mod` m == 0)
λ> let core = (fromMaybe . show <*> 3 ~> "fizz" <> 5 ~> "buzz")
λ> :t core
core :: (Show a, Integral a) => a -> String
This seems to check out; the type signature looks a bit weird because Haskell
derives the most general signature it can, but we can interpret it as core :: Integer -> String.
From abstract to concrete
Ok, so now we’re going to start from the core expression (adding clarifying
parentheses):
(fromMaybe . show) <*> (3 ~> "fizz" <> 5 ~> "buzz")
Let’s analyse this from the outside in by first looking at the types of the
arguments on either side of the <*>:
λ> :t (fromMaybe . show)
fromMaybe . show :: Show a => a -> Maybe String -> String
λ> :t (3 ~> "fizzbuzz" <> 5 ~> "buzz")
... :: (Alternative f, Integral a) => a -> f String
Hmm, the first one is kind of understandable, but the second one is still quite
abstract. In order to make this more concrete we could try to glue these pieces
together with <*>. Let’s remind ourselves of the signature for <*>:
λ> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
Now we have all the ingredients; let’s try and match the type signatures for
the previous expressions with the (very abstract) one for <*>:
f (a -> b) -> f a -> f b
a' -> (Maybe String -> String) -> a' -> f' String -> a' -> String
So the Applicative structure f matches up with the a' ->, and the f'
matches up with the Maybe. Given that we know that the whole combination needs
to give something of type Integer -> String, this fixes the type of a' in
the above to be “a function that takes an integer”.
Just to make things crystal clear let’s rewrite the signatures for the two sub-expressions using the concrete types that we managed to deduce:
(fromMaybe . show) :: Integer -> Maybe String - String
(3 ~> "fizz" <> 5 ~> "buzz") :: Integer -> Maybe String
This is pretty cool; by combining several expressions that individually have very abstract types we’ve managed to deduce concrete types for these expressions!
We can also see that by using <*> we’re using the Applicative instance of
functions to elide the Integer parameter to the two sub-expressions. We
could rewrite core like so:
core n = fromMaybe (show n) $ (3 ~> "fizz" <> 5 ~> "buzz") n
which is, in my opinion, more explicit but much less readable!
Down the layers
Now that we have these concrete types we can start understanding how everything fits together.
fromMaybe has signature a -> Maybe a -> a; it takes a default value, a
Maybe value and returns the default value if the Maybe is Nothing. In code:
fromMaybe a (Just b) = b
fromMaybe a Nothing = a
In core the default value is show n, where n
is the number we’re fizz-buzzing. This makes sense, as if n is not divisible
by 3 or 5 then we should show just the number itself.
We can therefore see that 3 ~> "fizz" <> 5 ~> "buzz" takes n and should
return Nothing if n is not divisible by 3 or 5, and Just "something"
otherwise.
Given this, it kind of makes sense if we can first look at 3 ~> "fizz" in
isolation. If we look at the type signature for <>:
λ> :t (<>)
(<>) :: Monoid m => m -> m -> m
we see that it takes two things of type m and produces a third thing of the
same type. We can therefore deduce that the type of 3 ~> "fizz" is the same as
the whole expression 3 ~> "fizz" <> 5 ~> "buzz", and is therefore Integer -> Maybe String.
To understand how 3 ~> "fizz" works we’ll first have to look at the definition
of ~> again:
(m ~> str) x = str <$ guard (x `mod` m == 0)
Ok, the last bit, x `mod` m == 0, is clearly checking whether x is
divisible by m. Let’s look at the signatures of <$ and guard:
λ> :t (<$)
(<$) :: Functor f => a -> f b -> f a
λ> :t guard
guard :: Alternative f => Bool -> f ()
Ok, so <$ seems to take two arguments, the second one being a functorial one,
and returns the first value in the functorial context of the second value. If I
had to guess I would say that it’s implemented like so:
a <$ fb = fmap (const a) fb
or, in point free style:
(<$) = fmap . const
Looking at the definition of ~> again we can see that the expression evaluates
to str put into the functorial context of guard (x `mod` m == 0). What the hell does that mean?
Once again we’re getting hit by the fact that the type signatures of the individual pieces are too general; we need to put stuff back into context and “match up the types” to understand what is really going on.
We know that str <$ guard (x `mod` m == 0) must have type Maybe String,
and we know that str has type String and guard returns an f () where f
is some functor (Alternative being a subclass of Functor). We can therefore
see that guard (x `mod` m == 0) must therefore have type Maybe (). This
means that the only values this expression can have are Just () and Nothing.
Combined with the <$ we can therefore see that (m ~> str) x evaluates to
Just str when m divides x, and Nothing otherwise.
Down, down, down
So now we’ve understood that layer of structure, let’s see if we can
understand the combination 3 ~> "fizz <> 5 ~> "buzz. Because we’ll be
referring to this thing a few times, I’m going to give it the name buzzer, so
buzzer :: Int -> Maybe String
buzzer = 3 ~> "fizz" <> 5 ~> "buzz"
The expressions on either side of the <> are functions from Integer to
Maybe String. <> is defined as follows between functions:
(f <> g) x = f x <> g x
so clearly for this to work f and g must have the same signature, and
the return value must itself be a monoid. We know that f and g return
Maybe String for our case. Maybe is indeed a monoid if the thing that
it contains is also a monoid; we just identify Nothing with the monoidal
identity for the contained values and we’re done. String is, of course,
a monoid with the empty string as its identity element and concatenation
as its <>.
Putting all this together we can see how buzzer actually
works. We can explicitly treat each case: not divisible by 3 or 5, divisible
by either 3 or 5, divisible by both 3 and 5.
When we apply buzzer to a number that is neither divisible by 3 nor by 5
then both of the subexpressions evaluate to Nothing and we get
Nothing <> Nothing, which is just Nothing. In the second case we get
either Just "fizz" <> Nothing or Nothing <> Just "buzz", which evaluate
to Just "fizz" and Just "buzz" respectively (thanks to the monoid on
Maybe). In the final case we get Just "fizz" <> Just "buzz", which
evaluates to Just ("fizz" <> "buzz") which is Just "fizzbuzz".
Putting it all together
Now comes the question of how we would rewrite this fizzbuzz so that it’s easier to understand. On one hand we want to use abstraction to help us reveal the actual structure of the problem (without getting bogged down in the messy details) and on the other hand we don’t want to abstract into the stratosphere so that it’s no longer clear what our intention is.
My compromise would probably look something like this:
import Control.Monad (guard)
import Data.Monoid ((<>))
import Data.Maybe (fromMaybe)
(m ~> str) x = if x `mod` m == 0
then Just str
else Nothing
fizz_or_buzz :: Integer -> Maybe String
fizz_or_buzz =
3 ~> "fizz"
<> 5 ~> "buzz"
fizzbuzz :: Integer -> String
fizzbuzz = fromMaybe <$> show <*> fizz_or_buzz
main = traverse putStrLn $ map fizzbuzz [1..100]
Essentially I made the following changes:
- I preferred an explicit ‘if-then-else’ over the use of
guardand<$, but did not apply a type signature to~>as I feel it would obscure, rather than clarify, meaning. - I put an explicit type signature on the piece that handles the fizzing and buzzing, but kept the abstract monoidal composition. I think that even if someone is not 100% clear on how all the monoid instances interact, the signature and definition make it obvious what this piece is doing. In addition the formatting makes it easy for someone else to modify the code, say to add printing of “baz” if the number is divisible by 7, or to reverse the order of “fizz” and “buzz”.
- I prefer using applicative style for both of the arguments for
fromMaybe; In my opinion this clarifies intent drastically.
So in the end we have not actually changed too much: the code still works in essentially the same way; I just clarified intent by adding explicit names to things, adding type signatures, and using explicit language features as opposed to what I consider excessive abstract logic.
Of course, the changes I made are coming from a place of ignorance; I am a
total Haskell noob, so the things that are not obvious to me could well be
obvious for a Haskell veteran. For example, the fact that I chose to keep the
fromMaybe <$> show <*> fizz_or_buzz is due to the fact that I understand and
know how to use the applicative instance of functions; maybe if I had more
experience using guard and <$ I would find the initial two-liner clearer
than my explicit ‘if-then-else’. I guess only time will tell.
Thoughts
Spaghetti
People complain about object oriented programming because when you make a method call you have no idea what code is actually getting called (‘cause dynamic dispatch + having to follow the object’s method resolution order). I would posit that finding the definition of any of the functionality defined in a typeclass is the same thing. From a function definition it is sometimes impossible to know what code will actually be run because it can depend on the type of the arguments; you need to go to the call site to find out what will happen.
In addition, I find that the abstract level at which Haskell operates sometimes
confuses more than it helps. Even though a a -> b and Maybe a both have
monoid instances, the meaning is totally different for the two. In my opinion
this is a case where treating things too generally can actually obscure meaning.
Work from the outside in
I found that the complexity from overgeneralising can be combated by working top-down. You first need to figure out the type of the top-level/outermost expression and work inwards. If you start out trying to understand the types for the constituent expressions, often they will be to general for you to be able to understand why they are being used in the first place.
By starting from the outermost expression you can apply the technique of “matching up the types” to figure out what is going on one layer down, and then carry on recursively like this until you have the concrete types for the innermost expressions.
Is there such a thing as being too general?
Abstraction is in some sense the essence of programming computers. It allows us
to see the forest instead of the trees and often enables thinking about
problems in a more fruitful way, i.e. closer to the domain in which the problem
was originally defined. Many languages define abstract (as opposed to concrete)
concepts. Python (my go-to language) has the concept of a sequence, an
iterable, a mapping etc. These are all useful concepts, as they signal
intent; we can define an algorithm that works on any iterable, and this
gives us the freedom to pass it an array, linked list, or anything else that can
be iterated over. Someone reading the algorithm doesn’t need to care about the
actual type that is passed in to understand what is going on.
Haskell takes this 1 step further with Functor, Applicative and Monad, and
I am yet to be convinced that this is actually useful for a wide variety of
cases. Even if Maybe and List can both formally be considered as applicative
functors, the applicative instances for these two types means totally different
things. Maybe represents computations that can fail, whereas the List
Applicative instance represents all possible combinations of the provided
computations. If I write some code that does something with a general
Applicative, I don’t really know what the code means before I apply it to
concrete types. This means that even if I can formulate an algorithm using
only Applicative, naming this thing sensibly is going to be a real
challenge.
On the other hand, some very smart people clearly think that thinking at this level of abstraction does produce better software, and I am still very new to Haskell and functional programming in general. I would really like to see a good set of concrete examples that show how abstracting into the stratosphere like this is actually beneficial and produces code that is more maintainable.