Project Euler #1 in Haskell

Question

Looking for feedback/critiques/alternatives to my solution for the 1st Project Euler question:

{-|
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3,5,6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
-}
import Data.List
-- Finds all multiples of a factor below set limit, by computing factor*n and adding to a list, until factor*n > limit
f_multiple :: [Int] -> Int -> Int -> Int -> [Int]
f_multiple multiples current limit factor
 | (current * factor) >= limit = multiples
 | otherwise = f_multiple (multiples ++ [current * factor]) (current + 1) limit factor
sum_multiples :: Int -> Int -> Int -> Int
sum_multiples max first_factor second_factor = foldr (+) 0 ( (f_multiple [] 0 max first_factor) `union` (f_multiple [] 0 max second_factor))

• WolfeFan: Project Euler #1 can be solved in constant time. Your solution is O(N). Hint: sum [1..n] == div (n * (n+1)) 2

Answer 1

There are several approaches to Project Euler Question 1. The one you have chosen is not particularly efficient, as it involves creating two lists, then merging them. I'm not going to present alternative solutions here. If you are going with this approach, you can write it much more simply:

sum_multiples :: Int -> Int -> Int -> Int
sum_multiples max factor1 factor2 = sum $ multiples1 `union` multiples2
 where
 multiples1 = [factor1, 2 * factor1 .. max - 1]
 multiples2 = [factor2, 2 * factor2 .. max - 1]

In particular,

• foldr (+) 0 is just the built-in sum function.
• f_multiple can be replaced with ranges.

In terms of style, your last line is hard to read due to its length. To shorten it,

• Use shorter variable names, e.g. factor1 instead of first_factor.
• Give names to complex subexpressions using a where clause.
• Use the $ operator to form a "pipeline", instead of nesting parentheses.

Answer 2

@200_success already gave you some nice tips pertaining your answer, so I'd like to present you an alternative:

pEuler1 :: Int
pEuler1 = sum[3, 6..999] + sum[5, 10..999] - sum[15, 30..999]

Add the sum of a list of multiples of 3 below 1000 with the sum of a list of multiples of 5 below 1000 and subtract the sum of a list of multiples of 15 to account for duplicates. Add those [1, 5..] kinds of range building to your toolbox because they're very handy!

Answer 3

I think your approach is more general and at least in my opinion slightly more complex than required. Here's my attempt:

sum [n | n <- [1..1000], n mod 3 == 0 || n mod 5 == 0]

I suppose I could pass in the "1000", "3" and "5" as parameters or even enable "n" number of filters to be passed. I think it would be an over-kill for this problem but a useful exercise :-)

• 200_success: Two problems. You need to write mod as an infix operator (n `mod` 3). Also, [1..999] would be more appropriate (even if it gives the same result), since the question says to consider numbers below 1000.