WARNING! This post contains a spoiler for Problem #1 listed at Project Euler. Do not read the rest of this post if you’re planning to attempt to solve the problem yourself.
I decided to work my way through these problems using Haskell, as I felt it’d be a great way to learn the language (or at least start to get familiar with it).
Problem #1 in the series is a nice “starter” question. It’s a simple one to get you going, which for me was great since I am a bit of a Haskell beginner:
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.
Here is my Haskell source that generates the required answer:
sum [ n | n <- [1..999], ((mod n 3) == 0) || ((mod n 5) == 0) ]
Don’t you just love how concise the answer is? If you’re like me and are new to Haskell, let me explain it a little.
- [1..999] - this generates a list of values from 1 to 999 inclusive.
- [ value | item <- source list, condition ] - this is the basic list comprehension syntax in Haskell (basically this is how you generate lists from other lists). Here is the breakdown.
- source list is a reference to a list which is used as the source to generate the new list.
- item is the variable that is an alias for each item in the source list. This is usually referenced in the value expression.
- condition is a boolean condition that indicates whether or not a value should be included in the list.
- value is the final expression that gets evaluated and stored in the list. The expression is only evaluated and added to the list if the condition is true
- mod n 3 - this evaluates “n modulo 3″, and hence gives the remainder when n is divided by 3.
- ((mod n 3) == 0) || ((mod n 5) == 0) - this is a condition that evaluates to true if n is evenly divisible by 3 or 5.
- [ n | n <- [1..999], ((mod n 3) == 0) || ((mod n 5) == 0) ] - for each item n in the list of numbers 1 through 999, if the number is evenly divisible by 3 or 5, then include it in the list.
- sum - this function simply produces the sum of all the numbers in the given list.
Pretty simple really isn’t it 
Enjoy.
March 18, 2008
That’s really elegant and simple enough that I didn’t need to read the explanation to figure out what it was doing (the list syntax is the only new thing to me).
March 18, 2008
Aye I agree with you mate. But I think there are some intricacies that some people might not be able to figure out without a brief explanation. Wait til the Fibonacci questions kick in, the self-referencing infinite data structure definition is a bit of a mind job
March 18, 2008
I had never played with Haskell before. It gives you an elegant solution. Tried the same problem in C#, much clunkier.
Also, a pleasant break from dealing with coal, that dirty black stuff that pays very well!
March 18, 2008
Hey James. It’s a good idea to have a play with these problems in other languages as it really does show how good and bad things can be. C# isn’t particularly nice compared to Haskell when it comes to the solution to this problem. But it’s not specific to C#, it’s Imperative languages in general.
Take a look at the next problem if you’re keen to see how messy (and slow) an imperative version can be!
April 6, 2008
Hmm. Interesting, and pretty terse too. But I’d always thought that list comprehensions were a poor man’s lambda.
Haskell does have a lambda syntax (it’s something like \x -> x 1), so I find myself wondering, how would the code look implemented that way?
Oh, and I’d be willing to bet at least $5 that there’s a Perl version which is half the length (but unreadable to anyone other than the original author!)
April 6, 2008
You’re right it does indeed have that kind of syntax for lambda expressions, though in this case I can’t see how it would make the problem easier to solve. List comprehension makes this problem a lot easier.
Here’s another solution that I just threw together for your viewing pleasure:
sum $ [3,6..999] ++ [5,20..999] ++ [10,25..999]
Avoids the need to do any modulo checking, and probably works a little bit quicker than the above solution.
Then again, mabye not
I can’t be arsed to punch them both in and get performance stats!
April 7, 2008
In this case, you’re probably right - the list comprehension is the right tool for the job. In general though (unless I am talking nonsense), a lambda expression can express anything that a list comprehension can, but not vice versa.
Maybe I should have a play with Haskell and see if I can knock up a lambda solution.
From a language design perspective, it would seem to make sense to either implement both features (and let the user choose which to use), or just to implement lambdas, but it wouldn’t make much sense to implement just list comprehensions. Anwyay, I’m starting to ramble…
That last solution is just building the list of results directly, without doing any filtering, then applying sum to that list, right?
April 7, 2008
Correct. Nothing smart at all. Just manual! Adding all the multiples of three to a list, then multiples of 5 at increments of 15, then same again, but starting at 10. This means I know I’m skipping all numbers which divide evently by 3 and 5. Add those lists together, then sum all the numbers in the list. Easy peasy
June 20, 2008
There are many many problems for which C is much clunkier than Haskell, but it’s silly to say that of this problem:
Also, there are other possible considerations than how easily the solution is expressed, such as how fast it runs, which might take a wee more thought:
int sum = 0; int inc[] = { 3,2,1,3,1,2,3 }; for( int n= 0, i = 0; (n += inc[i]) < 1000; ){ sum += n; if( ++i == 7 ) i = 0; }June 20, 2008
“But I’d always thought that list comprehensions were a poor man’s lambda.”
I wrote a longer response that got eaten, so I’ll just say: you always thought (very) wrong; that’s like saying that a Ferrari is a poor man’s junkyard, just because you can find all the raw materials you need there to build a Ferrari.
June 20, 2008
“Take a look at the next problem if you’re keen to see how messy (and slow) an imperative version can be!”
Your parenthetical is astoundingly wrongheaded (and intellectually dishonest). Of course an implementation in any language can be slow, but the idea that imperative languages are inherently slower than declarative languages is obviously belied by the fact that all declarative programs get translated into imperative programs.
June 23, 2008
@truthmachine: I like your second C solution. It’s an interesting approach. I also think that Jon’s wrong with his opinion on list comprehension vs lambda expressions. Let the tool fit the task.