FibFizzBuzz.hs

#!/usr/bin/env runhaskell
import qualified Data.Map as M
import Test.QuickCheck

fibs :: [Int]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

primes = sieve [2..] M.empty
  where
    sieve [] iterators = []
    sieve (n:ns) iterators =
      case M.lookup n iterators of
        Nothing -> n : (sieve ns $ M.insert (n*n) [n] iterators)
        Just primesToIterate ->
          let reinsertIncrement iterators increment =
                M.insertWith (++) (n+increment) [increment] iterators
              withCurrentRemoved = M.delete n iterators
              updatedTable = foldl reinsertIncrement withCurrentRemoved primesToIterate
          in sieve ns updatedTable

isPrime n =
  -- XXX: this could be implemented as a binary search if performance were a concern
  elem n $ take (findBound 1) primes
  where findBound index =
          if primes !! index > n then index else findBound $ index * 2

fizzBuzz i
  | i == 0 = show i
  | i `mod` 15 == 0 = "FizzBuzz"
  | isPrime i = "BuzzFizz"
  | i `mod` 5 == 0 = "Fizz"
  | i `mod` 3 == 0 = "Buzz"
  | otherwise = show i

fibsBuzz = map fizzBuzz fibs

-- I would usually put tests in a different file, but since we can only provide
-- a gist, I'll write them here

-- quickCheck ((\i -> fibs !! i + fibs !! i + 1 == fibs !! i + 2) :: Int -> Bool)

-- quickCheck ((\i -> not $ isPrime i * 2) :: Int -> Bool)

main = mapM_ putStrLn $ take 40 fibsBuzz