On Tue, Dec 13, 2011 at 11:25 PM, Alan Malloy <a...@malloys.org> wrote: > On Dec 13, 7:56 pm, Stephen Compall <stephen.comp...@gmail.com> wrote: >> On Tue, 2011-12-13 at 16:28 -0800, Alan Malloy wrote: >> > As you can see, only as many elements are realized as are needed to >> > satisfy the user's request. >> >> Yes, in the expression (conr (conr (conr '( 1 2 3) 4) 6) 7), all the >> lazy-seqs implied by the conr calls must be forced immediately to yield >> (1 . more). It is the same problem with repeatedly concatting to the >> end, and with left-fold in a top-down evaluation scheme like Haskell: >> you can run out of stack if you must travel deep to get to the first >> element. > > I see. You're making a subtler point than I realized, and you're right > there. Repeated applications of conr need to be resolved all at once, > but conr'ing one item onto an already-realized collection doesn't > cause anything new to be realized until the element itself is needed.
One way to mitigate it would be to use a datastructure with a seq and a vector: conr on a seq would produce one of these with the conr'd item the sole element of the vector, and conr on one of these datastructures would conj the item onto the vector. The datastructure would behave as a seq: first on the datastructure would return first on the seq part, and next would return a datastructure with the seq part nexted -- only, if the seq had only one element, instead with (seq the-vector-part) as the seq part and an empty vector part. An invariant would be maintained that the seq part is nil iff the whole thing is empty. Of course, such a datastructure is a queue, and it's not too much more work to turn it into a deque. Adding at both ends in O(1) and peeking/popping at the front is already in there. Peeking/popping at the rear is trickier, because a naive implementation is O(n) if the vector part happens to be empty. Any time the vector part would become empty you'd have to split the data in half between the seq part and the vector part, in a kind of reversal of how ArrayLists and vectors grow in amortized O(1). The invariant would now be that if there are at least two elements both parts are nonempty, if there's one element the vector part is empty, and if there's none the seq part is nil. (And nobody give me any guff about the vector operations actually being O(log_32 n); on present and near-future hardware I don't think log_32 n will get much above 6 or 7, so for all practical purposes it differs from O(1) by a constant factor of overhead. The work being done on finger trees might enable deques with "true" O(1) peeks at both ends, if the trees hold direct references to their end elements in their roots -- but then I'd expect O(log n) adds and pops at both ends, since the depth will need to be walked to do those.) -- 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
