Fibonacci numbers in Clojure

Question

I'm learning Clojure. Quite basic task is to generate Fibonacci sequence. I end up with pretty much copy of the imperative solution (and list is reversed, huh):

(defn n-fib [n]
  (if (= n 1) '(1)
  (loop [i 2 l '(1 1)]
    (if (= i n)
        l
        (recur (inc i) (cons (+ (fst l) (snd l)) l))))))

What is the better way, more functional, concise? Lazy sequences? How to use them? For example, in Haskell using laziness I can write one liner:

fib = 1 : 1 : zipWith + (tail fib)

Note that Haskell solution offers infinite sequence (laziness...). If Clojure both eager and lazy solutions can be (even like get n-length list) I would like to know both.

Update: Another solution I got yields not reversed list, but it uses stack to generate it:

(defn n-fib [n]
  (defn gen [i a b]
    (if (= i 0)
        ()
        (cons (+ a b) (gen (dec i) b (+ a b)))))
  (gen n 0 1))

You could use a vector representation rather than a list. The the last solution with a generator, you should be able to use a stream-cons to avoid using the stack. A stream is a pair where the first term is a value, and the second term is a delayed expression for calculating the rest of the values. — WorBlux
– WorBlux, Commented Jul 8, 2013 at 14:05
In Clojure, def / defn should not be used inside a function; in particular, if you do that, global Vars are created, not locals. To introduce locals, use let or letfn. — Michał Marczyk
– Michał Marczyk, Commented Jul 8, 2013 at 17:23
this is one of the first examples in the famous SICP book in infinite streams (= stream lazy-seq) section. Strongly recommended reading for grasping basic lazy seq concepts mitpress.mit.edu/sicp/full-text/book/… — jJ'
– jJ', Commented Jul 8, 2013 at 20:21

Joe Lehmann · Accepted Answer · 2013-07-08 03:34:58Z

7

You might want to look at http://en.wikibooks.org/wiki/Clojure_Programming/Examples/Lazy_Fibonacci

The equivalent to your lazy Haskell solution is this

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

answered Jul 8, 2013 at 3:34

Joe Lehmann

1,0855 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

demi Over a year ago

I found pretty much on clojuredocs.org/clojure_core/clojure.core/iterate and clojuredocs.org/clojure_core/clojure.core/lazy-seq. Both has Fibonacci seq as sample.

nackjicholson · Accepted Answer · 2019-10-08 04:53:04Z

0

This one doesn't generate the whole sequence, but it is good at finding the nth fibonacci number with an iterative algorithm. I'm only just learning clojure, so I'd be interested what people think about this approach and if there's something wrong with it. It's not pretty, and it's not clever, but it does seem to work.

(defn fib [n]
  (if (< n 2)
    n
    (loop [i 1
           lst 0
           nxt 1]
      (if (>= i n)
        nxt
        (recur (inc i) nxt (+' lst nxt))))))

edited Oct 8, 2019 at 4:53

answered Oct 7, 2019 at 5:45

nackjicholson

4,8594 gold badges40 silver badges36 bronze badges

Collectives™ on Stack Overflow

Fibonacci numbers in Clojure

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related