Re: Bug in clojure.core/take lazy seq?
Indeed you're right, the drop lazy-seq prevents the lookahead. Thanks Meikel for the thoughtful response! On Tuesday, October 25, 2016 at 2:36:26 AM UTC-4, Meikel Brandmeyer (kotarak) wrote: > > In fact, (doall (take (count t) t)) actually realises t completely. But > not because of the doall or take, but because of the count. The problem > is not take, it's the take-while of split-with, which is the trouble. You > know that the input is 50 items long. take-while does not. It has to > check the 51st item to identify the end of the sequence. So it has to hold > onto the head of the tail sequence. No matter what your (take 50 t) does. > This combined with the fact, that you hold onto the head of t with the (count > t) after the (count d). > > drop does obviously not look ahead due to the wrapping lazy-seq. This can > be easily verified in the repl. Please consider, that upon realisation via > seq, the first element of the remaining output has to be realised anyway! > > user> (def s (drop 2 (map #(doto % prn) (list 1 2 3 4 5 > #'user/s > user> (def t (seq s)) > 1 > 2 > 3 > #'user/t > user> > > Again that notwithstanding drop could be optimised to save a wrapping > lazy-seq object in the case we call drop with 0. But that again is an > optimisation, not a bug. An implementation could look like this: > > (defn drop+ > [n coll] > (if (pos? n) > (lazy-seq (drop+ (dec n) (rest coll))) > coll)) > > In general lookahead is not debatable. A sequence function which looks > further ahead then absolutely necessary to perform its function is broken. > > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Bug in clojure.core/take lazy seq?
However, the drop+ does not stop in case the input sequence is exhausted. So more waste there... -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Bug in clojure.core/take lazy seq?
In fact, (doall (take (count t) t)) actually realises t completely. But not because of the doall or take, but because of the count. The problem is not take, it's the take-while of split-with, which is the trouble. You know that the input is 50 items long. take-while does not. It has to check the 51st item to identify the end of the sequence. So it has to hold onto the head of the tail sequence. No matter what your (take 50 t) does. This combined with the fact, that you hold onto the head of t with the (count t) after the (count d). drop does obviously not look ahead due to the wrapping lazy-seq. This can be easily verified in the repl. Please consider, that upon realisation via seq, the first element of the remaining output has to be realised anyway! user> (def s (drop 2 (map #(doto % prn) (list 1 2 3 4 5 #'user/s user> (def t (seq s)) 1 2 3 #'user/t user> Again that notwithstanding drop could be optimised to save a wrapping lazy-seq object in the case we call drop with 0. But that again is an optimisation, not a bug. An implementation could look like this: (defn drop+ [n coll] (if (pos? n) (lazy-seq (drop+ (dec n) (rest coll))) coll)) In general lookahead is not debatable. A sequence function which looks further ahead then absolutely necessary to perform its function is broken. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Bug in clojure.core/take lazy seq?
Certainly the problem is the realizing the tail sequence of the split-with before the head sequence, and take shouldn't be trying to solve that. But I guess I would have thought that (doall (take (count t) t)) would have realized all of t so the head could be released. Indeed, the take* formulation is effectively a look-ahead, realizing one element more than necessary, and I can see how this might be undesirable. I suppose the two have to be weighed against each other and (doall (take (count t) t)) is enough of a special case that it's not worth the lookahead. But take* is the same formulation as drop, no? Is the lookahead problem not a problem there? Thanks for the response! On Mon, Oct 24, 2016 at 7:22 AM, Meikel Brandmeyer (kotarak) wrote: > I think this is not a bug in take, but an unfortunate constellation of > laziness. > > The solution you propose is basically making take looking one step ahead, > which is not take's business. It could be actually quite dangerous to do > so in case take's n was carefully calculated based on some external > stopping condition. > > It just fixes your one-step look ahead special case. However the real > problem is realising the tail sequence of the split-with before the head > sequence. This is not a problem of take either. > > That notwithstanding one could optimise take a little bit by actually > preventing holding onto the tail in the last step, since n is known > upfront. > > (defn take > [n coll] > (when (pos? n) > (lazy-seq > (when-let [s (seq coll)] > (cons (first s) (take+ (dec n) coll)) > > This would “fix” (split-at 50 (range 1e8)) in your example. However, it > wouldn't help with split-with. Here the stopping condition is unknown, > because it is based on a predicate of the input data. There we have to hold > onto the head of the input. > > Takeaway: Always realise t before d. And full t, not some derivative, if > you hold onto its head. > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en > --- > You received this message because you are subscribed to a topic in the > Google Groups "Clojure" group. > To unsubscribe from this topic, visit https://groups.google.com/d/ > topic/clojure/AvL4nurdB1E/unsubscribe. > To unsubscribe from this group and all its topics, send an email to > clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Bug in clojure.core/take lazy seq?
I think this is not a bug in take, but an unfortunate constellation of laziness. The solution you propose is basically making take looking one step ahead, which is not take's business. It could be actually quite dangerous to do so in case take's n was carefully calculated based on some external stopping condition. It just fixes your one-step look ahead special case. However the real problem is realising the tail sequence of the split-with before the head sequence. This is not a problem of take either. That notwithstanding one could optimise take a little bit by actually preventing holding onto the tail in the last step, since n is known upfront. (defn take [n coll] (when (pos? n) (lazy-seq (when-let [s (seq coll)] (cons (first s) (take+ (dec n) coll)) This would “fix” (split-at 50 (range 1e8)) in your example. However, it wouldn't help with split-with. Here the stopping condition is unknown, because it is based on a predicate of the input data. There we have to hold onto the head of the input. Takeaway: Always realise t before d. And full t, not some derivative, if you hold onto its head. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
