In our last post, we solved Problem 1 from Project Euler and learned a bit about sequences and filtering while we were at it. Now we'll tackle Problem 2, which reads:

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.

So, it seems pretty clear that the first step is some method of generating the Fibonacci sequence. There are a few ways of thinking about this, but the most straightforward is simply to code up the function fib(0) = 0, fib(1) = 1, fib(n) = fib(n-1) + fib(n-2):

(defn fib [n]
  (cond
    (= n 0) 0
    (= n 1) 1
    :else (+ (fib (- n 1)) (fib (- n 2)))))

Now, we want a sequence of the values of fib for increasing values of n, and we'll filter out the evens from that. Since we don't know how many values we are going to need up-front, we will use a lazy sequence, which is potentially infinite. The basic idea behind lazy sequences is that the sequence is represented by a cons cell which contains the first element of the sequence in its left half and a function that can generate the rest of the sequence in its right half. When this function is evaluated, it returns a new cons cell containing the second element of the list and a new function that can, again, generate the rest of the list and on and on, ad infinitum. For instance, a lazy sequence that can generate the natural numbers might look something like this psuedo-code:

(def natural-numbers
  (cons-cell 0
             (fn next []
               (fn [n]
                 (lazy-cons-cell (+ n 1)
                                 (next (+ n 1)))))))

A consumer of the sequence would pull the 0 and then evaluate the next function, which produces a cons cell that looks like (1 . (next 1)). Now, (next 1) returns a function, which, when evaluated, returns a cons cell looking like (2 . (next 2)), etc. So, the effect is that you get a sequence of cons cells where the first element in each successive cons cell is the next natural number. The "lazy-cons-cell" function (macro, really) just delays execution of (next (+ n 1)) until the consumer requests its value. That's what makes this a lazy sequence, computation happens on demand, which is awesome for large, infinite and compute-intensive sequences.

Okay, so now that we have the notion of lazy sequences down, we can try to come up with a lazy sequence based on our fib function. In Clojure, lazy sequences are born out of the use of lazy-cons in place of cons when building up a list. So, a lazy sequence of the Fibonacci numbers would be:

(def fib-seq
  ((fn f [i] (lazy-cons (fib i) (f (inc i)))) 0))

The magic here is in the inner lazy-cons expression, (lazy-cons (fib i) (f (inc i))). This builds our cons cell with the current Fibonacci value on the left and a function that can generate the rest of the sequence on the right. What is going on in the entire expression is that we are defining a global Var fib-seq to be (f 0) where f is defined to be the result of our lazy-cons expression. So, when we pull the first value out of fib-seq, we should get the left side of the cons cell, which is (fib 0), or 0. The next value will be (fib 1), which is 1, and so on.

The rest of the problem is easy and will be much like our solution to Problem 1. The only new thing here will be a function called take-while, which takes a predicate and a sequence and will take values out of the sequence as long as the predicate returns true for the current value.

(apply + (take-while #(< % 4000000)
           (filter #(even? %) fib-seq)))

So, we just pull even values out of fib-seq, thanks to our even? filter, as long as the value is less than 4,000,000 and sum the results. Tada!

There are better ways at generating the Fibonacci sequence, this just seemed the most straitforward to start with. A few good options are listed on the Clojure wiki here. In particular, check out the last one, which builds on a solution Rich proposed and is quite nice.

That's it for this problem. The code is available on GitHub. As always, comments, questions, problems and suggestions are welcome.