Prev: tagbody vs. defun
Next: A Fateman paper
From: Pascal Costanza on 3 Nov 2009 09:24
Thomas F. Burdick wrote:
> On Oct 28, 12:14 pm, Pascal Costanza <p...(a)p-cos.net> wrote:
>> 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.
>
> I think the historical alternative would have been to use tconc and
> lconc:
>
> (let ((new-bindings (list nil)))
> (dolist (binding source-of-new-bindings)
> (tconc new-bindings (process binding)))
> (car (lconc new-bindings existing-bindings)))

Ah, interesting. Wasn't aware of this. Thanks!


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/
First  |  Prev  | 
Pages: 1 2 3
Prev: tagbody vs. defun
Next: A Fateman paper