Project Euler Problem 2 in Clojure

Question

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.

Answer 1

(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))

Answer 2

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)))

Answer 3

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.