Informatikr

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.