Fizz Buzz in Haskell

Question

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?

Answer 1

*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.}

Answer 2

While I agree that using Data.Map is overkill, your solution is quite compact and easy to follow. My solution (working with the constraints that only core libraries should be used and the list of strings and conditions on those strings should be extensible) is nearly twice as long - I produced a list for each condition containing an empty list if the condition failed or a list containing its string if it succeeds, i.e. it worked the opposite way around the matrix of possible strings to your solution. This turned out to be more complex, and required the transpose function that is unfortunately note in the Prelude (which I had been hoping to stick to):

import Data.List (transpose)

divisibleBy :: Int -> Int -> Bool
divisibleBy d n = n `mod` d == 0

wordPicker :: [Int] -> (String,Int->Bool) -> [[String]]
wordPicker numbers (str, condition) =
    ([str] <*) <$> filter condition <$> pure <$> numbers

fizzbuzz :: [(String,Int->Bool)] -> [Int] -> [String]
fizzbuzz definitions numbers =
    concat <$> zipWith defaultOnEmpty mergeWords numbers
    where 
      mergeWords = concat <$> transpose wordLists
      wordLists = wordPicker numbers <$> definitions
      defaultOnEmpty [] n = [show n]
      defaultOnEmpty ws _ = ws

main :: IO ()
main = putStrLn $ unwords $ fizzbuzz
            [("Fizz", divisibleBy 3), ("Buzz",divisibleBy 5)]
            [1..100]

I think your approach is clearly better. What I do like about my solution compared to yours is the use of a divisibleBy function rather than messing around with lambdas when filtering the lists, and putting the filter predicates in the list of words rather than the factor that they require, which makes the solution more general.