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.

Standard range starts at 0, not 1. This does not affect the issue. — Thumbnail
– Thumbnail, Commented Mar 10, 2016 at 15:16

Sam Estep · Accepted Answer · 2016-03-10 12:36:58Z

14

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.

edited Mar 10, 2016 at 12:36

answered Mar 10, 2016 at 12:30

Sam Estep

13.4k3 gold badges40 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

skamsie Over a year ago

Thank you very much. With my very limited clojure knowledge I get the idea. However I do not understand why you are using inc' instead of inc?

Sam Estep Over a year ago

Try (inc Long/MAX_VALUE) and (inc' Long/MAX_VALUE).

Collectives™ on Stack Overflow

Generate lazy seq with recursion in Clojure?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related