How do I implement a lazy “reducing map” function?

Question

I am trying to implement a "reducing map" function. That is, it should return a sequence consisting of the result of applying f to the first 2 items of coll, followed by the result of applying f to that result and the third item in coll, etc.

(def c [[0 0 0 0] [1 0 0 0] [0 1 0 0] [0 0 1 0] [0 0 0 1]])

(defn- sum-vector [v1 v2]
  (map + v1 v2))

(defn reduce-map [f coll & acc]
  (if (< (count coll) 2)
    (if (empty? acc) coll acc)
    (let [head (apply f (take 2 coll))
          tail (drop 2 coll)]
      (recur f (conj tail head) (conj acc head)))))

For example, calling this function like this:

(reduce-map sum-vector c)

should return:

[[1 0 0 0] [1 1 0 0] [1 1 1 0] [1 1 1 1]]

(Actually, it should probably return the first item unmodified as well, to better mimic map, but I can fix that later.)

Right, now, this is what it returns:

((1 1 1 1) (1 1 1 0) (1 1 0 0) (1 0 0 0))

How do I "push" at the end of a(ny) seq?

If I substitute reduce-map for recur, this is what it returns:

(((1 1 1 1) ((1 1 1 0) ((1 1 0 0) ((1 0 0 0))))))

What is the difference between recur and true recursion in my code above?

And, is there a built-in, or better, or more idiomatic, way of implementing reduce-map?

Finally, I'd like the output sequence to be lazy. Do I just wrap the whole thing in lazy-seq?

Answer 1

This sounds a little bit like reductions.

As to "pushing" at the end of seq: in general seqs don't have an "end", cf. (iterate inc 0).

As to "pushing" at the end of a list: lists are not designed for that. Use a vector. Seed your accumulator with [], not nil.

As to lazy-seq: Use "true" recursion instead of recur. Here an example:

(defn integer-seq
  [start]
  (lazy-seq
    (cons start (integer-seq (inc start)))))