Informatikr

Learning Haskell’s Basics – Problems from Project Euler

with 5 comments

Recently I started to learn Haskell and figured, it would be a good Idea to experiment with some of the Problems from Project Euler

I worked through several of the Euler problems some time ago, when I was learning Ruby. Back then I was amazed, how concise my code was, compared to the other languages I knew (Java and C, mainly). With Haskell the same thing happened, although on a smaller scale.

Below, I will present you four solutions that I especially liked and discuss some of their features, comparing them to my Ruby code.

Problem 1

Find the sum of all the multiples of 3 or 5 below 1000.

This one is yet another flavour of the notorious FizzBuzz problem. Employers watch closely! Here’s my solution:

euler1 = sum $ filter (divisible [3,5]) [1..999]

divisible :: [Int] -> Int -> Bool
divisible divisors n = any (\d -> (mod n d)==0 ) divisors

This is solves the problem in quite a general way, by introducing the utility function divisible which takes a list of divisors as well as a number and returns True if the number is evenly divisible by any element of the divisors list.

Compared to Ruby, I see Haskell slightly ahead in this problem, due to the possibility of partial application. An equivalent Ruby solution would make use of blocks/lambdas that require definitions of formal parameters, which in turn make the code somewhat more verbose.

Problem 2

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

euler2 = sum $ filter even $ takeWhile (<= 4000000) fibs

fibs :: [Int]
fibs = 1 : 2 : zipWith (+) fibs (tail fibs)

Haskell’s clear win, in this case, is lazy evaluation and the possibility of recursively defining an infinite list containing all the Fibonacci numbers. However, Ruby deserves a golden style-point for allowing the number four million to be written as 4_000_000. Is there a similar way of writing numbers in Haskell that I should know of?

Problem 4

Find the largest palindrome made from the product of two 3-digit numbers.

This is my favourite code snippet in this article. Thanks to the list comprehension the solution rather looks like the problem definition. Simple and beautiful.

Problem 21

Evaluate the sum of all the amicable numbers under 10000.

euler21 = (sum . filter amicable) [1..9999]

amicable :: Int -> Bool
amicable a = (a /= b) && ((d b)==a)
    where d = sum . divisors
          b = d a

divisors :: Int -> [Int]
divisors = divisors' 2 [1]
    where divisors' d divs n
            | d^2 > n      = divs
            | (mod n d)==0 = if (div n d) == d
                             then divisors' (d+1) (d : divs) n
                             else divisors' (d+1) (d : (div n d) : divs) n
            | otherwise    = divisors' (d+1) divs n

My point on this piece of code is Haskell’s where clause. Locally defined helper functions come in handy all the time in a language without looping constructs (other than recursion), where you want to hide starting value-, accumulation- and similar parameters from the user. Here, the divisors function is just a prettier interface to the one that does the real job: divisors'.

Conclusion

Before starting to learn Haskell, Ruby was my favourite programming language. And it still is. But I’m definitely feeling Haskell’s gravitational field. As a next step I’m now looking forward to using Haskell in a slightly more serious context. Let’s see if I get caught inside it’s event horizon.

About these ads

Written by Falko

October 13, 2008 at 2:15 pm

Posted in programming

Tagged with , ,

5 Responses

Subscribe to comments with RSS.

  1. 1) I solved this with pencil and paper. If you are not so concerned with generality, a natural Haskell expression is
    sum [n | n <- [1..999],
    n `mod` 3 == 0 || n `mod` 5 == 0]
    Your solution can also be improved by a list comprehension that allows dropping the second argument of “divisible”:
    euler1 = sum [i | i [Int] -> Bool
    divides n = any ((== 0) . (mod n))

    2) Probably the best way to write 4 million in Haskell is just 4*10^6. The compiler will statically evaluate this, so there’s no interesting performance penalty.

    Interesting post, thanks!

    PO8

    November 13, 2008 at 4:32 pm

  2. [Oops. Let’s try that again.]

    1) I solved this with pencil and paper. If you are not so concerned with generality, a natural Haskell expression is
    sum [n | n <- [1..999],
    n `mod` 3 == 0 || n `mod` 5 == 0]
    Your solution can also be improved by a list comprehension that allows dropping the second argument of “divisible”:
    euler1 = sum [i | i [Int] -> Bool
    divides n = any ((== 0) . (mod n))

    2) Probably the best way to write 4 million in Haskell is just 4*10^6. The compiler will statically evaluate this, so there’s no interesting performance penalty.

    Interesting post, thanks!

    PO8

    November 13, 2008 at 4:34 pm

  3. Sorry about the code in the last two posts. Apparently I can’t figure out how to paste code here.

    PO8

    November 13, 2008 at 4:35 pm

  4. [… – informatikr.wordpress.com is another useful place of advice. Car insurance claims [… -

    Online Car Insurance >> http://onlinecarinsuranceclaims.com/

    November 23, 2009 at 8:24 pm

  5. If you are a real estate professional, be really careful in dealing with KoRes Corp. in Weston Florida. Tulio Rodriguez & Monica Cataluna-Shand are shysters and look for anyway to steal ones customers. They attempt to steal your client by requesting their contact information and later contact them behind your back to get them to deal with them directly.

    Nowsarcammola

    May 14, 2010 at 6:33 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: