Why is my lazy recursive Clojure function being realized?

Question

I'm trying to solve a 4Clojure problem (sequence reductions), and I've hit a wall. The problem is to reimplement the reductions function.

It seems to me like this function should return a lazy sequence, but it doesn't - evaluating (take 5 (redux + (range))) results in an infinite loop.

Here's my code:

(defn redux
  ([f coll] 
      (redux f (first coll) (rest coll)))
  ([f val coll] 
      ((fn red [val coll s]
           (if (empty? coll)
               s
               (lazy-seq
                  (let [val (f val (first coll))]
                    (red val 
                         (rest coll)
                         (conj s val))))))
       val coll [val])))

Why is this function not returning a lazy sequence?

Answer 1

There are a few misconceptions in the code. noisesmith pointed out on #clojurians chat (and Josh's comment stated as well) the following points:

1. There is no step in the above function where you can evaluate the head and not the tail of a list.
2. It does an immediate self recursion, and to get the n+1 element, you need to do the recursive call.
3. lazy-seq should always have a call to cons or some similar function that lets you return the next item of the list without recurring.
4. conj is never lazy, and vectors are never lazy.
5. You cannot append to a list without realizing the entire thing.

I modified the code to the following:

(fn redux
  ([f coll] 
      (redux f (first coll) (rest coll)))
  ([f val coll] 
      (cons val
        ((fn red [val coll]
           (lazy-seq
             (when-not (empty? coll)
               (let [val (f val (first coll))]
                 (cons val (red val (rest coll)))))))
          val coll))))

Note the use of cons instead of conj.