[Haskell-cafe] how to optmize this code?

[Daniel Fischer]

On Wednesday 30 March 2011 16:39:49, Gilberto Garcia wrote:
> Hi Haskellers,
> 
> I was solving this problem from project euler to study haskell.
> I came up whit the following solution and I was wondering if there is
> a more optimized and concise solution.

Yes. There's a constant-time formula for summing the multiples of k <= a 
(those are [k, 2*k .. (a `quot` k) * k], 
so the sum is k* sum [1 .. (a `quot` k)], 
try to find a formula for sum [1 .. n]), then you need the
http://en.wikipedia.org/wiki/Inclusion–exclusion_principle

If you're looking for multiples of any of few numbers, it's very simple 
then. For longer lists (say you want to sum the multiples of any of 30 
numbers), you have to be clever implementing the inclusion-exclusion 
algorithm to keep the running time low, sometimes other methods may be 
faster then (fkSum (10^7) [2 .. 30] for example).

> 
> fkSum :: Int -> [Int] -> Int
> fkSum a [] = 0
> fkSum a (b) = foldl (+) 0 (filter (\x -> isMultiple x b) [1..a])
> 
> isMultiple :: Int -> [Int] -> Bool
> isMultiple a [] = False
> isMultiple a (x:xs) = if (mod a x == 0) then True else isMultiple a xs
> 
> Thanks in advance
> ggarcia