Simplest Lazy function in Clojure

Question

I'm having a tough time understanding laziness.

Can someone help me understand why my function below is not lazy

(defn my-red
    ([f coll] (my-red f (first coll) (rest coll) ))
    ([f init coll] 
      (let [mr (fn [g i c d] 
            (if (empty? c) d 
        (recur  g (g  i (first c)) (rest c)  (conj d (g  i (first c)) ))))] 
    (lazy-seq (mr f init coll [])))))

whereas this example given on clojure.org/lazy is

(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))))

skuro · Accepted Answer · 2012-02-20 13:54:45Z

8

The laziness in filter comes from the call to filter in the if branch of the recursive loop. That's where the code hits another lazy-seq and stops evaluating the seq until another element is requested.

Your implementation of my-red hits a call to lazy-seq one and only one time, meaning that your seq is either not evaluated at all or completely evaluated.

answered Feb 20, 2012 at 13:54

skuro

13.5k2 gold badges50 silver badges68 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Joost Diepenmaat · Accepted Answer · 2012-02-20 14:03:31Z

2

The mr function will just recur through the whole of coll. Perhaps your indentation is misleading you. correctly indented, and with some useless parameters removed the function looks something like this:

(defn my-red
  ([f coll] (my-red f (first coll) (rest coll) ))
  ([f init coll] 
     (let [mr (fn [i c d] 
                (if (empty? c)
                  d 
                  (recur (f i (first c))
                         (rest c)
                         (conj d (f i (first c))))))] 
       (lazy-seq (mr init coll [])))))

Basically, you're wrapping (lazy-seq) around the mr function, which does all the work in one big recur loop.

answered Feb 20, 2012 at 14:03

Joost Diepenmaat

17.8k3 gold badges48 silver badges55 bronze badges

Comments

Retief · Accepted Answer · 2012-02-20 20:37:26Z

All lazy-seq does is take its argument and delay execution of it. In order to produce a true lazy sequence, every link must be wrapped in a lazy-seq call. The "granularity" of the lazyness is how much work is done between calls to lazy-seq. The one way to get around this is to use the higher level functions that return a lazy seq.

Additionally, tail recursion and lazyness are mutually exclusive. This does not cause stack overflows because at each step, the recursive call is wrapped up into a lazy seq and returned. If the caller then tries to evaluate the lazy seq, the recursive call is called, but it is being called by the original caller of the sequence function, not the sequence function itself, which means that the stack doesn't grow. This is somewhat similar to the idea of implementing optimized tail recursion via trampolines (see Clojure's trampoline function).

Here is a version that is lazy:

(defn my-red
  ([f coll] (my-red f (first coll) (rest coll) ))
  ([f init coll] 
   (let [mr (fn mr [g i c] 
              (if (empty? c)
                nil
                (let [gi (g  i (first c))]
                  (lazy-seq (cons gi (mr g gi (rest c)))))))] 
     (lazy-seq (mr f init coll)))))

Note how each run of mr immediately returns either nil or a lazy seq, and the recursive call is from within the lazy-seq call.

Collectives™ on Stack Overflow

Simplest Lazy function in Clojure

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related