# Generalized solution for project euler #1 in haskell with recursion

checkIfMultiple x [] = False
checkIfMultiple x (n:ns) = x mod n == 0 || checkIfMultiple x ns

findMultiples limit ns = [x | x <- [0..limit], checkIfMultiple x ns]

sumMultiples limit ns = sum (findMultiples limit ns)

sumMultiples 999 [3, 5]

1. Passing down limit and ns from sumMultiples to findMultiples might be redundant. I was wondering, if I could somehow use composition here or some other shortcut.

2. What is the convention regarding writing out the type in Haskell? Is it always recommended?

Any other suggestion is appreciated, thank you.

• Is the O(1) solution intentionally avoided? – slepic Dec 21 '20 at 9:26
• BTW it would be best to include the specification of the project Euler problem 1 in your question if you implemented the problem solution as stated in project euler. Since you have a generalized solution, you should provide your generalized specification of the problem. In other words, what is it that is generalized compared to the original problem? – slepic Dec 21 '20 at 9:35
• Oh it's more generalized then I thought. Well then my first comment should have been why O(len(ns)) solution is avoided and instead O(limit * len(ns)) is used? – slepic Dec 21 '20 at 9:38

I decided to do euler1 before looking at your solution and this is what I came up with:

euler1 :: [Int] -> Int -> Int
euler1 ns limit =
sum .
filter (\x -> any (\n -> x mod n == 0) ns) .
take limit \$
[0..]

• Yes, composition helps cut down on the things you have to name, and thus on the things you have to pass along to intermediate functions.
• Haskell loves lists, and [0..] is often a nice starting point for a composition chain.
• Your checkIfMultiple recursion is good, but you will often find a very short synonym for this type of thing (common operations on a list) in base (eg all).
• Types are awesome.
• List comprehensions are amazing but they can sometimes interrupt a good compositional chain, compared with the equivalent filters and/or fmaps.

If a helper function like findMultiples is not itself particularly interesting, then a standard way of passing down arguments is to move them into a where clause which will have available any bindings created by the pattern match:

sumMultiples limit ns = sum findMultiples
where findMultiples = [x | x <- [0..limit], checkIfMultiple x ns]

Alternatively, when a single argument is involved, composition works pretty well, and in your example, you can use composition to pass along the last argument (ns):

sumMultiples limit = sum . findMultiples limit
findMultiples limit ns = [x | x <- [0..limit], checkIfMultiple x ns]

However, extending this to two arguments starts to get confusing. The following works, but it's pretty hard to read:

sumMultiples = (.) sum . findMultiples
findMultiples limit ns = [x | x <- [0..limit], checkIfMultiple x ns]

The usual convention for types in Haskell is to annotate all top-level bindings with their type signatures. (Generally, bindings in where and let clauses aren't annotated, unless the types are very complicated and/or the compiler needs some help.)

There are several reasons for this. First, type signatures provide succinct documentation of how a function is meant be used. To the extent that top-level bindings provide the "interface" for your code, the type signatures document that interface. Second, type signatures assist the typechecker in producing sensible error messages and better localizing type errors. If all types are inferred, the compiler can construct extremely complicated and unexpected types which can result in error messages that don't make any sense or appear in the "wrong place", far away from the actual error in the code. For example, in your code, if you mix up the argument order for findMultiples in sumMultiples:

sumMultiples limit ns = sum (findMultiples ns limit)

then the program type checks fine, and when you try to calculate the answer:

> sumMultiples 999 [3,5]

you get the error Non type-variable argument in the constraint: Integral [a] (Use FlexibleContexts to permit this). With proper type signatures:

checkIfMultiple :: Int -> [Int] -> Bool
checkIfMultiple x [] = False
checkIfMultiple x (n:ns) = x mod n == 0 || checkIfMultiple x ns

findMultiples :: Int -> [Int] -> [Int]
findMultiples limit ns = [x | x <- [0..limit], checkIfMultiple x ns]

sumMultiples :: Int -> [Int] -> Int
sumMultiples limit ns = sum (findMultiples ns limit)
^^ ^^^^^

the error is immediately localized to the bug with sensible error messages that say ns was [Int] when it should have been Int, and limit was Int when it should have been [Int].

Annotating just the top-level bindings usually provides enough information for type inference that you get decent, localized error messages, and it's a happy medium between annotating nothing and annotating all bindings. Finally, another reason bindings in where clauses are left unannotated is that it can sometimes be hard to assign them a type signature when polymoprhic functions are involved. For example, in the following function, uncommenting the type signature for go causes a type error, and there's no type signature that will work, unless you enable a GHC extension:

countValue :: (Eq a) => a -> [a] -> Int
countValue target = go
where -- go :: [a] -> Int
go (x:xs) | x == target = 1 + go xs
| otherwise = go xs
go [] = 0

Here are some other suggestions. There are two pairs of functions (and/all and or/any) that are useful for checking a boolean condition across a list. In this case, checkIfMultiple can be rewritten as:

checkIfMultiple x ns = any (\n -> x mod n == 0) ns

or:

checkIfMultiple x = any (\n -> x mod n == 0)

or even:

checkIfMultiple x = any ((== 0) . mod x)

Personally, I'm not sure that checkIfMultiple and findMultiples deserve their own names. I'd give an evocative name to the following helper:

d divides x = x mod d == 0

and write:

sumMultiples :: [Int] -> Int -> Int
sumMultiples ds limit = sum [x | x <- [0..limit], any (divides x) ds]
where d divides x = x mod d == 0

which, to me, can almost be read aloud to describe what it's doing.

I think @slepic is pointing out that you can sum the multiples of d less than stop using a well known formula for the sum of an "arithmetic sequence". The formula is the average of the first and the last number times the count of numbers, so literally:

-- sum multiples of d that are less than stop
multiples :: Int -> Int -> Int
multiples d stop = count * (first + last) div 2
where first = d
count = (stop-1) div d
last = first + d*(count - 1)

If you write multiples 3 1000 + multiples 5 1000 to get the sum of all multiples of 3s and 5s, that overcounts, because multiples of 15 get counted twice, so you need to write:

euler1 = multiples 3 1000 + multiples 5 1000 - multiples 15 1000

which gives the same answer as sumMultiples 999 [3,5].

Of course, as far as I can see, the only way to be sure you didn't screw the clever answer up is to check it with the unclever answer, which kind of defeats the point.