On Thu, Jul 17, 2014 at 7:54 PM, Mark P <[email protected]> wrote: > > I notice in your lazy version (below), you preface the last cons with a > lazy-seq call, but do not do the same with the other cons calls (within the > first recur form). I know it was only the last line that previously had a > conj call and so participated in this transformation... but I'm wondering > why you wouldn't also use lazy-seq with the other cons-involving line? >
The lazy-seq is necessary because of the recursive call that isn't in tail-call position (so you can't use recur). One way to think about it is that at that point, we know what the first element of the sequence is going to be, so the lazy-seq lets us return immediately with the computed first element and a description of the further computation that can compute the rest on demand. lazy-seq is the secret sauce that makes it so non-tail recursive calls don't overflow the stack. That's because the sequence is prompted for one element at a time from an outside consumer -- as you noted in one of your messages, it's a lot like what trampolining does. So to make sure you don't have stack overflow, all you have to do is make sure that you use bounded stack space in the process of computing the next element. The other calls to cons are just part of the process of coming up with the next element, basically sticking "stuff to be computed" on the front of the list as a trick to avoid a separate accumulator. Because they are inside a recur, no additional stack is consumed (the list grows, but that's a heap-allocated data structure, so not a problem). > > Another question... > > I notice that you bound ys to (rest xs), in contrast to my choice of (next > xs) in some of my implementations. I realize this is probably a minor > point, but just wondering whether (rest xs) was a deliberate choice of > yours, or just habit. I realize that rest maximizes laziness in contrast > to next, but do we want maximum laziness here? > One idiom is to use to use (next xs), and then you can test against it being nil to determine whether it is empty or not. But to use that idiom, you have to be very careful to make sure you call seq on the sequence that is passed as an input to the function (which you did in your version). If you do that and are careful, the performance of next/nil? is slightly better than rest/empty?. But I've gotten burned enough times, I simply prefer to use empty? as my test, and then you might as well use rest rather than next. It's my own preference. I think many people in the Clojure community prefer to seq the input and then next/nil?. Either is fine. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to [email protected] Note that posts from new members are moderated - please be patient with your first post. 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 --- 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 [email protected]. For more options, visit https://groups.google.com/d/optout.
