CODEWITHSUNDEEP
clojure
Justin Thomas
Justin Thomas

Reputation: 5848

Clojure Lazy Sequence Issue

I'm working on 4clojure problems and a similar issue keeps coming up. I'll write a solution that works for all but one of the test cases. It's usually the one that is checking for lazy evaluation. The solution below works for all but the last test case. I've tried all kinds of solutions and can't seem to get it to stop evaluating until integer overflow. I read the chapter on lazy sequences in Joy of Clojure, but I'm having a hard time implementing them. Is there a rule of thumb I'm forgetting, like don't use loop or something like that?

; This version is non working at the moment, will try to edit a version that works
(defn i-between [p k coll]
  (loop [v [] coll coll]
     (let [i (first coll) coll (rest coll) n (first coll)]
        (cond (and i n)
          (let [ret (if (p i n) (cons k (cons i v)) (cons i v))]
            (recur ret coll))
          i
          (cons i v )
        :else  v))))

Problem 132

Ultimate solution for those curious:

(fn i-between [p k coll]
  (letfn [(looper [coll]
     (if (empty? coll) coll
       (let [[h s & xs] coll 
          c (cond (and h s (p h s))
                   (list h k )
                  (and h s)
                   (list h )
                  :else (list h))]
          (lazy-cat c (looper (rest coll))))
   ))] (looper coll)))

Upvotes: 1

Views: 414

Answers (1)

guilespi
guilespi

Reputation: 4702

When I think about lazy sequences, what usually works is thinking about incremental cons'ing

That is, each recursion step only adds a single element to the list, and of course you never use loop.

So what you have is something like this:

(cons (generate first) (recur rest))

When wrapped on lazy-seq, only the needed elements from the sequence are realized, for instance.

 (take 5 (some-lazy-fn))

Would only do 5 recursion calls to realize the needed elements.

A tentative, far from perfect solution to the 4clojure problem, that demonstrates the idea:

(fn intercalate 
  [pred value col]
  (letfn [(looper [s head]
            (lazy-seq 
              (if-let [sec (first s)]
                (if (pred head sec)
                  (cons head (cons value (looper (rest s) sec)))
                  (cons head (looper (rest s) sec)))
               (if head [head] []))))]
    (looper (rest col) (first col))))

There, the local recursive function is looper, for each element tests if the predicate is true, in that case realizes two elements(adds the interleaved one), otherwise realize just one.

Also, you can avoid recursion using higher order functions

(fn [p v xs]
   (mapcat
    #(if (p %1 %2) [%1 v] [%1])
    xs
    (lazy-cat (rest xs) (take 1 xs))))

But as @noisesmith said in the comment, you're just calling a function that calls lazy-seq.

Upvotes: 3

Related Questions