CODEWITHSUNDEEP
clojurelazy-evaluation
KobbyPemson
KobbyPemson

Reputation: 2539

Simplest Lazy function in Clojure

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

Upvotes: 4

Views: 881

Answers (3)

Retief
Retief

Reputation: 3217

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.

Upvotes: 2

Joost Diepenmaat
Joost Diepenmaat

Reputation: 17771

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.

Upvotes: 2

skuro
skuro

Reputation: 13514

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.

Upvotes: 8

Related Questions