I recently discovered Project Euler, an excellent resource to use while learning a new language. Maybe a little late to the game, but fun nonetheless.
The very first problem is rather simple:
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.
And a potential solution is haskell is could be to define the following:
isMultOf x n = mod n x == 0 sumList xs = foldr (+) 0 xs
After which the answer could be obtained with a simple:
sumList [a | a <- [1..1000], isMultOf 3 a || isMultOf 5 a, a < 1000]
And we have a list comprehension. Beautiful, and immediately expressive of exactly what’s happening for such a simple problem. The amazing thing is that properly written haskell maintains this same clarity and expressivity in even large scale programs. Sometimes it’s the little things in a language that makes you really appreciate it.
Hopefully wordpress hasn’t screwed up the formatting for you.
Comments 15
FWIW the prelude already has a `sum` function, and `a < 1000` is unnecessary since you’re only generating numbers from 1 to 1000.
Posted 16 Apr 2009 at 12:32 pm ¶Why the a<1000 test? Use a<-[1..1000-1] instead. And sumList exists and is called sum.
Posted 16 Apr 2009 at 12:40 pm ¶The “a < 1000″ in the body of the listcomp is redundant, since a already ranges over the list [1..1000].
You can write “mod” in Haskell’s infix syntax if you prefer: (mod n 3) is the same as (n `mod` 3).
Finally, sumList is unnecessary–there is already a built-in “sum” function that adds up the elements of a list.
So I’d write the answer as:
Posted 16 Apr 2009 at 12:53 pm ¶sum [a | a<-[1..1000], a`mod`3 == 0 || a `mod`5 == 0]
Solrize:
Nice solution. To pick a nit, however, the problem says for all multiples less than 1000, so we’ll want:
sum [a | a<-[1..999], a`mod`3 == 0 || a `mod`5 == 0]
Posted 16 Apr 2009 at 1:21 pm ¶Less repetitive:
a `isMultOf` b = a `mod` b == 0
sum [a | a <- [1..999], (a `isMultOf`) `any` [3,5]]
Posted 16 Apr 2009 at 4:28 pm ¶Without isMultOf:
Posted 16 Apr 2009 at 11:04 pm ¶sum [a | a <- [1..999], or $ map ((== 0) . mod a) [3,5]]
I would argue the last two attempts are much less clear than f.ex. Stephen Johnson’s expression..
Posted 17 Apr 2009 at 4:24 am ¶What about this?
sum [ a | a <- [1..999], any ((==) 0 . (a `mod`)) [3,5] ]
I’m a beginner, so if it is any wrong please tell me.
Posted 17 Apr 2009 at 4:40 am ¶Another way to do it:
sum_mult_3 = sum [3,6..1000]
sum_mult_5 = sum [5,10..1000]
sum_mult_15 = sum [15,30..1000]
result = sum_mult_3 + sum_mult_5 – sum_mult_15
all these lines could be reduced to:
sum $ map sum [[3,6..1000],[5,10..1000],[(-15),(-30)..(-1000)]]
but this is less understandable
Posted 17 Apr 2009 at 5:27 am ¶What’s unclear about (a `isMultOf`) `any` [3,5]? It’s practically english.
Posted 17 Apr 2009 at 8:38 am ¶I think that you’ve just shown that, while Haskell is a joy to learn, it’s not always a joy to show others your Haskell. Go for something incomprehensible first, so that it takes a while to come up with alternate idioms for it.
Posted 17 Apr 2009 at 9:04 am ¶I love all the discussion actually. I knew my solution was far from ideal when I posted it, especially given that I have a knowledge of the haskell Prelude that tends toward 0. So it’s been wonderfully informative to see the ongoing comments.
Posted 17 Apr 2009 at 9:38 am ¶I think one of swell things about Haskell is if you can’t find the wheel, it’s not hard to reinvent one.
So, just for giggles, let’s take the problem and make the limit and primes and their count variable:
sumPrimeMultsBeforeLimit :: [Integer] -> Integer -> Integer
sumPrimeMultsBeforeLimit primeList lim =
let
–a function that tests a number and base
modTestGood base val = mod val base == 0
–we’ll make a list of partial functions from the primes
–we’ll also say if the primes are an empty list, all the
— numbers are good and we get the sum of the numbers from 1 to n-1
— the type of testList is [Integer->Bool]
testList = if primeList == []
then [(\ i -> True )]
else map (\ k -> modTestGood k ) primeList
— we use or on a List of True and False results
— created by mapping a function that completes
— modTestGood
iOkay i = or ( map (\ f -> f i ) testList )
in
–sum the list comprehension use the iOkay filter
sum [ i | i sumPrimeMultsBeforeLimit [3,5] 1000
233168
*Vendor> seansFn
233168
Before I click “Post” a prayer to the CSS gods for a sensible layout.
Posted 23 Apr 2009 at 8:05 pm ¶Oh dear, not only did my indents not make it through, the last line of the function disappeared.
The last line of the function is:
sum [ i | i <- [ 1 .. lim - 1 ], iOkay i ]
Posted 23 Apr 2009 at 8:09 pm ¶Less repetitive:
a `isMultOf` b = a `mod` b == 0
sum [a | a <- [1..999], (a `isMultOf`) `any` [3,5]]
Posted 19 May 2010 at 6:25 am ¶Post a Comment