Project Euler and Erlang – introduction, problem #1

Posted by ochronus on Oct 4, 2008 in erlang | 2 comments

I decided to start learning Erlang by solving problems from Project Euler. In short, Project Euler maintains a list of problems (mainly more mathematical than of programming) ordered by difficulty. I’ve solved some already in ruby, focusing on producing a straightforward (but not too stupid) working version first, then rethinking and refining the algorithms for simplicity and performance. For learning erlang, though, I shall first focus on working versions, then maybe later, when I get proficient with the language, revisit my old soulutions and tweak them. I decided to make a series of posts about this here, so, dear reader, you are reading part #1 now.

The first (easiest) problem on Project Euler

The problem statement: “Find the sum of all the multiples of 3 or 5 below 1000.?”

This should be easy. Of course, a procedural solution came into my mind first, which is natural with my ruby-c-php-c# past (and present). The procedural solution goes like this: initialize a variable (sum) with the value 0, then iterate through the numbers starting from 1 until 999 (less than 1000), and if the number is divisible by either 3 or 5, add it to the sum variable. Nice and easy. In erlang, though, things are different. There is no “for loop” (it can be simulated, but it would ruin the point of learning erlang in the first place), variables are bind-once (assigned once, immutable later), so a running sum is not feasible (at least not easily). I had to find another solution. I knew from my previous encounters with functional languages (some haskell) that lists are a main concept. Actually, when I think of it, the list of numbers from 1 to 999 is a … erm… list. Right. So take another approach. Produce the list first, then decide what to do with it (still a procedural way of approaching problems…). Ok, but how do I produce a list in erlang? Do I have to define it by hand? No way. After some google’ing I found some built in goodness for it: the list module, and its seq function. It goes like this (in its most basic form):

MyList = lists:seq(1, 999).

Now the ‘variable’ MyList is bound to the value [1,2,3......999]. Nice. The next step is to filter this list so that only multiples of 3 and 5 remain. Of course erlang has its tool for this, lists:filter. This function takes two arguments, the first is the filtering function, the second is a list. Filter generates a new list from the items of the original list for which the filtering function returns true. So:

f(X) -> (X rem 3 == 0) or (X rem 5 == 0).
MyFilteredList = lists:filter(fun f/1, MyList).

Good, I now have the list [3,5,6,9,...]. What’s the next step? Nothing much remained, only summing up the generated and filtered list. For this, use – what a surprise – lists:sum.

TheResult = lists:sum(MyFilteredList).

That’s all. We’re ready. Why does it suck then? :) It sucks because it is still a procedural approach in a way, it feels like ‘hacking around’ the language, having my way by little tricks. Some points:

• why do we need variables?
• why do we do things in separate steps?

The answer is: there’s no reason. Let’s rewrite the code into one nice block:

lists:sum(lists:filter(fun(X) -> (X rem 5 == 0) or (X rem 3 == 0) end, lists:seq(1,999))).

That’s better, and more erlang-ish. It has what we wanted in one line. Almost an english sentence :) Let’s read it aloud: sum the list of numbers which is generated by filtering all the numbers from 1 to 999 which are either divisible by 3 or 5.

Nice, nice, but when learning a new language, I often find to reimplementing small, elemental functions/constructs are the key to understanding. So far, erlang’s list module does the heavy lifting for us. But how does filter, sum and seq work? Think! You don’t have any variables, no mutable state, only lists for now. Let’s implement them, in a primitive, simple way.

Implementing seq

What does seq do? It generates a list of integers from 1 upto its argument. So seq will take the form seq(N). Ok, but we don’t have iteration, loops. How do we cycle through numbers, then? Recursion, of course! Creating a recursive function requires you to know exactly when to have it stop. Seq should stop when there’s no number left to generate. When is that? When we reach N. Let’s turn this over, and generate the list from N to 1. So seq(N) needs to build a list recursively. How do we define such a thing?

seq(0) -> [];
seq(N) -> [N | seq(N-1)].

So basically we’re telling the compiler a definition. Notice that it’s a bit different from our usual procedural-language function defnition, where you write the steps needed for calculation. This is much more concise, much more like a mathematical definition. The second line says: for a number N, put it as the first item in the list, then genereate the sequence upto N-1  as the remaining items. The first line is the stop-clause for the recursion, it says when reaching 0, indicate the end of list by returning an emtpy list (it’s not added to the list of numbers). See how powerful this is? It amazes me. I’m not using any loops, any variables, I’m writing a fairly simple definition. It differs from lists:seq, of course (it does not support varying of the initial value, steps, or negative numbers), but it’s fair for our first erlang code :)

Implementing sum

Again, what does sum do? It takes a list, and sums it. But how, without variables and loops? Again, recursion. What is summing up a list anyway?

Procedural way: initialize sum = 0. Take an item, add it to the sum. Take the next and add until there’s nothing to sum.

Functional way: take the first item, then add the sum of the rest to it. The sum of an empty list is 0.

Let’s put this functional definition into code:

seq(0) -> [];
seq(N) -> [N | seq(N-1)].

filter(F, [H|T]) ->
	case F(H) of
		true -> [H|filter(F, T)];
		false -> filter(F, T)
	end;
filter(F, []) -> [].

-module(wip).
-export([seq/1]).
-export([sum/1]).
 
-export([filter/2]).
-export([get_the_sum/1]).
 
seq(0) -> [];
seq(N) -> [N | seq(N-1)].
 
sum([H|T]) -> H + sum(T); 
 
sum([]) -> 0. 
 
filter(F, [H|T]) ->
	case F(H) of
		true -> [H|filter(F, T)];
		false -> filter(F, T)
	end; 
 
filter(F, []) -> [].
 
get_the_sum(N) -> sum(filter(fun(X) -> (X rem 3 == 0) or (X rem 5 == 0) end, seq(N-1))).
 
sum_using_builtins(N)-> lists:sum(lists:filter(fun(X) -> (X rem 5 == 0) or (X rem 3 == 0) end, lists:seq(1,N-1))).

If you liked this, check out my haskell-ruby solution to problem #25!

Related posts:

1. Ruby vs. Haskell – project Euler #25 deathmatch