# Project Euler Problem 2 in Clojure

I am in the process of learning Clojure. I am fairly new to functional programming and would like to know if my code smells or if there are any performance implications with my approach.

; Returns the the given sequence with the given item appended to it.
(defn snoc [xs x] (concat xs [x]))

; Returns the Fibonacci sequence up to the highest number less than max.
(defn fib [max]
(loop [a 1, b 1, acc [1]]
(if (> b max)
acc
(recur b (+ a b) (snoc acc b)))))

; Project Euler Problem 2: Attempt A
(defn pe2a []
(reduce +
(filter even? (fib 4000000))))


For reference:

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.

-
You can generate the even-valued terms directly, rather than generating all terms and discarding the odd ones. The direct approach takes a bit less time to generate the sequence up to four million. –  Nathan Hughes Jul 24 '12 at 21:08

(defn snoc [xs x] (concat xs [x]))


There is a reason snoc is not defined by default in clojure: Since appending at the end of a singly linked list takes O(n) time, this is actually quite expensive. When building up non-lazy lists tail-recursively in a functional language, you often build the list the wrong way around (using cons instead of snoc) and then reverse it at the end to avoid that cost.

However in this case there is actually a nicer way: by using a lazy sequence rather than a strict list, we can avoid the need for loop/recur and save the cost of building up the list. We can also separate the logic of creating the Fibonacci numbers from the logic which decides how many numbers we want by first creating a lazy sequence containing all Fibonacci numbers and then using take-while to take those less than the given maximum. This will lead to the following code:

;; A lazy sequence containing all fibonacci numbers
(def fibs
(letfn
[(fibsrec [a b]
(lazy-seq (cons a (fibsrec b (+ a b)))))]
(fibsrec 1 1)))

;; A function which returns all fibonacci numbers which are less than max
(defn fibs-until [max]
(take-while #(<= % max) fibs))

-
Thanks for your answer. I didn't think about building the list with cons and just reversing it, albeit reversing it really doesn't matter in this situation. Also, thanks for the tip on lazy-seq and take-while! –  Jeremy Heiler Jan 27 '11 at 19:27
I think I have broken part your code well enough. Just to be sure, what does the % do? From what I can see, it represents the parameter that is implicitly being passed into the anonymous function. –  Jeremy Heiler Jan 27 '11 at 20:12
@Jeremy: That's right. #(<= % max) is just a short way to write (fn [x] (<= x max)), i.e. a function which takes an argument and then checks whether that argument is less than or equal to max. –  sepp2k Jan 27 '11 at 20:18

I'm not sure if this belongs as a comment here but I built my solution in clojure as well. The Fibonacci numbers are generated as an infinite sequence as per Halloway's "Programming in Clojure" p. 136. I then sum using using a list comprehension

;;Programming in Clojure p. 136

(defn fibo [] (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

(defn proj-euler2 []
(reduce + (for [x (fibo) :when (even? x) :while (< x 4000000)] x)))

-

Rather than writing snoc, just use conj.

(conj [1 2] 3)


returns

[1 2 3]


Note that this only works for vectors.

(conj (list 1 2) 3)


returns

(3 1 2)


Finally, if there were performance implications, you could use a transient vector and persist it at the last possible moment.

P.S. I like Dave's solution.

-