FizzBuzz

FizzBuzz is a cut-down version of Eratosthenes’ sieve, which started as a drinking game and is now often used as an interview question.

The rules are that you start counting, and replace numbers by Fizz if they are divisible by three, Buzz if they are divisible by five, and FizzBuzz if divisible by both.

The key is to avoid calculating modulus/remainder, for a few overlapping reasons:

  1. Division is an expensive operation for computers as well as humans
  2. If you know (n-2) mod 3 and (n-1) mod 3, you do not need arithmetic to calculate n mod 3.
  3. It is overkill to use arithmetic for a problem that can be solved with category theory.

In this program, I use circular linked lists.

newtype FizzBuzz = FizzBuzz (Maybe String,Int)
instance Show FizzBuzz where
  show (FizzBuzz (Just s,_)) = s
  show (FizzBuzz (Nothing,i)) = show i  

main :: IO()
main = mapM_ putStrLn $ fizzBuzz 150

fizzBuzz :: Int -> [String]
fizzBuzz n = map (show . FizzBuzz) $ zip noises [1..n] 

noises :: [Maybe String]
noises = tail $ foldr1 (zipWith mappend) (map wheel substitutions)  

substitutions :: [(Int, String)]
substitutions = [(3,"Fizz"),(5,"Buzz"),(7,"Crash"),(11,"Bang"),(13,"Wallop")] 

wheel :: (Int, a) -> [Maybe a]
wheel (modulus,noise) = cycle $ take modulus $ (Just noise) : (repeat Nothing)

It is a little over-complicated to make FizzBuzz an instance of Show, instead of just writing the show function, but I think it makes the intention clear.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: