Generate lazy seq with recursion in Clojure?

Question

I am new to clojure and currently struggling with loop / recur. The question basically is why my 'custom' range func. does not return a lazy sequence. Is there something wrong with my implementation or you are not supposed to use recursion in this case?

(defn my-range
  [nr]
  (loop [l nr acc '()]
    (if (< l 1)
      acc
      (recur (dec l) (conj acc l)))))

When I run it:

> (time (take 10 (my-range 100000))) ;; "Elapsed time: 85.443 msecs"
> (time (take 10 (range 100000))) ;; "Elapsed time: 0.095 msecs"

The very big time difference leads me to belive the list is first constructed and then 10 taken.

Answer 1

You do not use any lazy constructs in my-range. Since you assemble the list by starting at the end and working your way toward the beginning, the only way to access the first ten elements is to first realize all the other elements.

Lazy sequences start at the beginning and work toward the end, like this:

(defn my-range
  ([end]
   (my-range 1 end))
  ([start end]
   (when (<= start end)
     (lazy-seq (cons start (my-range (inc' start) end))))))

The trick here is that you don't return a realized sequence. Rather, you return an object that stores this function:

#(cons start (my-range (inc' start) end))

When someone calls seq on that object, it will call the above function, cache its result, and return that result. Future calls to seq will simply return the cached result. Note, though, that the second parameter you pass to cons is also a lazy sequence (because a call to my-range returns a lazy-seq), so it, in turn, will only be realized when necessary.

Just for completeness, another way to write this function is as follows:

(defn my-range
  [end]
  (take end (iterate inc' 1)))

This works because iterate and take both return lazy sequences.