2

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?

Garrett Rowe
  • 1,205
  • 9
  • 13

1 Answers1

2

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
Michał Marczyk
  • 83,634
  • 13
  • 201
  • 212
  • The reasons for the stack overflow are pretty much the same as [here](http://stackoverflow.com/questions/2946764/recursive-function-causing-a-stack-overflow) (<- link to an old question on SO involving the same general principle) -- there are too many lazy seq layers and at some point, the attempt to produce the next element involves too many nested calls (to the thunks stored inside the lazy seq objects). – Michał Marczyk Jun 01 '13 at 04:34
  • After a little studying, I get the code, but why does a queue 'work' for the deferred calculations when a vector doesn't. (using first/next in place of peek/pop)? – Garrett Rowe Jun 01 '13 at 05:10
  • 1
    A vector (or a list) will work if the deferred calculations logically form a stack. Here they don't; instead, they form a queue, since we want LIFO processing. Using a vector as a queue won't work, because calling `next` on a vector returns a seq rather than a vector, and pouring that back into a vector is linear in the number of elements of the seq. (Adding something to the end of a seq is also linear in its length and further additions will be linear in the current length, unless you do it lazily, in which case it's constant time, but you'll eventually blow the stack with too many layers.) – Michał Marczyk Jun 01 '13 at 05:35
  • You could use [core.rrb-vector](https://github.com/clojure/core.rrb-vector) to enable the use of vectors as queues with good big-O complexity, or perhaps use `clojure.core/subvec` with occasional reconstruction of the vector to make things eligible for GC, but there's no point in doing so with a proper persistent queue available. – Michał Marczyk Jun 01 '13 at 05:51
  • "calling next on a vector returns a seq rather than a vector" That comment just explained the answer to a question I didn't even know I had. (conj [1 2 3] 4) yields a different result than (conj (next [0 1 2 3] 4) That explains a lot. – Garrett Rowe Jun 01 '13 at 07:23