Clojure Lazy Sequence Issue

Question

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

There are two ways to make a lazy-seq: call the lazy-seq function, or call a function that calls it. — noisesmith
– noisesmith, Commented Nov 7, 2013 at 1:51
if I use lazy-cat and wrap it, it still doesn't evaluate lazy. it goes until the whole thing overflows. — Justin Thomas
– Justin Thomas, Commented Nov 7, 2013 at 1:57

guilespi · Accepted Answer · 2013-11-07 16:58:38Z

3

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.

edited Nov 7, 2013 at 16:58

answered Nov 7, 2013 at 2:25

guilespi

4,7021 gold badge18 silver badges24 bronze badges

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

4 Comments

DaoWen Over a year ago

Your second solution adds a :less on the end (not inserted between anything) for (__ < :less [1 2 3 2 1 0]).

guilespi Over a year ago

I know, but it passes the tests and was good enough an alternative example without recursion.

amalloy Over a year ago

The advice to never use for is baseless: for is lazy, and is frequently a perfect component of a lazy-seq-producing function. For example, I don't think for is the most readable choice here, but gist.github.com/amalloy/72d98ff89b7ffe665df5 is my solution to this 4clojure problem, modified slightly to use for instead of mapcat.

amalloy Over a year ago

By the way, (cons a (cons b xs)) is better written as (list* a b xs): list* is just a series of calls to cons.

Collectives™ on Stack Overflow

Clojure Lazy Sequence Issue

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related