Implementation of lazy filter in clojure

Question

On http://clojure.org/lazy, filter is defined this way:

(defn filter
  "Returns a lazy sequence of the items in coll for which
  (pred item) returns true. pred must be free of side-effects."
  [pred coll]
  (let [step (fn [p c]
                 (when-let [s (seq c)]
                   (if (p (first s))
                     (cons (first s) (filter p (rest s)))
                     (recur p (rest s)))))]
    (lazy-seq (step pred coll))))

Is it important that the recursive call is to filter, not to step? If it is, why?

Answer 1

It is with the rest of the code as given here, because it is filter which does the wrapping in lazy-seq. If step called itself, it would do all the filtering at once instead of lazily.

(Updated.) If lazy-seq was added to step's body, step could then call itself and still be lazy. This could be accomplished at least in these two ways:

1. by wrapping the entire body in lazy-seq and replacing both the recursive call to filter and the recur with calls to step; NB. in this case the step function would need to be named (either by replacing the let with letfn, with the appropriate change in syntax, or by adding a name to the fn form: (fn step ...)); the lazy-seq wrapping the outermost call to step would then be unnecessary; also, at this point you could simply not have an inner helper function (just use this approach in filter directly);

2. by leaving the lazy-seq in filter in place and wrapping the recursive call in step (which would now be to step itself) in lazy-seq (with the recur form remaining unchanged).

Note that clojure.core/filter has a different implementation, with separate logic handling chunked sequences and no internal helper functions. In the non-chunked case it operates like the version of step described in 1. above.