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)
(defn stuff [] (lazy-seq (stuff)))
take-while
is limited by x, and x is a current primes 'cap', so it will never ask for more primes over the ones that are already generated. Alsorange
already produces infinite seq, no need to customize it.(drop 3 (range))
, or(iterate inc 3)
take-while
is not even needed here:(fn [x] (some #(zero? (mod x %)) primes))
. and even withoutlazy-seq
:(def primes (remove (fn [x] (some #(zero? (mod x %)) primes)) (iterate inc 2)))
primes
works and wrote about it in a blog post: phillippe.siclait.com/blog/primes-lazy-sequence