Integer overflow using lazy sequences in Clojure

Question

I'm just learning to use lazy sequences in Clojure, and I'm not sure what I'm doing wrong in the following code:

(defn sum [seqn]
  (reduce + seqn))

(defn fib
  ([] (concat [0 1] (fib 0 1)))
  ([a b] (lazy-seq (cons (+ a b) (fib b (+ a b))))))

(defn up-to [n seqn]
  (filter (fn [x] (< x n)) seqn))

(sum (up-to 100 (fib))) => ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1388)

The numbers being summed shouldn't be larger than 100, so what is causing the integer overflow?

Answer 1

Filtering an infinite seq produces an infinite seq and reducing over this causes filter to keep looking for another matching item even after the predicate stops returning true.

Replace filter with take-while. The infinite sequence generated by (fib) will cause filter to run forever, but before that it will break due to the ArithmeticException you're experiencing. take-while will stop further evaluation of the list after the (fn [x] (< x n)) predicate evaluates to false.

(defn up-to [n seqn]
  (take-while (fn [x] (< x n)) seqn))

(sum (up-to 100 (fib))) ;; => 232

Answer 2

starting with clojure 1.3.0 numbers don't auto-promote to bigInt/bigDecimal.

to fix this use +' instead

your 100th fibinachi number is too large for an integer

user> (nth (fib) 100)
354224848179261915075N