Infinitely recursive lazy sequence appears as empty sequence in Clojure

user_10252774 0
Viewed 264

Suppose I wrote:

(def stuff
  (lazy-seq stuff))

When I ask for the value of stuff in REPL, I would expect it to be stuck in an infinite loop, since I'm defining stuff as itself(which pretty much says nothing about this sequence at all).

However, I got an empty sequence instead.

> stuff
()

Why?

Edit: By "recursive" I meant recursive data, not recursive functions.

I'm still confused about why the sequence terminated. As a comparison, the following code is stuck in infinite loop(and blows the stack).

(def stuff
  (lazy-seq (cons (first stuff) [])))

Some background: This question arises from me trying to implement a prime number generator using the sieve of Eratosthenes. My first attempt was:

(def primes
  (lazy-seq (cons 2
                  (remove (fn [x]
                            (let [ps (take-while #(< % x) primes)]
                              (some #(zero? (mod x %)) ps)))
                          (range 3 inf))))) ;; My customized range function that returns an infinite sequence

I figured that it would never work, since take-while would keep asking for more primes even if they could not be calculated yet. So it surprised me when it worked pretty well.

> (take 20 primes)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)
clojure
1 Answers

First, each lazy seq can only be realized once. Second, your definition of stuff doesn't use recursion — stuff isn't a function. If you look at the definition of lazy-seq, you can see that your definition of stuff expands to

(def stuff (new clojure.lang.LazySeq (fn* [] stuff)))

When the fn arg to the clojure.lang.LazySeq constructor is invoked, it returns the same lazy seq that has already been realized. So, when you attempt to print the lazy seq to the REPL, iteration immediately terminates and returns nil.

You can verify that the type of stuff is clojure.lang.LazySeq

user=> (type stuff)
clojure.lang.LazySeq

and that after printing stuff to the REPL, stuff has been realized

user=> (realized? stuff)
false
user=> stuff
()
user=> (realized? stuff)
true

You can use recursion to get the effect that you expected

user=> (defn stuff
         []
         (lazy-seq (stuff)))
#'user/stuff
user=> (stuff) ;; Hangs forever.
user_52739230
Related