On Dec 8, 2008, at 8:56 PM, Stephen C. Gilardi wrote:
> I think I finally see the problem. The "rest expression" in filter's
> call to lazy-cons has a reference to "coll" in it. That's all it
> takes for coll to be retained during the entire calculation of the
> rest.
>
> (defn filter
> "Returns a lazy seq of the items in coll for which
> (pred item) returns true. pred must be free of side-effects."
> [pred coll]
> (when (seq coll)
> (if (pred (first coll))
> (lazy-cons (first coll) (filter pred (rest coll)))
> (recur pred (rest coll)))))
>
> The stye of fix that occurs to me involves peeling off coll from
> (frest coll) and (rrest coll) before continuing the lazy evaluation.
>
> Posting so someone else can beat me to the answer. :-)
>
I'm sorry I haven't chimed in sooner. I fully understand this. Yes,
it's the closure over coll in the rest portion, which means that after
finding some match, a subsequent call to rest that needs to skip a lot
will create a window over the interval where the seq will be realized.
Eagerly evaluating (rest coll) won't work - the result will still be
in the closure while the recursion occurs. The only solutions involve
mutation in filter. Here's one way:
(defn filter
[pred coll]
(let [sa (atom (seq coll))
step (fn step []
(when-let [s @sa]
(let [x (first s)]
(if (pred x)
(lazy-cons x (do (swap! sa rest) (step)))
(do (swap! sa rest)
(recur))))))]
(step)))
But it's not pretty. Fortunately, this segues with work I have been
doing on I/O and generators/streams. This will let you write things
like:
(defn filter-stream
"Returns a stream of the items in strm for which
(pred item) returns true. pred must be free of side-effects."
[pred strm]
(stream
#(let [x (next! strm)]
(if (or (eos? x) (pred x)) x (recur)))))
(defn filter
"Returns a lazy seq of the items in coll for which
(pred item) returns true. pred must be free of side-effects."
[pred coll]
(stream-seq (filter-stream pred (stream coll))))
I'm still not done with this yet, so anyone who is stuck can use the
former version.
Rich
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
