why REVAPPEND?
in [Lisp]
|
Prev: tagbody vs. defun
Next: A Fateman paper
From: Chris Riesbeck on 27 Oct 2009 21:49 Is there some actual usefulness to REVAPPEND? In pre-Common Lisp days, I assumed it was a utility created to define REVERSE, but it made it into CL unscathed. Anyone know why?
From: Joshua Taylor on 27 Oct 2009 22:55 Chris Riesbeck wrote: > Is there some actual usefulness to REVAPPEND? In pre-Common Lisp days, I > assumed it was a utility created to define REVERSE, but it made it into > CL unscathed. Anyone know why? If REVERSE and APPEND each traverse their first argument once, then (APPEND (REVERSE l1) l2) requires O(2*length(l1)) time. REVAPPEND can combine the traversals and bring it down to O(length(l1)). //JT
From: vippstar on 28 Oct 2009 06:35 On Oct 28, 4:55 am, Joshua Taylor <tay...(a)cs.rpi.edu> wrote: > Chris Riesbeck wrote: > > Is there some actual usefulness to REVAPPEND? In pre-Common Lisp days, I > > assumed it was a utility created to define REVERSE, but it made it into > > CL unscathed. Anyone know why? > > If REVERSE and APPEND each traverse their first argument once, then > (APPEND (REVERSE l1) l2) requires O(2*length(l1)) time. REVAPPEND can > combine the traversals and bring it down to O(length(l1)). //JT Still, it occurs often that an (f (g x)) form would be using half operations if f and g are implemented into a single function. Was REVAPPEND standing out so much from all the other cases that it was included in the spec?
From: Pascal Costanza on 28 Oct 2009 07:14 vippstar wrote: > On Oct 28, 4:55 am, Joshua Taylor <tay...(a)cs.rpi.edu> wrote: >> Chris Riesbeck wrote: >>> Is there some actual usefulness to REVAPPEND? In pre-Common Lisp days, I >>> assumed it was a utility created to define REVERSE, but it made it into >>> CL unscathed. Anyone know why? >> If REVERSE and APPEND each traverse their first argument once, then >> (APPEND (REVERSE l1) l2) requires O(2*length(l1)) time. REVAPPEND can >> combine the traversals and bring it down to O(length(l1)). //JT > > Still, it occurs often that an (f (g x)) form would be using half > operations if f and g are implemented into a single function. Was > REVAPPEND standing out so much from all the other cases that it was > included in the spec? A typical situation in an interpreter is that you want to process a list of conses that are supposed to end up as new variable bindings, and put them on top of existing variable bindings. The idiom is this: (let ((new-bindings '())) (dolist (binding source-of-new-bindings) (push (process binding) new-bindings)) (revappend new-bindings existing-bindings)) You would actually use nreconc here, but this is the motivation for those two operators. The reversal of the first argument is necessary because the push leads to a list of new-bindings that is in the wrong order initially. I am not aware of a more efficient, but still elegant solution for this particular use case. Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Chris Riesbeck on 28 Oct 2009 13:36
Pascal Costanza wrote: >>> Chris Riesbeck wrote: >>>> Is there some actual usefulness to REVAPPEND? > > A typical situation in an interpreter is that you want to process a list > of conses that are supposed to end up as new variable bindings, and put > them on top of existing variable bindings. The idiom is this: > > (let ((new-bindings '())) > (dolist (binding source-of-new-bindings) > (push (process binding) new-bindings)) > (revappend new-bindings existing-bindings)) > > You would actually use nreconc here, but this is the motivation for > those two operators. The reversal of the first argument is necessary > because the push leads to a list of new-bindings that is in the wrong > order initially. > > I am not aware of a more efficient, but still elegant solution for this > particular use case. And I take it you can't just push onto existing-bindings directly? I guess I've only seen two pattern for bindings. In pattern matching and backchaining code, bindings extend bindings as you match, and REVAPPEND hasn't been necessary that I've seen. For implementing something like a DO loop, there's old bindings and new bindings, but no appending, just replacement. |