On Dec 13, 8:37 pm, Cedric Greevey <cgree...@gmail.com> wrote: > 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.)
This queue already exists: clojure.lang.PersistentQueue. -- 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
