Lazy sequence using loop/recur?

Question

I'd like to write an implementation to an algorithm that produces an infinite sequence of results, where each element represents the calculation of a single iteration of the algorithm. Using a lazy sequence is convenient, as it decouples the logic of the number of iterations (by using take) and burn-in iterations (by using drop) from the implementation.

Here's an example of two algorithm implementations, one that produces a lazy sequence (yadda-lazy), and one that does not (yadda-loop).

(defn yadda-iter
  [v1 v2 v3]

  (+ (first v1)
     (first v2)
     (first v3)))

(defn yadda-lazy
  [len]

  (letfn [(inner [v1 v2 v3]
            (cons (yadda-iter v1 v2 v3)
                  (lazy-seq (inner (rest v1)
                                   (rest v2)
                                   (rest v3)))))]
    (let [base (cycle (range len))]
      (inner base
             (map #(* %1 %1) base)
             (map #(* %1 %1 %1) base)))))

(defn yadda-loop
  [len iters]

  (let [base (cycle (range len))]
    (loop [result nil
           i 0
           v1 base
           v2 (map #(* %1 %1) base)
           v3 (map #(* %1 %1 %1) base)]
      (if (= i iters)
        result
        (recur (cons (yadda-iter v1 v2 v3) result)
               (inc i)
               (rest v1)
               (rest v2)
               (rest v3))))))

(prn (take 11 (yadda-lazy 4)))
(prn (yadda-loop 4 11))

Is there a way to create a lazy sequence using the same style as loop/recur? I like yadda-loop better, because:

• It's more obvious what the initial conditions are and how the algorithm progresses to the next iteration.
• It won't suffer from a stack overflow due to tail optimization.

Answer 1

Your loop version would be better written to (1) pull the addition out of the loop so you don't have to recur on so many sequences, and (2) use conj on a vector accumulator so your results are in the same order as your yadda-lazy.

(defn yadda-loop-2 [len iters]
  (let [v1 (cycle (range len))
        v2 (map * v1 v1)
        v3 (map * v1 v2)
         s (map + v1 v2 v3)]
    (loop [result [], s s, i 0]
      (if (= i iters)
        result
        (recur (conj result (first s)), (rest s), (inc i))))))

However, at this point it becomes clear that the loop is pointless as this is just

(defn yadda-loop-3 [len iters]
   (let [v1 (cycle (range len))
         v2 (map * v1 v1)
         v3 (map * v1 v2)
         s (map + v1 v2 v3)]
     (into [] (take iters s))))

and we might as well pull out the iters parameter, return simply s and take from it.

(defn yadda-yadda [len]
   (let [v1 (cycle (range len))
         v2 (map * v1 v1)
         v3 (map * v1 v2)]
     (map + v1 v2 v3)))

This produces the same results as your yadda-lazy, is also lazy, and is quite clear

(take 11 (yadda-yadda 4)) ;=> (0 3 14 39 0 3 14 39 0 3 14)

You could also, equivalently

(defn yadda-yadda [len] 
  (as-> (range len) s 
        (cycle s)
        (take 3 (iterate (partial map * s) s))
        (apply map + s)))

Addendum

If you are looking for a pattern for converting an eager loop like yours to a lazy-sequence

1. (loop [acc [] args args] ...) -> ((fn step [args] ...) args)
2. (if condition (recur ...) acc) -> (when condition (lazy-seq ...)
3. (recur (conj acc (f ...)) ...) -> (lazy-seq (cons (f ...) (step ...)))

Applying this to your yadda-lazy

(defn yadda-lazy-2 [len iters]
  (let [base (cycle (range len))]
    ((fn step [i, v1, v2, v3]
      (when (< i iters)
        (lazy-seq 
          (cons (yadda-iter v1 v2 v3)
            (step (inc i), (rest v1), (rest v2), (rest v3))))))
      0, base, (map #(* %1 %1) base), (map #(* %1 %1 %1) base))))

And at this point you'd probably want to pull out the iters

(defn yadda-lazy-3 [len]
  (let [base (cycle (range len))]
    ((fn step [v1, v2, v3]
        (lazy-seq 
          (cons (yadda-iter v1 v2 v3)
            (step (rest v1), (rest v2), (rest v3)))))
      base, (map #(* %1 %1) base), (map #(* %1 %1 %1) base))))

So you can

(take 11 (yadda-lazy-3 4)) ;=> (0 3 14 39 0 3 14 39 0 3 14)

And then you might say, hey, my yadda-iter is just applying + on the first and step is applied on the rest, so why not combine my v1, v2, v3 and make this a bit clearer?

(defn yadda-lazy-4 [len]
  (let [base (cycle (range len))]
    ((fn step [vs]
        (lazy-seq 
          (cons (apply + (map first vs))
            (step (map rest vs)))))
      [base, (map #(* %1 %1) base), (map #(* %1 %1 %1) base)])))

And lo and behold, you have just re-implemented variadic map

(defn yadda-lazy-5 [len]
  (let [base (cycle (range len))]
    (map + base, (map #(* %1 %1) base), (map #(* %1 %1 %1) base))))