Fizz Buzz in Haskell

Pretty straightforward, I implemented the popular fizz buzz challenge in Haskell.

import qualified Data.Map as M

factorWords = M.fromList [(3, "fizz"), (5, "buzz")]

factors :: Int -> [Int]
factors x = filter (\y -> x `mod` y == 0) factorKeys
    where factorKeys = M.keys factorWords

fizzbuzz :: Int -> String
fizzbuzz x = if null fs then show x
                        else concatMap ((M.!) factorWords) fs
    where fs = factors x

main = mapM_ (putStrLn . fizzbuzz) [1..100]

I'm guessing people are going tell me that using Data.Map and concatMap is overkill for a program of this size and complexity, but it seemed the most natural way to do it in Haskell for whatever reason. Any advice, particularly regarding my use of data structures?

ahem Data.Map is an overkill for this program. It needs the containers package. Also, if a number is divisible by \$k\$ of your \$K\$ divisors, your algorithm is \$\mathcal O(K + k \log K)\$ (*), so worst case (\$K = k \$) you will have \$\mathcal O(K \log K) \$.

This is due to the definition of factors. Compare your factors with the following variant:

factors' :: Int -> [(Int, String)]
factors' x = filter (\(y,_) -> x `mod` y == 0) factorPairs
  where factorPairs = M.toAscList factorWords

It's almost the same, and has the same algorithmic complexity as your previous factors, namely \$\mathcal O(K)\$. But this time, you're getting more information from a single function: you can define both factors and fizzbuzz in terms of factors', without using the original map/list anymore:

factors :: Int -> [Int]
factors = map fst . factors'

fizzbuzz :: Int -> String
fizzbuzz x = case concatMap snd (factors' x) of 
               [] -> show x
               xs -> xs
-- feel free to use your "where style" here instead

As you can see, a list of pairs is enough to capture everything, since you're going to traverse all of them either way. It also leads to a complexity of \$\mathcal O(K)\$ (*). If you're concerned about the order of elements, a single Data.List.sort at the original definition can help.

However, even this might be an overkill if you never intend to increase the number of factors. If all you want to do is to solve fizzbuzz, you can drop down to a guard solution:

fizzbuzz :: Int -> String
fizzbuzz x
  | isDivisibleBy 15 = "FizzBuzz"
  | isDivisibleBy  5 =     "Buzz"
  | isDivisibleBy  3 =     "Fizz"
  | otherwise        =     show x
 where isDivisibleBy n = x `rem` n == 0

Which beats all other discussed solutions in terms of complexity and clarity.

(*) Only counting filter and lookup, not actual concatenation.

StackExchange Code Review Q#121515, answer score: 2