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? -- 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
