14

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.
Improve this question
2
  • 5
    Lazy sequences won't overflow the stack anyway. In order to overflow the stack, you need to keep building up stack frames, whereas a lazy sequence just returns a sequence with the current item in the head and a thunk for the tail. In other words, the first call to inner will return before the next call occurs, so the stack stays at a constant depth. Commented Feb 11, 2014 at 20:42
  • 2
    You won't get a stack overflow error, but you can get an OutOfMemoryError if you hang onto the head (you'll overflow the memory, not the stack). Commented Feb 11, 2014 at 22:55

3 Answers 3

Reset to default
32

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))))
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

This doesn't really answer my question. But your code inspired me to re-code the implementation using iterate and map instead of using lazy-seq and cons. Part of the problem was that I was co-recurring over several items (v1, v2, v3), and it wasn't immediately obvious how to do so with iterate, since iterate only allows one element. That was solved by wrapping all co-recurring elements in a vector and deconstructing it to get the individual co-recurring elements back from the vector.
@SamadLotia I'm not sure I understood your question then, but see the addendum I just edited in.
5

@A.Webb's answer is perfect, but if your love for loop/recur overcomes his arguments, know that you can still combine both styles of recursion.

For example, take a look at the implementation of range:

(defn range
  (...)
  ([start end step]
   (lazy-seq
    (let [b (chunk-buffer 32)
          comp (cond (or (zero? step) (= start end)) not=
                     (pos? step) <
                     (neg? step) >)]
      (loop [i start]                        ;; chunk building through loop/recur
        (if (and (< (count b) 32)
                 (comp i end))
          (do
            (chunk-append b i)
            (recur (+ i step)))
          (chunk-cons (chunk b) 
                      (when (comp i end) 
                        (range i end step))))))))) ;; lazy recursive call

Here's another example, an alternate implementation of filter:

(defn filter [pred coll]
  (letfn [(step [pred coll]
            (when-let [[x & more] (seq coll)]
              (if (pred x)
                (cons x (lazy-seq (step pred more))) ;; lazy recursive call
                (recur pred more))))]                ;; eager recursive call
    (lazy-seq (step pred coll))))
Improve this answer

2 Comments

I did look at the code for range and filter. Indeed, my solution for a lazy sequence (yadda-lazy) follows the form of filter, which is precisely what I was trying to avoid. range just looks way too complicated to replicate.
I agree, range is a mouthful. But I don't understand why you prefer the loop/recur style. From the issues you mentioned, the stack overflow risk has been addressed ; and I don't see how the initial conditions are more obvious - is it that they are introduced first ?
0

The Tupelo library has a new lazy-gen/yield feature that mimics generator functions in Python. It can generate a lazy sequence from any point in a looping structure. Here is version of yadda-loop that shows lazy-gen & yield in action:

(ns tst.xyz
  (:use clojure.test tupelo.test)
  (:require [tupelo.core :as t] ))

(defn yadda-lazy-gen
  [len iters]
  (t/lazy-gen
    (let [base (cycle (range len))]
      (loop [i      0
             v1     base
             v2     (map #(* %1 %1) base)
             v3     (map #(* %1 %1 %1) base)]
        (when (< i iters)
          (t/yield (yadda-iter v1 v2 v3))
          (recur
            (inc i)
            (rest v1)
            (rest v2)
            (rest v3)))))))

Testing tst.clj.core
(take 11 (yadda-lazy 4))  => (0 3 14 39 0 3 14 39 0 3 14)
(yadda-loop 4 11)         => (0 3 14 39 0 3 14 39 0 3 14)
(yadda-lazy-gen 4 11)     => (0 3 14 39 0 3 14 39 0 3 14)

Ran 1 tests containing 1 assertions.
0 failures, 0 errors.
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.