On Dec 14, 1:18 am, Cedric Greevey <cgree...@gmail.com> wrote: > On Wed, Dec 14, 2011 at 3:12 AM, Alan Malloy <a...@malloys.org> wrote: > > 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. > > Should be better documented. > > Is it a fully fledged deque?
Yes and yes. -- 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
