I’ve always enjoyed Math. It’s concise and to the point. When you get an answer, you don’t have to consider “what the author was thinking when he wrote the problem.” Either you’re right, or you’re wrong. In fact, it’s partly due to my love of math that I decided to pursue a career as a software developer.

So naturally, when I discovered projecteuler.net, a site designed for those who enjoy writing programs to solve challenging math problems, I was all over it. Unfortunately, I only knew basic Java at the time, so I was rather limited in not only how I could solve problems, but also in how I could reason about a problem. After learning Clojure, a functional programming language for the Java Virtual Machine (JVM), I decided to give Project Euler another shot. And I’m glad that I did. Solving problems on Project Euler is significantly easier in Clojure than it is in Java. I don’t mean to pick on Java or even the object-oriented paradigm. Rather, I intend to display how a functional programming language, such as Clojure, allows you to solve and reason about problems in ways that are either difficult or impossible in procedural/object-oriented languages.

Let’s start with the first problem on Project Euler as an example:

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.

This problem is pretty straightforward. In Java, we would likely do the following:

long total = 0;
//for each integer between 3 and 1000
for (int i = 3; i < 1000; i++) {
//if i is divisible by 3 or 5, then add it to our total
if (i % 3 == 0 || i % 5 == 0) {
total += i;
}
}
System.out.println(total);

In Clojure, your solution will look much different. First, let’s generate our data set:

;Call the range function to generate a lazy sequence of all
;of the integers between 3 and 999 (inclusive)
(range 3 1000)

Now, we need to filter that data set to only include numbers that are divisible by 3 or 5. We don’t have a function for checking for divisibility, but we can write one:

(defn divisible? "Is n divisble by x?" [n x]
(zero? (mod n x)))

This will create a function called “divisible?” that accepts two integers, n and x, and checks to see if n is divisible by x. Next, we’ll need to create a function that will tell us if a given integer is divisible by either 3 or 5. Since we will only use this function for the duration of this problem and then likely never need it again, we can make it an anonymous function. The “#” indicates that the following form is an anonymous function and the “%” will represent the first parameter passed to the function:

#(or (divisible? % 3) (divisible? % 5))

Now, we can use our anonymous function above against all of the integers between 3 and 999 as a *filter* so that we will be left with a sequence of the numbers we actually care about:

(filter #(or (divisible? % 3) (divisible? % 5)) (range 3 1000))

After that, we simply need to *reduce* our data set using the “+” function. This will give us the sum we are looking for. In the end, our solution looks like this:

(defn divisible? "Is n divisble by x?" [n x] (zero? (mod n x)))
(reduce + (filter #(or (divisible? % 3) (divisible? % 5)) (range 3 1000)))

So that’s it. We’ve just solved the first problem, but more than likely, you’re not convinced. If you’re accustomed to object-oriented languages like Java, then you probably see nothing wrong with the Java solution to the previous problem. You wouldn’t be wrong, after all, it does produce the correct answer and in a reasonable amount of time. But that was just a warm-up problem. More difficult problems will hit the limits of Java and procedural/object-oriented programming, so let’s up the difficulty and look at problem number two:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

In Java, our solution definitely involves recursion. We’ll need to keep track of our two most recent Fibonacci numbers and a running sum. Our solution likely looks something like this:

public static long numberTwo(int fib1, int fib2, long sum) {
if (fib2 < 4000000) {
int nextFib = fib1 + fib2;
if (nextFib % 2 == 0) {
sum += nextFib;
}
return numberTwo(fib2, nextFib, sum);
} else {
return sum;
}
}

Then we simply need to call this function with the following arguments to get the result we’re looking for:

System.out.println(numberTwo(1, 2, 3));

Now, let’s look at a solution to the same problem except using Clojure. Our approach is going to be much different than it was with Java. Instead of creating the Fibonacci sequence while simultaneously calculating our sum, we’re just going to create a lazy sequence of the Fibonacci sequence and keep pulling values from it until we have everything we need:

(def fib-seq ;Define the variable fib-seq to hold our lazy sequence
((fn rfib [a b] ;Define a recursive function for calculating Fibonacci values
(lazy-seq ;Define a lazy sequence.
;Creates a new sequence consisting of the value of 'a'
;followed by the result of calling rfib
(cons a
; call rfib again with 'b' and 'a + b'
(rfib b (+ a b)))))
;Use 0 and 1 as the first set of values to our Fibonacci sequence.
0 1))

Now we have a lazy sequence that will calculate only as many values of the Fibonacci sequence as we need. The rest of this is easy. First, we’re going to drop the first two values (since we only care about the second ’1′ and the ’2′ value). Next, we will take only the values which are less than 4,000,000. After that, we simply need to filter and reduce like we did with the previous problem. Our solution ends up looking like this:

(def fib-seq ((fn rfib [a b] (lazy-seq (cons a (rfib b (+ a b))))) 0 1))
(reduce + (filter even? (take-while #(< % 4000000) (drop 2 fib-seq))))

Our Clojure solution has a couple of advantages over our Java solution:

1. Our Clojure solution is very clear about what we are trying to do. With our Java solution, our problem-solving logic is mixed in with our recursion which can make debugging very difficult.

2. Our Clojure solution is going to be reusable in the future if we ever run into the Fibonacci sequence again. Of course, you could rewrite the Java solution to first create a list of all of the Fibonacci values that we care about and that might work. However, with Clojure constructs such as take, drop-while, lazy-seq, and the myriad of other core Clojure constructs, we get a lot of functionality out of the box that we don’t have with Java. We could build it out ourselves, but that would involve extra work and debugging that I don’t care to perform. Even if we were to build such a library, it wouldn’t be as flexible as something we could build with Clojure.

So far, we’ve only considered problems that are straight forward and fairly simple. However, the problems on Project Euler grow progressively more difficult as you progress.

Consider problem 34:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?

Problems like this are common in computer science. With both Java and Clojure, our solution to this problem will involve looping through multiple different scenarios while only counting those which are valid. However, Clojure wins again with its “memoize” construct. Memoize essentially works as an in-memory cache which will allow you cache each combination that you’ve tested so that you can avoid running the same calculations multiple times. Again, you *could* write functionality to do this in Java, but I get that out of the box with Clojure and would rather not waste my time.

Additionally, we haven’t even touched on several of the other advantages of Clojure such as tail recursion, immutability, and macros. We’ll save those for a future blog post.

Solving problems involving complicated operations across large complex sets of data is best suited for tackling functional programming. While many of these problems can be solved using a procedural or object-oriented language, they are best left to functional programming languages. I challenge you to pick up a functional programming language (such as Clojure) and start solving problems on projecteuler.net. As you progress and solve problems, consider the advantages and disadvantages of using a procedural or object-oriented language such as Java versus a functional programming language such as Clojure. But be forewarned, after you start solving problems in a functional programming language, you’ll likely have a hard time going back to anything else.