## Archive for **October 2008**

## Learning Haskell’s Basics – Problems from Project Euler

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.