Project Euler #2 - Sum of even Fibonacci numbers to 4,000,000

Question

This particular problem has already been posted here before, but the community is ok with me to post it again, so I can have feedback on my own implementation.

I tried to keep things simple, with each function having its own responsibility so they can be reused in other contexts. Here it is:

(ns marcofiset.euler.problem2)

(defn fib [n]
  (if (< n 0)
    (throw (Exception. "Can't compute fib of n < 0"))
    (loop [i n cur 1 next 1]
      (if (zero? i)
        next
        (recur (dec i) next (+ cur next))))))

(defn fibs []
  (map fib (iterate inc 0)))

(defn fibs-until [max]
  (take-while #(< % max) (fibs)))

(defn solution []
  (apply + (filter even? (fibs-until 4000000))))

(println (solution))

I'm beginning to learn Clojure and this is one of my first exercices. I'd like to have some feedback from more experienced Clojure programmers.

Answer 1

I'm also kind of a Clojure newbie (I've been messing with it off and on for about two years), so take my comments with a grain of salt.

In the loop in fib, I would separate each binding pair with commas, like this:

(loop [i n, cur 1, next 1] ; etc.

Clojure treats commas as whitespace, so you can use them anywhere you can use a space. It can make binding vectors and map literals with everything on one line a lot easier to read.

It looks like your function fibs is just making an infinite lazy sequence of Fibonacci numbers by mapping fib over a range. You can actually write a function to do this directly; see http://clojuredocs.org/clojure_core/clojure.core/lazy-seq (the second example). I don't know how the performance compares, but it's short and a good way to learn about making your own lazy sequences.

I think your solution function is good, but https://stackoverflow.com/questions/3153396/clojure-reduce-vs-apply says there might be a tiny performance advantage to using reduce instead, like this:

(reduce + (filter even? (fibs-until 4000000)))

The hard-coded limit in solution makes me uncomfortable somehow. The rest of your code is very nicely packaged out into separate, reusable functions, so it feels a little odd to see solution not. Maybe pass the limit as an argument, and then write

(println (solution 4000000))

Otherwise your code looks good to me. It's very clean and easy to read.

You might also be interested in type hinting and the memoize function if you're working through Project Euler; they can help improve performance, especially on mathematical code. For example, if you know the argument to fib will always fit in a Java long (64 bits), you can write fib like this:

(defn fib [^long n]  ;etc

This gives the compiler a type hint that lets it avoid reflection, and can improve performance.

You can pass memoize a referentially transparent function (one that always returns the same value given the same arguments), and it will return a new version of the function that caches results. For example, say you'd written a naive Fibonacci like this:

(defn fib [n]
  (if (< n 2)
    1
    (+ (fib (- n 1)) (fib (- n 2)))))

Then you could send that function to memoize, and you'd get a new version that would save its previous results. Since that naive function keeps recalculating the same cases, you'd get a performance boost by turning those repeat calls into map lookups.

I hope some of my comments were helpful, and have fun with Clojure; it rekindled my interest in programming.