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:
- Division is an expensive operation for computers as well as humans
- If you know (n-2) mod 3 and (n-1) mod 3, you do not need arithmetic to calculate n mod 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.
Great Wall 