Learning Clojure with Project Euler
This article is a quick introduction to Clojure from someone still learning the language. I work through a few Project Euler problems, refining solutions along the way. In the end I give some general impressions of the language, the install and setup process, and support for Clojure within different development tools. Long time readers of this blog will remember I also used Project Euler to learn Scala basics a while ago.
I haven’t done much with Scala since then, mostly because I found the syntax a bit too quirky and the documentation lacking. Lau Jensens’s comparisions between Scala and Clojure inspired me to have a look at Clojure.
When getting started with a new language, I like to use a site that has excercises for programming practice. A great site for this is Project Euler; it gives you short problems to solve, and once a problem is correctly solved you are given access to the forum for that problem which contains hundreds of solutions written in different languages. Each of the problems are designed to be solved by some combination of mathematical insight and computer programming. Enough talk; lets see some code.
Warning: Spoilers ahead for Project Euler problems 1 through 3.
Project Euler Problem 1
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.
Here is the code I came up with:
1 2 3 4 5
(defn e1 [limit] (reduce + (filter #(or (zero? (mod % 3)) (zero? (mod % 5))) (take (- limit 1) (iterate inc 1))))) (e1 1000)
We start out by defining the function
e1 which takes a
limit is the stopping point of the the function. Since we want the sum of all multiples below 1000, on line 5 we call
e1 with 1000 for our
limit. Starting at the bottom of
e1, this code creates a lazy sequence of integers by starting at one and incrementing
(inc) from there. The
take just outside of that grabs the first limit – 1 elements from the sequence.
Now we want to
filter the sequence so that it only contains integers that are multiples of 3 or 5. The first argument to
filter is an anonymous function (lambda in Common Lisp) and the second argument is the sequence we just created. Clojure uses
#(...) as syntactic sugar for an anonymous function. Looking at that function on lines 2 and 3, the
% has nothing to do with the modulus. Each element of the sequence is being bound to
% when it is passed into the modulus function.
So now that we have our sequence, we want to add up everything inside to get the answer.
reduce applies the + function to each element in the sequence, plus the total so far, and we’re done!
Unfortunately, the solution board on Project Euler doesn’t have any Clojure solutions, but DZone has a wiki of Clojure solutions. Comparing my solution with some of the others there, it is looking like pretty idiomatic Clojure code. However, using the
range function, line 4 can be simplified to
(range 1 limit), which simply creates a lazy sequence of all of the numbers between 1 (inclusive) and
Project Euler Problem 2
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, …
Find the sum of all the even-valued terms in the sequence which do not exceed four million.
Lets start out by defining the sequence of Fibonacci numbers:
(def fibs (lazy-cat [0 1] (map + fibs (rest fibs))))
On line 2 we describe
fibs as a sequence created by adding each element of
fibs to each element of “the rest of fibs”. The rest of fibs is just everything but the first element, or for those familiar with Common Lisp, we are taking the tail. On line 1 we seed the sequence with 0 and 1.
Now that we have the sequence we sum up the evens under 4 million:
1 2 3
(defn e2 [limit] (reduce + (filter #(zero? (mod % 2)) (take-while #(< % limit) fibs))))
This is just a simple
filter like problem 1.
Now, do we really need to create a separate
fibs function? Why not combine the two functions? We can’t use an anonymous function for the argument to
filter, because we want to be able to define
fibs in terms of itself. What about this:
1 2 3 4 5
(defn e2 [limit] (let [fibs2 (lazy-cat [0 1] (map + fibs2 (rest fibs2)))] (reduce + (filter #(zero? (mod % 2)) (take-while #(< % limit) fibs2)))))
OK that was a trick. It seems to me that this should work, but let doesn’t allow lazy evaluation; it gives an error that
fibs2 isn’t defined when we try to use it in the
Project Euler Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
To tackle this one, lets write a recursive function that takes a number to factor (
num) and also the lowest prime that could be a factor of that number (
cur). As we recurse, if
cur is a factor, then we call
factor again with
cur / factor, and continue looking for factors. If we haven’t found a factor, then lets check if
cur + 1 is a factor. Because we continue dividing factors out of
cur and we are looking at factors from lowest to highest, we know that if
num are ever equal we’ve found the largest factor, which must also be prime.
1 2 3 4 5 6 7
(defn factor [num cur] (if (= num cur) num (if (zero? (mod num cur)) (factor (/ num cur) cur) (factor num (inc cur))))) (factor 600851475143 2)
So, lets start with the base case on line 2. To stop the recursion, we return
num have the same value. Otherwise (line 4) we want to continue looking for factors. If we have a factor, then recursively look for factors of
num / cur. If we don’t have a factor (line 6), then increment
cur and continue looking for factors. When we call
factor, we need to figure out the lowest prime that could be a factor. By inspection, we can see that 2 isn’t a factor of 600851475143, but 2 works as the starting value of
First Impressions of Clojure
Clojure’s syntax is very clean, and just makes sense. There isn’t much syntax to learn, just parentheses and the odd
%. Although I didn’t use it here, there is some additional syntax to learn for creating vectors, maps, and sets, but its easy to learn. People who haven’t used Lisp in the past may run into a bit more trouble, but I suspect that anyone who has done functional programming before will pick up Clojure quickly.
The API does a good job of documenting everything, and the Clojure site in general is well organized. The only suggestion I have for improvement here is to include a page describing the more common language features and gotchas, along with some examples. Ruby does this pretty well. Anyone looking for a more structured introduction to Clojure may want to pick up the Programming Clojure book from The Pragmatic Programmers.
I found tool support to be lacking, which maybe is to be expected since Clojure isn’t a very popular language. There are two emacs modes for Clojure; one barfed out an error on me, and the other doesn’t seem to be picking up all of the keywords, function names, and other syntax bits that should be colorized. It also wasn’t supported by GeSHi, which I use for syntax highlighting here on GrokCode. I put together a new GeSHi language file for Clojure, and sent it to the project owner for inclusion. Meanwhile, you can get the Clojure file here. Rename it with a php extension and drop it into the geshi directory.
As a whole, I was impressed with Clojure, and plan to continue working with it.