Cleaning up Clojure function

Question

Coming from imperative programming languages, I am trying to wrap my head around Clojure in hopes of using it for its multi-threading capability.
One of the problems from 4Clojure is to write a function that generates a list of Fibonacci numbers of length N, for N > 1. I wrote a function, but given my limited background, I would like some input on whether or not this is the best Clojure way of doing things. The code is as follows:

(fn fib [x] (cond 
               (= x 2) '(1 1)
            :else   (reverse (conj (reverse (fib (dec x))) (+ (last (fib (dec x))) (-> (fib (dec x)) reverse rest first))))
          ))

Answer 1

The most idiomatic "functional" way would probably be to create an infinite lazy sequence of fibonacci numbers and then extract the first n values, i.e.:

(take n some-infinite-fibonacci-sequence)

The following link has some very interesting ways of generating fibonnaci sequences along those lines:

http://en.wikibooks.org/wiki/Clojure_Programming/Examples/Lazy_Fibonacci

Finally here is another fun implementation to consider:

 (defn fib [n]
   (let [next-fib-pair (fn [[a b]] [b (+ a b)])
         fib-pairs (iterate next-fib-pair [1 1])
         all-fibs (map first fib-pairs)]
     (take n all-fibs)))


 (fib 6)
 => (1 1 2 3 5 8)

It's not as concise as it could be, but demonstrates quite nicely the use of Clojure's destructuring, lazy sequences and higher order functions to solve the problem.

Answer 2

Here is a version of Fibonacci that I like very much (I took the implementation from the clojure wikibook: http://en.wikibooks.org/wiki/Clojure_Programming)

 (def fib-seq (lazy-cat [0 1] (map + (rest fib-seq) fib-seq)))

It works like this: Imagine you already have the infinite sequence of Fibonacci numbers. If you take the tail of the sequence and add it element-wise to the original sequence you get the (tail of the tail of the) Fibonacci sequence

0 1 1 2 3 5 8 ...
1 1 2 3 5 8 ...
-----------------
1 2 3 5 8 13 ... 

thus you can use this to calculate the sequence. You need two initial elements [0 1] (or [1 1] depending on where you start the sequence) and then you just map over the two sequences adding the elements. Note that you need lazy sequences here.

I think this is the most elegant and (at least for me) mind stretching implementation.

Edit: The fib function is

 (defn fib [n] (nth fib-seq n)) 

Answer 3

Here's one way of doing it that gives you a bit of exposure to lazy sequences, although it's certainly not really an optimal way of computing the Fibonacci sequence.

Given the definition of the Fibonacci sequence, we can see that it's built up by repeatedly applying the same rule to the base case of '(1 1). The Clojure function iterate sounds like it would be good for this:

user> (doc iterate)
-------------------------
clojure.core/iterate
([f x])
  Returns a lazy sequence of x, (f x), (f (f x)) etc. f must be free of side-effects

So for our function we'd want something that takes the values we've computed so far, sums the two most recent, and returns a list of the new value and all the old values.

(fn [[x y & _ :as all]] (cons (+ x y) all))

The argument list here just means that x and y will be bound to the first two values from the list passed as the function's argument, a list containing all arguments after the first two will be bound to _, and the original list passed as an argument to the function can be referred to via all.

Now, iterate will return an infinite sequence of intermediate values, so for our case we'll want to wrap it in something that'll just return the value we're interested in; lazy evaluation will stop the entire infinite sequence being evaluated.

(defn fib [n]
   (nth (iterate (fn [[x y & _ :as all]] (cons (+ x y) all)) '(1 1)) (- n 2)))

Note also that this returns the result in the opposite order to your implementation; it's a simple matter to fix this with reverse of course.

Edit: or indeed, as amalloy says, by using vectors:

(defn fib [n]
   (nth (iterate (fn [all]
                   (conj all (->> all (take-last 2) (apply +)))) [1 1])
        (- n 2)))