On Feb 28, 2009, at 6:25 PM, Mark Engelberg wrote:
> > On Sat, Feb 28, 2009 at 6:09 AM, Rich Hickey <[email protected]> > wrote: >> I think your fundamental hangup is on looking at (rest x) as a >> calculation/effect triggered by a consumer. (rest x) is logically >> just >> a slot lookup that obtains another seq. The laziness of that seq is >> its constructor's problem. > > Right, I'm aware that "rest" isn't an expensive operation. This was > meant to be for illustrative purposes. > > In my actual code, it's more like this: > > Imagine a permutation algorithm that works by storing the sequence in > a vector, and then permuting the various indices to get new sequences. > Simplifying considerably, with no laziness, the heart might look kind > of like this: > > (defn permutation-helper [v indices] > (cons (vector-in-order-of-indices v indices) > (permutations v > (do-complicated-transformation-of-indices-to-next-permutation > indices)))) > > So where should the lazy-seq call go? > > (defn permutation-helper [v indices] > (lazy-seq (cons (vector-in-order-of-indices v indices) > (permutations v > (do-complicated-transformation-of-indices-to-next-permutation > indices))))) > > unnecessarily does the complicated-transform function when you call > first. > > (defn permutation-helper [v indices] > (cons (vector-in-order-of-indices v indices) > (lazy-seq (permutations v > (do-complicated-transformation-of-indices-to-next-permutation > indices))))) > > works better for this case, but unnecessarily does the > vector-in-order-of-indices at the beginning, and whenever you call > rest (not a hugely expensive operation, but let's pretend it is). > > (defn permutation-helper [v indices] > (lazy-seq (cons (vector-in-order-of-indices v indices) > (lazy-seq (permutations v > (do-complicated-transformation-of-indices-to-next-permutation > indices)))))) > > delays everything, but with a whole lot of overhead. That is a false economy. If do-complicated-transformation-of-indices- to-next-permutation is truly expensive it will dwarf the cost of lazy- seq. > > When you have a lot of local definitions that compute things before > the first call, and the helper function is embedded in something else, > deciding where to put lazy-seq becomes even more complicated. > > For the most part, I decided the odd-style worked best, and went with > something like this: > (defn permutation-helper [v indices] > (cons (vector-in-order-of-indices v indices) > (lazy-seq (permutations v > (do-complicated-transformation-of-indices-to-next-permutation > indices))))) > > (defn permutation [sequence] > (lazy-seq (permutation-helper (vec sequence) (initialize-indices))) > > thus delaying the setup and first element of the list, as well as all > the rests. This is all just pseudo-code and not the actual thing, but > it's enough to convey the idea. > There's no problem with this. Clojure features interop between concrete and lazy sequences. If you want to create a concrete seq whose rest is a lazy seq that's no problem, but you have to make sure that creating the first of that concrete seq doesn't force any other seqs. > My point is that lazy-seq gives you a lot more choices than lazy-cons, > but isolating the expensive part, rather than just blindly choosing > even laziness (which is the paradigm it's mainly geared for), can be > complicated. As I mentioned, rewriting filter to delay the call to > rest is an interesting exercise to see the challenge involved > (although I acknowledge that delaying rest isn't inherently useful > given that, like you said, sequence providers will ensure that.rest is > fast). > You are creating your own complexity by trying to avoid another lazy- seq call. There's no challenge. If you have code that produces a sequence, and you'd like to delay that work until the sequence is needed, simply wrap it in a call to lazy-seq. I think this still misses the critical distinction about lazy-seq vs lazy-cons. It's no longer about delaying the work of rest until it is called - it's about rest returning something that doesn't do work until it is needed, which may be never. 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 -~----------~----~----~----~------~----~------~--~---
