What is the difference between the Clojure function (nth [coll index]) and the composition (last (take index coll))

Question

I'm trying to work through Stuart Halloway's book Programming Clojure. This whole functional stuff is very new to me.

I understand how

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

generates the Fibonacci sequence lazily. I do not understand why

(last (take 1000000 (fibo)))

works, while

(nth (fibo) 1000000)

throws an OutOfMemoryError. Could someone please explain how these two expressions differ? Is (nth) somehow holding on to the head of the sequence?

Thanks!

Answer 1

I think you are talking about issue that was discussed in google group and Rich Hickey provided patch that solved the problem. And the book, whick was published later, didn't cover this topic.

In clojure 1.3 your nth example works with minor improvements in fibo function. Now, due to changes in 1.3, we should explicitly flag M to use arbitrary precision, or it falls with throwIntOverflow.

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

And with these changes

(nth (fibo) 1000000)

succeed (if you have enough memory)

Answer 2

What Clojure version are you using? Try (clojure-version) on a repl. I get identical results for both expressions in 1.3.0, namely an integer overflow.

For

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

I get correct results for both expressions (a really big integer...).

Answer 3

I think that you may be hitting a specific memory limit for your machine, and not a real difference in function.

Looking at the source code for nth in https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java it does not look like either nth or take are retaining the head.

However, nth uses zero-based indexing, rather than a count by item number. Your code with nth selects the 1000001st element of the sequence (the one at index 1000000). You code with take is returning the final element in a 1000000 element sequence. That's the item with the index 999999. Given how fast fib grows, that last item could be the one that broke the camel's back.

Also, I was checking the 1.3.0 source. Perhaps earlier versions had different implementations. To get your fibo to work properly in 1.3.0 you need to use the arithmetic functions that will promote numbers to bignums:

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