This is just a quick story about something that happened last night while I was attempting to teach a friend a bit of what I’d learned about FP/PureScript so far. We decided to implement the infamous FizzBizz Interview question.
If you’re not sure what FizzBuzz is, you just count from 1 to 100 (or any range really) with some special rules. Here’s what the basic thing looks like:
The Immediate Solution
This is (in my view) the best solution given the task FizzBuzz puts before you. It’s quick to develop, easy to understand, and unlikely to have errors. If asked this question in an interview, I would do this.
main :: Effect Unit
main = for_ (range 1 100) \n -> log $ fizzBuzz n
isMultipleOf :: Int -> Int -> Boolean
isMultipleOf dividend divisor = dividend `rem` divisor == 0
fizzBuzz :: Int -> String
fizzBuzz n
| n `isMultipleOf` (3 * 5) = "FizzBuzz"
| n `isMultipleOf` 3 = "Fizz"
| n `isMultipleOf` 5 = "Buzz"
| otherwise = show n
Some of the output:
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
... ect
A Problem Going Forward
The above solution is great for a simple problem, but what happens when the rules of FizzBuzz are extended. Maybe we want to do something with multiples of 7 and 13 as well?
fizzBuzzExt :: Int -> String
fizzBuzzExt n
| n `isMultipleOf` (3 * 5 * 7) = "FizzBuzzPazz"
| n `isMultipleOf` (3 * 5 * 13) = "FizzBuzzBoop"
| n `isMultipleOf` (5 * 7 * 13) = "BuzzPazzBoop"
| n `isMultipleOf` (3 * 5) = "FizzBuzz"
| n `isMultipleOf` (3 * 7) = "FizzPazz"
| n `isMultipleOf` (3 * 13) = "FizzBoop"
| n `isMultipleOf` (5 * 7) = "BuzzPazz"
| n `isMultipleOf` (5 * 13) = "BuzzBoop"
| n `isMultipleOf` (7 * 13) = "PazzBoop"
| n `isMultipleOf` 3 = "Fizz"
| n `isMultipleOf` 5 = "Buzz"
| n `isMultipleOf` 7 = "Pazz"
| n `isMultipleOf` 13 = "Boop"
| otherwise = show n
Did I leave one out? Is that right? This is probably gonna take quite a few tests passing before I’m confident.
What we’d rather do is sort of build the string incrementally:
fizzBuzzExt :: Int -> String
fizzBuzzExt n = e
where
a = if n `isMultipleOf` 3 then "Fizz" else ""
b = if n `isMultipleOf` 5 then a <> "Buzz" else a
c = if n `isMultipleOf` 7 then b <> "Pazz" else b
d = if n `isMultipleOf` 13 then c <> "Boop" else c
e = if length d > 0 then d else show n
This is much better and perhaps it’s worth leaving this here, but there’s a pattern in there that can be extracted. Each bit of the string is (maybe) built relative to what came before and nothing else. This sort of feels like function composition.
Lone behold!
modTag :: Int -> String -> Int -> String -> String
modTag divisor tag dividend acc =
if dividend `rem` divisor == 0 then acc <> tag else acc
fizzBuzzExt :: Int -> String
fizzBuzzExt n = if length strn > 0 then strn else show n
where
strn = "" # (modTag 3 "Fizz" n)
>>> (modTag 5 "Buzz" n)
>>> (modTag 7 "Pazz" n)
>>> (modTag 13 "Boop" n)
Now we’re just abstracting for the sake of it, but we’ve come this far and it seems there must be some way to un-boilderplate the passing of the dividend to modTag. It’s always the same so matter what.
There’s actually two ways that came to us. The first is just to use partial application. We have to redefine modTag to take the dividend first.
modTag :: Int -> Int -> String -> String -> String
modTag dividend divisor tag acc =
if dividend `rem` divisor == 0 then acc <> tag else acc
fizzBuzzExt :: Int -> String
fizzBuzzExt n = if length strn > 0 then strn else show n
where
becomes = modTag n
strn = "" # (3 `becomes` "Fizz")
>>> (5 `becomes` "Buzz")
>>> (7 `becomes` "Pazz")
>>> (13 `becomes` "Boop")
This looks nice again, but sadly we haven’t really fixed the underlying problem. So long as all we want to do is compute modTags, we’re good, but if we want a variety of computations then we’re back to the same situation of applying n to each function.
-- if n is a prime number, append "Prime" to the given string
primeTag :: Int -> String -> String
primeTag n acc = ...
-- if n is less than 10, append "Small" to the given string
smallTag :: Int -> String -> String
smallTag n acc = ...
fizzBuzzExt :: Int -> String
fizzBuzzExt n = if length strn > 0 then strn else show n
where
becomes = modTag n
primes = primeTag n
smalls = smallTag n
strn = "" # smalls
>>> primes
>>> (3 `becomes` "Fizz")
>>> (5 `becomes` "Buzz")
>>> (7 `becomes` "Pazz")
>>> (13 `becomes` "Boop")
Upgrading Compose
So how do we solve this more convincingly? We need to move away from function composition and create another way to call functions. One that passes the dividend to any function so long as it has the right general shape. While still letting each step build our string.
So maybe we can package up our functions in a list and create a higher-order function that will compose them all together for us.
modTag :: Int -> String -> String -> Int -> String
modTag divisor tag acc dividend =
if dividend `rem` divisor == 0 then acc <> tag else acc
defaultNum :: String -> Int -> String
defaultNum acc n = if length acc > 0 then acc else show n
composeAndRun :: Array (String -> Int -> String) -> Int -> String
composeAndRun fns n = foldl (\acc fn -> fn acc n) "" fns
fizzBuzzExt :: Int -> String
fizzBuzzExt = composeAndRun
[ modTag 3 "Fizz"
, modTag 5 "Buzz"
, modTag 7 "Pazz"
, modTag 13 "Boop"
, defaultNum
]
Now we can compose defaultNum with modTag, but also we could create primeTag or smallTag and throw them in there without issue too.
This is the final implementation that we decided was enough.
Finally, The Reader Monad
Here’s the thing. If you squint at what we did, you might notice that we’re basically composing functions with some constant state that each function has access to.
This is a bit uglier, but this is what the above implementation looks like if we use the Reader monad explicitly:
modTag :: Int -> String -> String -> Reader Int String
modTag divisor tag acc = do
dividend <- ask
pure $ if dividend `rem` divisor == 0 then acc <> tag else acc
defaultNum :: String -> Reader Int String
defaultNum acc = do
n <- ask
pure $ if length acc > 0 then acc else show n
composeAndRun :: Array (String -> Reader Int String) -> Int -> String
composeAndRun fns = case fromArray fns of
Nothing -> \n -> show n
Just (someFns) -> runReader $ "" # foldl (>=>) (head someFns) (tail someFns)
fizzBuzzExt :: Int -> String
fizzBuzzExt = composeAndRun
[ modTag 3 "Fizz"
, modTag 5 "Buzz"
, modTag 7 "Pazz"
, modTag 13 "Boop"
, defaultNum
]
And that is how we accidentally got most of the way to creating out own Reader Monad.
All while solving a basic interview-style question.
