Project Euler #1 using Haskell

4
votes
import Data.Set

euler :: Int
euler = sum [ x | x <- nums ]
    where
    nums = Data.Set.toList (Data.Set.union (Data.Set.fromList [3,6..999])
                                           (Data.Set.fromList [5,10..999]))

I am learning Haskell and hope you don't mind me asking this. Is there a nicer way to get a list holding all natural numbers below one thousand that are multiples of 3 or 5? (E.g. with zip or map?)

Edit:

import Data.List

euler :: Int
euler = sum (union [3,6..999] [5,10..999])

Thanks for your help, guys.

7
haskell
data-ordlist:Data.List.Ordered.union; also, [x | x <- nums] is better spelled nums. - Daniel Wagner
First it looked ugly, now I feel stupid... euler = sum (union [3,6..999] [5,10..999]) works. Thanks, guys. - user1602492
No, Data.List.union is inefficient, of quadratic time complexity. - Will Ness

7 Answers

15
votes

Use list comprehension: 

sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]
10
votes

You could go with the hardcoded version too:

sum $ [3, 6 .. 999] ++ [5, 10 .. 999] ++ [-15, -30 .. -999]
8
votes

This will give you the list you asked for:

filter (\x -> (x `mod` 3 == 0) || (x `mod` 5 == 0)) [1..999]
5
votes

Here's one.

mults35 = union [3,6..999] [5,10..999]
  where
    union (x:xs) (y:ys) = case (compare x y) of 
       LT -> x : union  xs  (y:ys)
       EQ -> x : union  xs     ys 
       GT -> y : union (x:xs)  ys
    union  xs     []    = xs
    union  []     ys    = ys

Here's another, less efficient way:

import Data.List

nub . sort $ ([3,6..999] ++ [5,10..999])

(we don't have to use fully qualified names if we have the import statement).

Also interesting is to find the multiples of only 3 and 5:

m35 = 1 : (map (3*) m35 `union` map (5*) m35)
2
votes
sum [x | x <- [1..999], let m k = (x`mod`k==0), m 3 || m 5]
1
votes

A more general solution for a list of numbers instead of just 3 and 5:

addMultiples :: [Int] ->  Int -> Int
addMultiples multiplesOf upTo = sum[n | n <- [1..upTo-1], or (map ((0==) . mod n) multiplesOf)]
1
votes

Here's one that is super-fast. Try it with values of over a billion.

eu x = sum[div (n*(p*(p+1))) 2 | n<-[3,5,-15], let p = div (x-1) n]

I imagine it can be shortened further.