Determining the cause of StackOverflow in code using lazy-seq

Question

I have the following snippet:

(defn explode [e]
  (seq [e e e e]))

(defn f [coll]
  (when-first [e coll]
    (cons e 
          (lazy-seq (f (lazy-cat (next coll)
                                 (explode e)))))))

When I try to access an element, I get a StackOverflow error:

user=> (nth (f (seq [1 2 3])) 1000)
3
user=> (nth (f (seq [1 2 3])) 10000)

StackOverflowError   clojure.core/concat/fn--3923 (core.clj:678)

How can I structure this code in a way that doesn't blow the stack?

Michał Marczyk Michał Marczyk · Accepted Answer · 2013-06-01T02:57:42

You'll have to keep track of the remaining work explicitly, perhaps like so:

(defn f [coll]
  (letfn [(go [xs q]
            (lazy-seq
             (cond
               (seq xs)
               (cons (first xs)
                     (go (next xs) (conj q (explode (first xs)))))
               (seq q)
               (go (peek q) (pop q)))))]
    (go coll clojure.lang.PersistentQueue/EMPTY)))

From the REPL:

(nth (f [1 2 3]) 1000)
;= 3
(nth (f [1 2 3]) 10000)
;= 2

;; f-orig is f as found in the question text
(= (take 1000 (f-orig [1 2 3])) (take 1000 (f [1 2 3])))
;= true

Determining the cause of StackOverflow in code using lazy-seq

1 Answers