What is the recommended way to Push/Pop for the tail end of lists?
I've come up with the following. I know the pop-end implementation
isn't the most efficient, but simple imp is important to me, too.
BTW, is there any advantage to making these inline functions instead
of macros? Wouldn't the two techniques pretty much accomplish the
same in this case?
Thanks
-lv
(defmacro push-end (list item)
`(if (null ,list)
(setf ,list (list ,item))
(nconc ,list (list ,item))))
(defmacro pop-end (place)
`(prog1
(first (last ,place))
(if (null (second ,place))
(setf ,place nil)
(rplacd (last ,place 2) nil))))
vanekl <·····@acd.net> writes:
I'm normally pretty flexible on style choices, leaving them to
personal taste, but I'm going to risk leaning a bit heavily to make
sure you go study up on the relevant information to allow you to code
well in CL in the future without confusing yourself...
> What is the recommended way to Push/Pop for the tail end of lists?
Not to do it.
CONS is O(1) and your alternatives are O(n).
CL's list datatype is not the list datatype used by other languages.
It is a pointer chain, not a vector nor extensible vector.
Normally in Lisp, if you need this at all, you cons up the list you
want to put on the end backward, then nconc the result once. The very
abstraction of PUSH/POP suggests you're going to do this repeatedly,
and since you ask in terms of the word "recommend" it suggests you're
going to push this on others or have them push it on you. I don't
think that's wise.
Show a sample _use_ of this macro and people will show you the
recommended alternative.
Alternatively, use one of the LOOP keywords, since at least LOOP knows
what you're up to and can conspire to make it better by keeping a
trailing pointer in some circumstances.
> I've come up with the following. I know the pop-end implementation
> isn't the most efficient,
The only efficiency of interest here should be algorithmic efficiency,
which will dominate in a real computation.
> but simple imp is important to me, too.
Why? The point of packaging something for repeated and recommended
use is to take the pain once rather than many times. To focus on the
implementation cost is to focus on something you could put behind you,
and then you could move on to guilt-free use. In this case, you're
going throught he effort of soliciting group opinion and then saying
you don't want to worry about making it efficient, and then you're
going to want to use the result repeatedly or suggest others do even
when you know it was a design constraint that it prefer your ease of
implementation over quality of use (which would be space or speed).
There is a reason that CL's optimize declaration does not contain
DESIGN-SPEED among the qualities.
> BTW, is there any advantage to making these inline functions instead
> of macros?
Since you're doing (SETF ,LIST ...) in the PUSH-END case, it cannot be
done by function anyway.
Ordinarily, it's good to make something a function rather than a macro
the two are possible.
> Wouldn't the two techniques pretty much accomplish the same in this case?
No. Consider trying to do MAPCAR or APPLY.
But in this case the issue is that only a macro can do the job as you've
described it, so there is no choice.
> Thanks
> -lv
>
>
> (defmacro push-end (list item)
> `(if (null ,list)
> (setf ,list (list ,item))
> (nconc ,list (list ,item))))
>
>
> (defmacro pop-end (place)
> `(prog1
> (first (last ,place))
> (if (null (second ,place))
> (setf ,place nil)
> (rplacd (last ,place 2) nil))))
Although, strictly speaking, this is still O(n), you're actually making
it twice as slow by doing the call to LAST twice here. Constant factors
don't dominate in large computations, but they do in smaller ones.
You might also want to consider making an adjustable array and using
vector-push-extend.
Thanks for your response. Comments embedded.
Kent M Pitman wrote:
> vanekl <·····@acd.net> writes:
>
> I'm normally pretty flexible on style choices, leaving them to
> personal taste, but I'm going to risk leaning a bit heavily to make
> sure you go study up on the relevant information to allow you to code
> well in CL in the future without confusing yourself...
>
>> What is the recommended way to Push/Pop for the tail end of lists?
>
> Not to do it.
>
> CONS is O(1) and your alternatives are O(n).
Understood, which is why I was asking if there was a better way.
> CL's list datatype is not the list datatype used by other languages.
> It is a pointer chain, not a vector nor extensible vector.
>
> Normally in Lisp, if you need this at all, you cons up the list you
> want to put on the end backward, then nconc the result once. The very
> abstraction of PUSH/POP suggests you're going to do this repeatedly,
> and since you ask in terms of the word "recommend" it suggests you're
> going to push this on others or have them push it on you. I don't
> think that's wise.
Actually, this is just "pushing" it on my own code.
> Show a sample _use_ of this macro and people will show you the
> recommended alternative.
I need to use a deque data structure, something that can be manipulated
at both ends.
> Alternatively, use one of the LOOP keywords, since at least LOOP knows
> what you're up to and can conspire to make it better by keeping a
> trailing pointer in some circumstances.
>
>> I've come up with the following. I know the pop-end implementation
>> isn't the most efficient,
>
> The only efficiency of interest here should be algorithmic efficiency,
> which will dominate in a real computation.
I also consider simplicity, clarity of code, developer maintenance time,
and the associated costs.
>> but simple imp is important to me, too.
>
> Why? The point of packaging something for repeated and recommended
> use is to take the pain once rather than many times. To focus on the
> implementation cost is to focus on something you could put behind you,
> and then you could move on to guilt-free use. In this case, you're
> going throught he effort of soliciting group opinion and then saying
> you don't want to worry about making it efficient, and then you're
> going to want to use the result repeatedly or suggest others do even
> when you know it was a design constraint that it prefer your ease of
> implementation over quality of use (which would be space or speed).
> There is a reason that CL's optimize declaration does not contain
> DESIGN-SPEED among the qualities.
Point taken, but as hardware becomes faster and faster, and software
development becomes more costly, there comes a point where
simple to maintain macros/functions provide a better economic trade off
than weighing only computation speed and memory requirements.
I'm not a big believer in all-powerful macros that try to do it all.
I prefer getting something that works, is simple and reasonably efficient.
Afterwards, if it becomes a bottleneck, I can go back and either add a
new function/macro or redefine previous work. This goes double when
prototyping.
>> BTW, is there any advantage to making these inline functions instead
>> of macros?
>
> Since you're doing (SETF ,LIST ...) in the PUSH-END case, it cannot be
> done by function anyway.
>
> Ordinarily, it's good to make something a function rather than a macro
> the two are possible.
>
>> Wouldn't the two techniques pretty much accomplish the same in this case?
>
> No. Consider trying to do MAPCAR or APPLY.
>
> But in this case the issue is that only a macro can do the job as you've
> described it, so there is no choice.
>
>> Thanks
>> -lv
>>
>>
>> (defmacro push-end (list item)
>> `(if (null ,list)
>> (setf ,list (list ,item))
>> (nconc ,list (list ,item))))
>>
>>
>> (defmacro pop-end (place)
>> `(prog1
>> (first (last ,place))
>> (if (null (second ,place))
>> (setf ,place nil)
>> (rplacd (last ,place 2) nil))))
>
> Although, strictly speaking, this is still O(n), you're actually making
> it twice as slow by doing the call to LAST twice here. Constant factors
> don't dominate in large computations, but they do in smaller ones.
Yep, I alluded to this wart when I said I knew this wasn't the most
efficient algo.
> You might also want to consider making an adjustable array and using
> vector-push-extend.
I guess I should have mentioned that I was trying to implement a deque,
and there's going to be a bunch of pushing and popping from both ends.
I don't think an array is going to help me much in this case.
Thanks,
-lv
vanekl <·····@acd.net> writes:
> I guess I should have mentioned that I was trying to implement a deque,
> and there's going to be a bunch of pushing and popping from both ends.
> I don't think an array is going to help me much in this case.
You probably want to make a structure (using defstruct or defclass)
that contains a pointer to the head and the tail.
You clearly don't just want what lisp calls a list, so trying to add
operations relates to lists without adding the additional
infrastructure to make them work is not the right thing.
No matter how much hardware speeds up, it cannot overcome algorithmic
concerns. Of course, if an application knows the algorithmic concerns
aren't an issue, that's something else--but general-purpose routines
may not presuppose such things, IMO, unless they put it in their
name. e.g.,
SLOWLY-PUSH-ONTO-WRONG-END-SO-DON\'T-USE-ME-VERY-OFTEN-OR-IN-TIGHT-INNER-LOOPS
would be an ok name for a general-purpose operation. :)
Kent M Pitman wrote:
> vanekl <·····@acd.net> writes:
>
>> I guess I should have mentioned that I was trying to implement a deque,
>> and there's going to be a bunch of pushing and popping from both ends.
>> I don't think an array is going to help me much in this case.
>
> You probably want to make a structure (using defstruct or defclass)
> that contains a pointer to the head and the tail.
>
> You clearly don't just want what lisp calls a list, so trying to add
> operations relates to lists without adding the additional
> infrastructure to make them work is not the right thing.
>
> No matter how much hardware speeds up, it cannot overcome algorithmic
> concerns. Of course, if an application knows the algorithmic concerns
> aren't an issue, that's something else--but general-purpose routines
> may not presuppose such things, IMO, unless they put it in their
> name. e.g.,
>
> SLOWLY-PUSH-ONTO-WRONG-END-SO-DON\'T-USE-ME-VERY-OFTEN-OR-IN-TIGHT-INNER-LOOPS
>
> would be an ok name for a general-purpose operation. :)
Yeah, I think if I rename it,
push-on-ass-end
it will be suitably cautionary (at least for most people).
On Feb 27, 8:55 am, vanekl <·····@acd.net> wrote:
> I need to use a deque data structure, something that can be manipulated
> at both ends.
Ruby:
>> irb --prompt xmp
d = [3,'foo',4,5]
==>[3, "foo", 4, 5]
d << 6
==>[3, "foo", 4, 5, 6]
d.push(7)
==>[3, "foo", 4, 5, 6, 7]
d.unshift(2)
==>[2, 3, "foo", 4, 5, 6, 7]
d.pop
==>7
d
==>[2, 3, "foo", 4, 5, 6]
d.shift
==>2
d
==>[3, "foo", 4, 5, 6]
On Feb 27, 1:17 pm, William James <·········@yahoo.com> wrote:
> On Feb 27, 8:55 am, vanekl <·····@acd.net> wrote:
> > I need to use a deque data structure, something that can be manipulated
> > at both ends.
> > [Kaz: and he's willing to step into dog shit to get this! ]
>
> Ruby:
Response now matches requirements.
William James wrote:
> On Feb 27, 8:55 am, vanekl <·····@acd.net> wrote:
>
>> I need to use a deque data structure, something that can be manipulated
>> at both ends.
>
> Ruby:
>
>>> irb --prompt xmp
> d = [3,'foo',4,5]
> ==>[3, "foo", 4, 5]
> d << 6
> ==>[3, "foo", 4, 5, 6]
> d.push(7)
> ==>[3, "foo", 4, 5, 6, 7]
> d.unshift(2)
> ==>[2, 3, "foo", 4, 5, 6, 7]
> d.pop
> ==>7
> d
> ==>[2, 3, "foo", 4, 5, 6]
> d.shift
> ==>2
> d
> ==>[3, "foo", 4, 5, 6]
You left out just one little thing: Ruby is 10X slower
than CL and it's interpreter is so slow Matz himself says
Ruby sux.
You didn't think you were going to post that w/o
anybody saying nuttin, did you?
-lv
On Feb 27, 3:28 pm, vanekl <·····@acd.net> wrote:
> You didn't think you were going to post that w/o
> anybody saying nuttin, did you?
Being a COMMUNE-LISP user, you know nothing of spelling or
logic. First, to correct the spelling:
anybody saying nothing, did you?
Now, to correct the logic:
anybody saying anything, did you?
Let's improve the style.
Did you think when you made that post that none of us
COMMUNE-LISP weenies would howl as a scalded cat?
--
Common LISP is the PL/I of Lisps.
--- Jeffrey M. Jacobs
William James wrote:
> On Feb 27, 3:28 pm, vanekl <·····@acd.net> wrote:
>
>> You didn't think you were going to post that w/o
>> anybody saying nuttin, did you?
>
> Being a COMMUNE-LISP user, you know nothing of spelling or
> logic. First, to correct the spelling:
>
> anybody saying nothing, did you?
>
> Now, to correct the logic:
>
> anybody saying anything, did you?
>
> Let's improve the style.
>
> Did you think when you made that post that none of us
> COMMUNE-LISP weenies would howl as a scalded cat?
>
> --
> Common LISP is the PL/I of Lisps.
> --- Jeffrey M. Jacobs
Touched a nerve, I see. Interesting that my
damning points were excised w/ neither snip
nor retort. Talk about logic <cough>or not</cough>.
--
[Secret confession: if Ruby had a compiler as kick-ass
as Lisp's, and Lisp only had a lame-ass compiler, I'd
switch in a heartbeat. But to ensure animosity btn
the two camps, let's pretend I dinnut admit that, and
you instead rail about how I purposely misspell some
of my big words, shall we?]
On Feb 27, 4:03 am, vanekl <·····@acd.net> wrote:
> What is the recommended way to Push/Pop for the tail end of lists?
In a loose order of preference:
- Use LOOP with COLLECT if possible
- REVERSE (or NREVERSE, if you can get away with it), then push and
pop at the head of the list, then NREVERSE when finished.
- Some destructive hack in which you maintain a pointer to the tail
node, to avoid rescanning the list.
> I've come up with the following. I know the pop-end implementation
> isn't the most efficient, but simple imp is important to me, too.
> BTW, is there any advantage to making these inline functions instead
> of macros? Wouldn't the two techniques pretty much accomplish the
> same in this case?
> Thanks
> -lv
>
> (defmacro push-end (list item)
> `(if (null ,list)
> (setf ,list (list ,item))
> (nconc ,list (list ,item))))
For inserting a single item, this is no better than NREVERSE, a
regular push, and another NREVERSE. Asymptotically speaking, that is.
It's O(N) in the length of the list.
For inserting M items, this is O(M * N).
Reversing the list of N items first, pushing M items, and reversing
again, is O(M + N).
O(M + N) is faster than O(M * N) for sufficiently large M and N.
Of course, this PUSH-END macro absolves you from having to maintain
any state whatsoever: no tail node, no reversed list, no code
restructuring. So it could be handy.
I'd fix the double evaluation of ,list though, ouch! Rather than
whipping out GENSYM-s, the thing to do is to simply eliminate the
superfluous IF:
(defmacro push-end (list item)
(setf ,list (nconc ,list (list ,item)))
Can you think of a way whereby PUSH-END and POP-END could secretly
maintain state to be faster?
An explicit way to do it would be to have an extra argument: the name
of a variable where state is maintained. Multiple calls to PUSH-END
and POP-END on the same list would be tied together by sharing the
same state variable.
(defmacro push-end (list-place &key cache-tail-in)
...)
If :CACHE-TAIL-IN X is supplied, X designates a location in which PUSH-
END can remember the tail node for future use. X must be NIL prior to
the first use, and must be cleared to NIL whenever you do something
that invalidates it.
Kaz Kylheku wrote:
> On Feb 27, 4:03 am, vanekl <·····@acd.net> wrote:
>> What is the recommended way to Push/Pop for the tail end of lists?
>
> In a loose order of preference:
>
> - Use LOOP with COLLECT if possible
If Loop would allow me to push/pop on either end of the collection
this would be ideal for my algorithm, but I don't think that
capability is there. My algorithm requires a deque.
> - REVERSE (or NREVERSE, if you can get away with it), then push and
> pop at the head of the list, then NREVERSE when finished.
I think my macros should be a little faster than this technique,
but I'll test this to make sure since now you got me wondering.
> - Some destructive hack in which you maintain a pointer to the tail
> node, to avoid rescanning the list.
This is what I'll probably end up doing if proto evolves into
prod code.
>> I've come up with the following. I know the pop-end implementation
>> isn't the most efficient, but simple imp is important to me, too.
>> BTW, is there any advantage to making these inline functions instead
>> of macros? Wouldn't the two techniques pretty much accomplish the
>> same in this case?
>> Thanks
>> -lv
>>
>> (defmacro push-end (list item)
>> `(if (null ,list)
>> (setf ,list (list ,item))
>> (nconc ,list (list ,item))))
>
> For inserting a single item, this is no better than NREVERSE, a
> regular push, and another NREVERSE. Asymptotically speaking, that is.
In theory, you are, of course, right.
Not so sure that's a better idea in practice than nconc, though,
assuming M == 1.
> It's O(N) in the length of the list.
>
> For inserting M items, this is O(M * N).
>
> Reversing the list of N items first, pushing M items, and reversing
> again, is O(M + N).
>
> O(M + N) is faster than O(M * N) for sufficiently large M and N.
Good point. I can get away w/o having any state variables as long
as I can simply delay the final reverse until after all the pushing
and popping is done. This fits into my algorithm well, since the
pushing and popping come in a lot of short bursts. Pascal even
wrote a macro that facilitates this. As long as I am careful
to use pascal's macro such that it doesn't interfere with the
pops and pushes to the front end, this should work.
> Of course, this PUSH-END macro absolves you from having to maintain
> any state whatsoever: no tail node, no reversed list, no code
> restructuring. So it could be handy.
>
> I'd fix the double evaluation of ,list though, ouch! Rather than
> whipping out GENSYM-s, the thing to do is to simply eliminate the
> superfluous IF:
>
> (defmacro push-end (list item)
> (setf ,list (nconc ,list (list ,item)))
Yep, this is better (but Pascal's macro is even better).
> Can you think of a way whereby PUSH-END and POP-END could secretly
> maintain state to be faster?
>
> An explicit way to do it would be to have an extra argument: the name
> of a variable where state is maintained. Multiple calls to PUSH-END
> and POP-END on the same list would be tied together by sharing the
> same state variable.
>
> (defmacro push-end (list-place &key cache-tail-in)
> ...)
>
> If :CACHE-TAIL-IN X is supplied, X designates a location in which PUSH-
> END can remember the tail node for future use. X must be NIL prior to
> the first use, and must be cleared to NIL whenever you do something
> that invalidates it.
My thinking on all this is that since I thought this type
of micro-pattern had to occur to other people long before it hit
me, there was probably a CL function/macro/idiom that already
solved it. Guess this isn't a common enough pattern to have
a macro for it. I'll just (carefully) apply Pascal's macro.
Thanks, sometimes I just need to talk it out.
On Feb 27, 1:04 pm, vanekl <·····@acd.net> wrote:
> Kaz Kylheku wrote:
> > On Feb 27, 4:03 am, vanekl <·····@acd.net> wrote:
> >> What is the recommended way to Push/Pop for the tail end of lists?
>
> > In a loose order of preference:
>
> > - Use LOOP with COLLECT if possible
>
> If Loop would allow me to push/pop on either end of the collection
> this would be ideal for my algorithm, but I don't think that
> capability is there. My algorithm requires a deque.
Here is an idea. Who says that a deque has to be represented by
exactly one list? What if a deque is represented by two lists? The
dequeue then presents the same interface on both ends: a chain of one-
way links emanating from the extreme nodes, into the middle of the
deque.
The final operation of obtaining the deque as one list requires that
the tail piece be nreversed, and nconced onto the end of the first
piece.
While you are working with the deque, you can push and pop either end
normally, except that in the case of underflow, you have to transfer
nodes from one the other piece, if there are any. And of course they
have to be reversed.
Is this worthwhile, or does the invention of something like this
indicate that maybe it's time to whip out the structs and make doubly-
linked list?
What's good about this hybrid approach? It could save time if the
input list that is to be treated as a deque is long, and can be
destructively manipulated. The tail piece is then just pushed.
It's better than maintaining a tail pointer on a singly-linked list,
because a tail pointer helps with pushes, not with pops. To do a pop,
you have to find parent.
The lack of abstraction and encapsulation of the hybrid approach is
seductive. You use the regular PUSH macros for pushing at either end.
For popping, you can use the same macro also for either end, you just
swap the lists! Reversibility: it's not just for jackets!
(defmacro pop-dequeue (facing-piece other-piece)
(let ((facing (gensym))
(other (gensym)))
`(let ((,facing ,facing-piece))
(if (null ,facing)
(let ((,other ,other-piece))
(if (null ,other-piece)
nil
(let ((other-rev (nreverse ,other-piece)))
(prog1 (car other-rev)
(setf ,other-piece nil)
(setf ,facing-piece (cdr other-rev))))))
(prog1 (car ,facing)
(setf ,facing-piece (cdr ,facing)))))))
Test session:
;; deque containing (1 2 3 4 5 6)
(defparameter *x* (list 1 2 3)) ;; front half
(defparameter *y* (list 6 5 4)) ;; rear half
(pop-deque *x* *y*) -> 1
(pop-deque *x* *y*) -> 2
(pop-deque *x* *y*) -> 3
*x* -> NIL ;; good!
*y* -> (4 5 6) ;; not touched yet!
(pop-deque *x* *y*) -> 4 ;; good!
*x* -> (5 6) ;; whole other piece
*y* -> NIL ;; good!
(pop-deque *x* *y*) -> 5
(pop-deque *x* *y*) -> 6
(list *x* *y*) -> (NIL NIL) ;; all clear
(pop-deque *x* *y*) -> NIL ;; final case, good
(list *x* *y*) -> (NIL NIL)
If you have some sane naming for the lists, then the code is readable:
(push item foo-front)
(push item foo-back)
(pop-deque foo-front foo-back) ;; front pop
(pop-deque foo-back foo-front) ;; back pop
(nconc foo-front (nreverse foo-back)) ;; convert to list
Hmm.
On Feb 27, 3:30 pm, Kaz Kylheku <········@gmail.com> wrote:
> (defmacro pop-dequeue (facing-piece other-piece)
Just auditing for macro hygiene bugs, before I let this recede into
the Usenet archives.
> (let ((facing (gensym))
> (other (gensym)))
> `(let ((,facing ,facing-piece))
> (if (null ,facing)
> (let ((,other ,other-piece))
> (if (null ,other-piece)
And there is one. This should be (null ,other), using the gensym.
> nil
> (let ((other-rev (nreverse ,other-piece)))
Another instance; should be: (nreverse ,other).
> (prog1 (car other-rev)
> (setf ,other-piece nil)
This is a problem, because OTHER-PIECE is a form that makes a lexical
reference in order to compute the place to be stored. So the temporary
OTHER-REV has to go into a proper package, or else be a gensym.
Damn, where is define-syntax when you need it? Help, Lexicons!
Kaz Kylheku wrote:
> On Feb 27, 1:04 pm, vanekl <·····@acd.net> wrote:
>> Kaz Kylheku wrote:
>>> On Feb 27, 4:03 am, vanekl <·····@acd.net> wrote:
>>>> What is the recommended way to Push/Pop for the tail end of lists?
>>> In a loose order of preference:
>>> - Use LOOP with COLLECT if possible
>> If Loop would allow me to push/pop on either end of the collection
>> this would be ideal for my algorithm, but I don't think that
>> capability is there. My algorithm requires a deque.
>
> Here is an idea. Who says that a deque has to be represented by
> exactly one list? What if a deque is represented by two lists? The
> dequeue then presents the same interface on both ends: a chain of one-
> way links emanating from the extreme nodes, into the middle of the
> deque.
>
> The final operation of obtaining the deque as one list requires that
> the tail piece be nreversed, and nconced onto the end of the first
> piece.
>
> While you are working with the deque, you can push and pop either end
> normally, except that in the case of underflow, you have to transfer
> nodes from one the other piece, if there are any. And of course they
> have to be reversed.
>
> Is this worthwhile, or does the invention of something like this
> indicate that maybe it's time to whip out the structs and make doubly-
> linked list?
>
> What's good about this hybrid approach? It could save time if the
> input list that is to be treated as a deque is long, and can be
> destructively manipulated. The tail piece is then just pushed.
>
> It's better than maintaining a tail pointer on a singly-linked list,
> because a tail pointer helps with pushes, not with pops. To do a pop,
> you have to find parent.
>
> The lack of abstraction and encapsulation of the hybrid approach is
> seductive. You use the regular PUSH macros for pushing at either end.
> For popping, you can use the same macro also for either end, you just
> swap the lists! Reversibility: it's not just for jackets!
>
> (defmacro pop-dequeue (facing-piece other-piece)
> (let ((facing (gensym))
> (other (gensym)))
> `(let ((,facing ,facing-piece))
> (if (null ,facing)
> (let ((,other ,other-piece))
> (if (null ,other-piece)
> nil
> (let ((other-rev (nreverse ,other-piece)))
> (prog1 (car other-rev)
> (setf ,other-piece nil)
> (setf ,facing-piece (cdr other-rev))))))
> (prog1 (car ,facing)
> (setf ,facing-piece (cdr ,facing)))))))
>
>
> Test session:
>
> ;; deque containing (1 2 3 4 5 6)
> (defparameter *x* (list 1 2 3)) ;; front half
> (defparameter *y* (list 6 5 4)) ;; rear half
>
> (pop-deque *x* *y*) -> 1
> (pop-deque *x* *y*) -> 2
> (pop-deque *x* *y*) -> 3
>
> *x* -> NIL ;; good!
> *y* -> (4 5 6) ;; not touched yet!
>
> (pop-deque *x* *y*) -> 4 ;; good!
>
> *x* -> (5 6) ;; whole other piece
> *y* -> NIL ;; good!
>
> (pop-deque *x* *y*) -> 5
> (pop-deque *x* *y*) -> 6
>
> (list *x* *y*) -> (NIL NIL) ;; all clear
>
> (pop-deque *x* *y*) -> NIL ;; final case, good
>
> (list *x* *y*) -> (NIL NIL)
>
>
> If you have some sane naming for the lists, then the code is readable:
>
> (push item foo-front)
> (push item foo-back)
> (pop-deque foo-front foo-back) ;; front pop
> (pop-deque foo-back foo-front) ;; back pop
>
> (nconc foo-front (nreverse foo-back)) ;; convert to list
>
> Hmm.
Hah!
Necessity and constraints truly are the mothers and fathers
of invention.
In order to keep this demented deque abstraction from leaking
like a hemorrhaging aorta gushing all over my algorithm, I
changed 'nconc' to 'append' and 'nreverse' to 'reverse'
when stitching the two lists back together.
This moves the time wastage manipulating items at the end
of the deque into the GC (due to more consing), but it may be
a worthwhile trade off. I don't care--this is too much fun
to stop playing with.
i love new toys that make you think different (sic).
-lv
On Feb 27, 7:31 pm, vanekl <·····@acd.net> wrote:
> Kaz Kylheku wrote:
> > On Feb 27, 1:04 pm, vanekl <·····@acd.net> wrote:
> >> Kaz Kylheku wrote:
> >>> On Feb 27, 4:03 am, vanekl <·····@acd.net> wrote:
> >>>> What is the recommended way to Push/Pop for the tail end of lists?
> >>> In a loose order of preference:
> >>> - Use LOOP with COLLECT if possible
> >> If Loop would allow me to push/pop on either end of the collection
> >> this would be ideal for my algorithm, but I don't think that
> >> capability is there. My algorithm requires a deque.
>
> > Here is an idea. Who says that a deque has to be represented by
> > exactly one list? What if a deque is represented by two lists? The
> > dequeue then presents the same interface on both ends: a chain of one-
> > way links emanating from the extreme nodes, into the middle of the
> > deque.
>
> > The final operation of obtaining the deque as one list requires that
> > the tail piece be nreversed, and nconced onto the end of the first
> > piece.
>
> > While you are working with the deque, you can push and pop either end
> > normally, except that in the case of underflow, you have to transfer
> > nodes from one the other piece, if there are any. And of course they
> > have to be reversed.
>
> > Is this worthwhile, or does the invention of something like this
> > indicate that maybe it's time to whip out the structs and make doubly-
> > linked list?
>
> > What's good about this hybrid approach? It could save time if the
> > input list that is to be treated as a deque is long, and can be
> > destructively manipulated. The tail piece is then just pushed.
>
> > It's better than maintaining a tail pointer on a singly-linked list,
> > because a tail pointer helps with pushes, not with pops. To do a pop,
> > you have to find parent.
>
> > The lack of abstraction and encapsulation of the hybrid approach is
> > seductive. You use the regular PUSH macros for pushing at either end.
> > For popping, you can use the same macro also for either end, you just
> > swap the lists! Reversibility: it's not just for jackets!
>
> > (defmacro pop-dequeue (facing-piece other-piece)
> > (let ((facing (gensym))
> > (other (gensym)))
> > `(let ((,facing ,facing-piece))
> > (if (null ,facing)
> > (let ((,other ,other-piece))
> > (if (null ,other-piece)
> > nil
> > (let ((other-rev (nreverse ,other-piece)))
> > (prog1 (car other-rev)
> > (setf ,other-piece nil)
> > (setf ,facing-piece (cdr other-rev))))))
> > (prog1 (car ,facing)
> > (setf ,facing-piece (cdr ,facing)))))))
>
> > Test session:
>
> > ;; deque containing (1 2 3 4 5 6)
> > (defparameter *x* (list 1 2 3)) ;; front half
> > (defparameter *y* (list 6 5 4)) ;; rear half
>
> > (pop-deque *x* *y*) -> 1
> > (pop-deque *x* *y*) -> 2
> > (pop-deque *x* *y*) -> 3
>
> > *x* -> NIL ;; good!
> > *y* -> (4 5 6) ;; not touched yet!
>
> > (pop-deque *x* *y*) -> 4 ;; good!
>
> > *x* -> (5 6) ;; whole other piece
> > *y* -> NIL ;; good!
>
> > (pop-deque *x* *y*) -> 5
> > (pop-deque *x* *y*) -> 6
>
> > (list *x* *y*) -> (NIL NIL) ;; all clear
>
> > (pop-deque *x* *y*) -> NIL ;; final case, good
>
> > (list *x* *y*) -> (NIL NIL)
>
> > If you have some sane naming for the lists, then the code is readable:
>
> > (push item foo-front)
> > (push item foo-back)
> > (pop-deque foo-front foo-back) ;; front pop
> > (pop-deque foo-back foo-front) ;; back pop
>
> > (nconc foo-front (nreverse foo-back)) ;; convert to list
>
> > Hmm.
>
> Hah!
> Necessity and constraints truly are the mothers and fathers
> of invention.
>
> In order to keep this demented deque abstraction from leaking
> like a hemorrhaging aorta gushing all over my algorithm, I
> changed 'nconc' to 'append' and 'nreverse' to 'reverse'
> when stitching the two lists back together.
>
> This moves the time wastage manipulating items at the end
> of the deque into the GC (due to more consing), but it may be
> a worthwhile trade off. I don't care--this is too much fun
> to stop playing with.
>
> i love new toys that make you think different (sic).
> -lv- Hide quoted text -
>
> - Show quoted text -
Demented? We're just getting started! ;-)
Try a completely symmetric "ladder" of 4-element cons rings ... O(1)
for all operations.
(defmacro deque-push (item fore back)
`(let ((ring (list ,fore ,item nil nil)))
(setf (cddddr ring) ring)
(setf (fourth ring) (second ring))
(if ,fore
(setf (caddr ,fore) (cddr ring))
(setf ,back (cddr ring)))
(setf ,fore ring)))
(defmacro deque-pop (fore back)
`(let ((item (cadr ,fore)))
(setf ,fore (car ,fore))
(if ,fore
(setf (caddr ,fore) nil)
(setf ,back nil))
item))
(defmacro deque-first (fore-or-back)
`(cadr ,fore-or-back))
(setq x nil y nil)
(deque-push 'a x y)
(deque-push 'b x y)
(deque-push 'c x y)
CL-USER> x
#1=(#2=(#3=(NIL A #4=(#5=(NIL C . #1#) B . #2#) A . #3#) B . #4#) C .
#5#)
CL-USER> y
#1=(#2=(#3=(NIL C #4=(#5=(NIL A . #1#) B . #2#) C . #3#) B . #4#) A .
#5#)
CL-USER> (deque-pop x y)
C
CL-USER> x
#1=(#2=(NIL A #3=(NIL B . #1#) A . #2#) B . #3#)
CL-USER> y
#1=(#2=(NIL B #3=(NIL A . #1#) B . #2#) A . #3#)
CL-USER> (deque-pop y x)
A
CL-USER> x
#1=(NIL B NIL B . #1#)
CL-USER> y
#1=(NIL B NIL B . #1#)
CL-USER>
Gene wrote:
> On Feb 27, 7:31 pm, vanekl <·····@acd.net> wrote:
>> Kaz Kylheku wrote:
>>> On Feb 27, 1:04 pm, vanekl <·····@acd.net> wrote:
>>>> Kaz Kylheku wrote:
>>>>> On Feb 27, 4:03 am, vanekl <·····@acd.net> wrote:
>>>>>> What is the recommended way to Push/Pop for the tail end of lists?
>>>>> In a loose order of preference:
>>>>> - Use LOOP with COLLECT if possible
>>>> If Loop would allow me to push/pop on either end of the collection
>>>> this would be ideal for my algorithm, but I don't think that
>>>> capability is there. My algorithm requires a deque.
>>> Here is an idea. Who says that a deque has to be represented by
>>> exactly one list? What if a deque is represented by two lists? The
>>> dequeue then presents the same interface on both ends: a chain of one-
>>> way links emanating from the extreme nodes, into the middle of the
>>> deque.
>>> The final operation of obtaining the deque as one list requires that
>>> the tail piece be nreversed, and nconced onto the end of the first
>>> piece.
>>> While you are working with the deque, you can push and pop either end
>>> normally, except that in the case of underflow, you have to transfer
>>> nodes from one the other piece, if there are any. And of course they
>>> have to be reversed.
>>> Is this worthwhile, or does the invention of something like this
>>> indicate that maybe it's time to whip out the structs and make doubly-
>>> linked list?
>>> What's good about this hybrid approach? It could save time if the
>>> input list that is to be treated as a deque is long, and can be
>>> destructively manipulated. The tail piece is then just pushed.
>>> It's better than maintaining a tail pointer on a singly-linked list,
>>> because a tail pointer helps with pushes, not with pops. To do a pop,
>>> you have to find parent.
>>> The lack of abstraction and encapsulation of the hybrid approach is
>>> seductive. You use the regular PUSH macros for pushing at either end.
>>> For popping, you can use the same macro also for either end, you just
>>> swap the lists! Reversibility: it's not just for jackets!
>>> (defmacro pop-dequeue (facing-piece other-piece)
>>> (let ((facing (gensym))
>>> (other (gensym)))
>>> `(let ((,facing ,facing-piece))
>>> (if (null ,facing)
>>> (let ((,other ,other-piece))
>>> (if (null ,other-piece)
>>> nil
>>> (let ((other-rev (nreverse ,other-piece)))
>>> (prog1 (car other-rev)
>>> (setf ,other-piece nil)
>>> (setf ,facing-piece (cdr other-rev))))))
>>> (prog1 (car ,facing)
>>> (setf ,facing-piece (cdr ,facing)))))))
>>> Test session:
>>> ;; deque containing (1 2 3 4 5 6)
>>> (defparameter *x* (list 1 2 3)) ;; front half
>>> (defparameter *y* (list 6 5 4)) ;; rear half
>>> (pop-deque *x* *y*) -> 1
>>> (pop-deque *x* *y*) -> 2
>>> (pop-deque *x* *y*) -> 3
>>> *x* -> NIL ;; good!
>>> *y* -> (4 5 6) ;; not touched yet!
>>> (pop-deque *x* *y*) -> 4 ;; good!
>>> *x* -> (5 6) ;; whole other piece
>>> *y* -> NIL ;; good!
>>> (pop-deque *x* *y*) -> 5
>>> (pop-deque *x* *y*) -> 6
>>> (list *x* *y*) -> (NIL NIL) ;; all clear
>>> (pop-deque *x* *y*) -> NIL ;; final case, good
>>> (list *x* *y*) -> (NIL NIL)
>>> If you have some sane naming for the lists, then the code is readable:
>>> (push item foo-front)
>>> (push item foo-back)
>>> (pop-deque foo-front foo-back) ;; front pop
>>> (pop-deque foo-back foo-front) ;; back pop
>>> (nconc foo-front (nreverse foo-back)) ;; convert to list
>>> Hmm.
>> Hah!
>> Necessity and constraints truly are the mothers and fathers
>> of invention.
>>
>> In order to keep this demented deque abstraction from leaking
>> like a hemorrhaging aorta gushing all over my algorithm, I
>> changed 'nconc' to 'append' and 'nreverse' to 'reverse'
>> when stitching the two lists back together.
>>
>> This moves the time wastage manipulating items at the end
>> of the deque into the GC (due to more consing), but it may be
>> a worthwhile trade off. I don't care--this is too much fun
>> to stop playing with.
>>
>> i love new toys that make you think different (sic).
>> -lv- Hide quoted text -
>>
>> - Show quoted text -
>
> Demented? We're just getting started! ;-)
>
> Try a completely symmetric "ladder" of 4-element cons rings ... O(1)
> for all operations.
>
> (defmacro deque-push (item fore back)
> `(let ((ring (list ,fore ,item nil nil)))
> (setf (cddddr ring) ring)
> (setf (fourth ring) (second ring))
> (if ,fore
> (setf (caddr ,fore) (cddr ring))
> (setf ,back (cddr ring)))
> (setf ,fore ring)))
>
> (defmacro deque-pop (fore back)
> `(let ((item (cadr ,fore)))
> (setf ,fore (car ,fore))
> (if ,fore
> (setf (caddr ,fore) nil)
> (setf ,back nil))
> item))
>
> (defmacro deque-first (fore-or-back)
> `(cadr ,fore-or-back))
>
> (setq x nil y nil)
> (deque-push 'a x y)
> (deque-push 'b x y)
> (deque-push 'c x y)
>
> CL-USER> x
> #1=(#2=(#3=(NIL A #4=(#5=(NIL C . #1#) B . #2#) A . #3#) B . #4#) C .
> #5#)
> CL-USER> y
> #1=(#2=(#3=(NIL C #4=(#5=(NIL A . #1#) B . #2#) C . #3#) B . #4#) A .
> #5#)
> CL-USER> (deque-pop x y)
> C
> CL-USER> x
> #1=(#2=(NIL A #3=(NIL B . #1#) A . #2#) B . #3#)
> CL-USER> y
> #1=(#2=(NIL B #3=(NIL A . #1#) B . #2#) A . #3#)
> CL-USER> (deque-pop y x)
> A
> CL-USER> x
> #1=(NIL B NIL B . #1#)
> CL-USER> y
> #1=(NIL B NIL B . #1#)
> CL-USER>
Ladder? More like whirlpool. I went into three infinite loops while
playing with it.
The data structure I'm looking
for also has to periodically resemble a list in that it can
be traversed (in order) easily. I'll probably come back to this
and pick it apart later because I've never worked with anything
like it, but this is a Dangerous Deque.
-lv
On Feb 28, 8:37 am, vanekl <·····@acd.net> wrote:
> Gene wrote:
> > On Feb 27, 7:31 pm, vanekl <·····@acd.net> wrote:
> >> Kaz Kylheku wrote:
> >>> On Feb 27, 1:04 pm, vanekl <·····@acd.net> wrote:
> >>>> Kaz Kylheku wrote:
> >>>>> On Feb 27, 4:03 am, vanekl <·····@acd.net> wrote:
> >>>>>> What is the recommended way to Push/Pop for the tail end of lists?
> >>>>> In a loose order of preference:
> >>>>> - Use LOOP with COLLECT if possible
> >>>> If Loop would allow me to push/pop on either end of the collection
> >>>> this would be ideal for my algorithm, but I don't think that
> >>>> capability is there. My algorithm requires a deque.
> >>> Here is an idea. Who says that a deque has to be represented by
> >>> exactly one list? What if a deque is represented by two lists? The
> >>> dequeue then presents the same interface on both ends: a chain of one-
> >>> way links emanating from the extreme nodes, into the middle of the
> >>> deque.
> >>> The final operation of obtaining the deque as one list requires that
> >>> the tail piece be nreversed, and nconced onto the end of the first
> >>> piece.
> >>> While you are working with the deque, you can push and pop either end
> >>> normally, except that in the case of underflow, you have to transfer
> >>> nodes from one the other piece, if there are any. And of course they
> >>> have to be reversed.
> >>> Is this worthwhile, or does the invention of something like this
> >>> indicate that maybe it's time to whip out the structs and make doubly-
> >>> linked list?
> >>> What's good about this hybrid approach? It could save time if the
> >>> input list that is to be treated as a deque is long, and can be
> >>> destructively manipulated. The tail piece is then just pushed.
> >>> It's better than maintaining a tail pointer on a singly-linked list,
> >>> because a tail pointer helps with pushes, not with pops. To do a pop,
> >>> you have to find parent.
> >>> The lack of abstraction and encapsulation of the hybrid approach is
> >>> seductive. You use the regular PUSH macros for pushing at either end.
> >>> For popping, you can use the same macro also for either end, you just
> >>> swap the lists! Reversibility: it's not just for jackets!
> >>> (defmacro pop-dequeue (facing-piece other-piece)
> >>> (let ((facing (gensym))
> >>> (other (gensym)))
> >>> `(let ((,facing ,facing-piece))
> >>> (if (null ,facing)
> >>> (let ((,other ,other-piece))
> >>> (if (null ,other-piece)
> >>> nil
> >>> (let ((other-rev (nreverse ,other-piece)))
> >>> (prog1 (car other-rev)
> >>> (setf ,other-piece nil)
> >>> (setf ,facing-piece (cdr other-rev))))))
> >>> (prog1 (car ,facing)
> >>> (setf ,facing-piece (cdr ,facing)))))))
> >>> Test session:
> >>> ;; deque containing (1 2 3 4 5 6)
> >>> (defparameter *x* (list 1 2 3)) ;; front half
> >>> (defparameter *y* (list 6 5 4)) ;; rear half
> >>> (pop-deque *x* *y*) -> 1
> >>> (pop-deque *x* *y*) -> 2
> >>> (pop-deque *x* *y*) -> 3
> >>> *x* -> NIL ;; good!
> >>> *y* -> (4 5 6) ;; not touched yet!
> >>> (pop-deque *x* *y*) -> 4 ;; good!
> >>> *x* -> (5 6) ;; whole other piece
> >>> *y* -> NIL ;; good!
> >>> (pop-deque *x* *y*) -> 5
> >>> (pop-deque *x* *y*) -> 6
> >>> (list *x* *y*) -> (NIL NIL) ;; all clear
> >>> (pop-deque *x* *y*) -> NIL ;; final case, good
> >>> (list *x* *y*) -> (NIL NIL)
> >>> If you have some sane naming for the lists, then the code is readable:
> >>> (push item foo-front)
> >>> (push item foo-back)
> >>> (pop-deque foo-front foo-back) ;; front pop
> >>> (pop-deque foo-back foo-front) ;; back pop
> >>> (nconc foo-front (nreverse foo-back)) ;; convert to list
> >>> Hmm.
> >> Hah!
> >> Necessity and constraints truly are the mothers and fathers
> >> of invention.
>
> >> In order to keep this demented deque abstraction from leaking
> >> like a hemorrhaging aorta gushing all over my algorithm, I
> >> changed 'nconc' to 'append' and 'nreverse' to 'reverse'
> >> when stitching the two lists back together.
>
> >> This moves the time wastage manipulating items at the end
> >> of the deque into the GC (due to more consing), but it may be
> >> a worthwhile trade off. I don't care--this is too much fun
> >> to stop playing with.
>
> >> i love new toys that make you think different (sic).
> >> -lv- Hide quoted text -
>
> >> - Show quoted text -
>
> > Demented? We're just getting started! ;-)
>
> > Try a completely symmetric "ladder" of 4-element cons rings ... O(1)
> > for all operations.
>
> > (defmacro deque-push (item fore back)
> > `(let ((ring (list ,fore ,item nil nil)))
> > (setf (cddddr ring) ring)
> > (setf (fourth ring) (second ring))
> > (if ,fore
> > (setf (caddr ,fore) (cddr ring))
> > (setf ,back (cddr ring)))
> > (setf ,fore ring)))
>
> > (defmacro deque-pop (fore back)
> > `(let ((item (cadr ,fore)))
> > (setf ,fore (car ,fore))
> > (if ,fore
> > (setf (caddr ,fore) nil)
> > (setf ,back nil))
> > item))
>
> > (defmacro deque-first (fore-or-back)
> > `(cadr ,fore-or-back))
>
> > (setq x nil y nil)
> > (deque-push 'a x y)
> > (deque-push 'b x y)
> > (deque-push 'c x y)
>
> > CL-USER> x
> > #1=(#2=(#3=(NIL A #4=(#5=(NIL C . #1#) B . #2#) A . #3#) B . #4#) C .
> > #5#)
> > CL-USER> y
> > #1=(#2=(#3=(NIL C #4=(#5=(NIL A . #1#) B . #2#) C . #3#) B . #4#) A .
> > #5#)
> > CL-USER> (deque-pop x y)
> > C
> > CL-USER> x
> > #1=(#2=(NIL A #3=(NIL B . #1#) A . #2#) B . #3#)
> > CL-USER> y
> > #1=(#2=(NIL B #3=(NIL A . #1#) B . #2#) A . #3#)
> > CL-USER> (deque-pop y x)
> > A
> > CL-USER> x
> > #1=(NIL B NIL B . #1#)
> > CL-USER> y
> > #1=(NIL B NIL B . #1#)
> > CL-USER>
>
> Ladder? More like whirlpool. I went into three infinite loops while
> playing with it.
>
> The data structure I'm looking
> for also has to periodically resemble a list in that it can
> be traversed (in order) easily. I'll probably come back to this
> and pick it apart later because I've never worked with anything
> like it, but this is a Dangerous Deque.
>
> -lv- Hide quoted text -
>
> - Show quoted text -
Well, yes, one side the ladder goes up and the other down! You need
to set *print-circle* true and be a careful out there... That's what
makes it demented.
This version is coded so that car pointers make forward and backward
lists of rungs. The rungs are rings connected by cdrs.
Therefore you can easily traverse either the forward or the backward
"list" by following cars to get to the right rung of the ladder. Then
cadr always gets you to the element. So to print forward,
(do ((ring fore (car ring))) ; haven't coded a (do ) for ages,
((null ring)) ; but think this is right
(print (cadr ring)))
To print backward just substitute the other "list" for fore.
You could easily recode the macros, swapping the roles of cars and
cdrs. Then the lists would be more conventional, while the accessor
would become cdar . For example, you'd print forward with
(dolist (ring fore) (print (cdar ring)))
Gene wrote:
[big snip]
>
> Well, yes, one side the ladder goes up and the other down! You need
> to set *print-circle* true and be a careful out there... That's what
> makes it demented.
>
> This version is coded so that car pointers make forward and backward
> lists of rungs. The rungs are rings connected by cdrs.
>
> Therefore you can easily traverse either the forward or the backward
> "list" by following cars to get to the right rung of the ladder. Then
> cadr always gets you to the element. So to print forward,
>
> (do ((ring fore (car ring))) ; haven't coded a (do ) for ages,
> ((null ring)) ; but think this is right
> (print (cadr ring)))
>
> To print backward just substitute the other "list" for fore.
>
> You could easily recode the macros, swapping the roles of cars and
> cdrs. Then the lists would be more conventional, while the accessor
> would become cdar . For example, you'd print forward with
>
> (dolist (ring fore) (print (cdar ring)))
I appreciate the explanation.
This deserves further attention,
but it will have to wait.
lv
--
W.F.B. :: R.I.P.
On Feb 28, 7:09 pm, vanekl <·····@acd.net> wrote:
> Gene wrote:
>
>
> I appreciate the explanation.
> This deserves further attention,
> but it will have to wait.
>
> lv
> --
> W.F.B. :: R.I.P.- Hide quoted text -
>
I understand, but can't stop. Here is the revision, with some
attention to macro hygiene, also. I was off by one pointer in
previous post. Accessor is just (cdr ), not (cdar ). Here we go...
(defmacro deque-push (item fore back)
(let ((x (gensym "x"))
(ring (gensym "ring")))
`(let* ((,x ,item)
(,ring (cons (cons (cons (cons t ,x) nil) ,x) ,fore)))
(setf (caaaar ,ring) ,ring)
(if ,fore
(setf (cdaar ,fore) (caar ,ring))
(setf ,back (caar ,ring)))
(setf ,fore ,ring))))
(defmacro deque-pop (fore back)
`(prog1 (cdar ,fore)
(pop ,fore)
(if ,fore
(setf (cdaar ,fore) nil)
(setf ,back nil))))
CL-USER> (setq x nil y nil)
(deque-push 'b x y)
(deque-push 'a y x)
(deque-push 'c x y)
(deque-push 'd x y)
#1=((#2=((#1# . D)) . D) .
#3=((#4=((#3# . C) . #2#) . C) . #5=((#6=(# . #4#) . B) . #7=((# .
A)))))
CL-USER> (dolist (p x) (print (cdr p)))
D
C
B
A
NIL
CL-USER> (dolist (p y) (print (cdr p)))
A
B
C
D
NIL
CL-USER> (deque-pop x y)
D
CL-USER> (deque-pop y x)
A
CL-USER>
Gene wrote:
snip
>
> I understand, but can't stop. Here is the revision, with some
> attention to macro hygiene, also. I was off by one pointer in
> previous post. Accessor is just (cdr ), not (cdar ). Here we go...
>
> (defmacro deque-push (item fore back)
> (let ((x (gensym "x"))
> (ring (gensym "ring")))
> `(let* ((,x ,item)
> (,ring (cons (cons (cons (cons t ,x) nil) ,x) ,fore)))
> (setf (caaaar ,ring) ,ring)
> (if ,fore
> (setf (cdaar ,fore) (caar ,ring))
> (setf ,back (caar ,ring)))
> (setf ,fore ,ring))))
>
> (defmacro deque-pop (fore back)
> `(prog1 (cdar ,fore)
> (pop ,fore)
> (if ,fore
> (setf (cdaar ,fore) nil)
> (setf ,back nil))))
>
> CL-USER> (setq x nil y nil)
> (deque-push 'b x y)
> (deque-push 'a y x)
> (deque-push 'c x y)
> (deque-push 'd x y)
>
> #1=((#2=((#1# . D)) . D) .
> #3=((#4=((#3# . C) . #2#) . C) . #5=((#6=(# . #4#) . B) . #7=((# .
> A)))))
> CL-USER> (dolist (p x) (print (cdr p)))
>
> D
> C
> B
> A
> NIL
> CL-USER> (dolist (p y) (print (cdr p)))
>
> A
> B
> C
> D
> NIL
> CL-USER> (deque-pop x y)
> D
> CL-USER> (deque-pop y x)
> A
> CL-USER>
works like a charm, and i managed not to do anything too
stupid this time and fall into an endless loop. thanks.
i learn more new things w/ cl than w/ any other language
--
I call on all members of all races,
To weep for loss and gain of graces
On Feb 28, 8:42 pm, vanekl <·····@acd.net> wrote:
> Gene wrote:
>
> snip
>
>
>
> > I understand, but can't stop. Here is the revision, with some
> > attention to macro hygiene, also. I was off by one pointer in
> > previous post. Accessor is just (cdr ), not (cdar ). Here we go...
>
> > (defmacro deque-push (item fore back)
> > (let ((x (gensym "x"))
> > (ring (gensym "ring")))
> > `(let* ((,x ,item)
> > (,ring (cons (cons (cons (cons t ,x) nil) ,x) ,fore)))
> > (setf (caaaar ,ring) ,ring)
What kind of a debased language has an abomination like
"caaaar"? Let's make it even more powerful and add
"caaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaar"!
> > (if ,fore
> > (setf (cdaar ,fore) (caar ,ring))
> > (setf ,back (caar ,ring)))
> > (setf ,fore ,ring))))
>
> > (defmacro deque-pop (fore back)
> > `(prog1 (cdar ,fore)
> > (pop ,fore)
> > (if ,fore
> > (setf (cdaar ,fore) nil)
> > (setf ,back nil))))
>
> > CL-USER> (setq x nil y nil)
> > (deque-push 'b x y)
> > (deque-push 'a y x)
> > (deque-push 'c x y)
> > (deque-push 'd x y)
>
> > #1=((#2=((#1# . D)) . D) .
> > #3=((#4=((#3# . C) . #2#) . C) . #5=((#6=(# . #4#) . B) . #7=((# .
> > A)))))
> > CL-USER> (dolist (p x) (print (cdr p)))
>
> > D
> > C
> > B
> > A
> > NIL
> > CL-USER> (dolist (p y) (print (cdr p)))
>
> > A
> > B
> > C
> > D
> > NIL
> > CL-USER> (deque-pop x y)
> > D
> > CL-USER> (deque-pop y x)
> > A
> > CL-USER>
>
> works like a charm, and i managed not to do anything too
> stupid this time and fall into an endless loop. thanks.
> i learn more new things w/ cl than w/ any other language
but i cant think so clearly like i used 2
To attain knowledge, add things every day.
To attain wisdom, remove things every day.
--- Lao-tse
All this for push and pop? It's no wonder that Paul Graham
said that COMMON-LISP sucks.
Programmers are always surrounded by complexity; we cannot avoid
it.... If our basic tool, the language in which we design and
code our programs, is also complicated, the language itself
becomes part of the problem rather than part of its solution.
--- C. A. R. Hoare (1980 Turing Award Lecture)
NewLisp:
; inserting in front
(set 'pList '(b c)) $B"*(B (b c)
(push 'a pList) $B"*(B a
pList $B"*(B (a b c)
; insert at index
(push "hello" pList 2) $B"*(B "hello"
pList $B"*(B (a b "hello" c)
; optimized appending at the end
(push 'z pList -1) $B"*(B z
pList $B"*(B (a b "hello" c z)
(set 'pList '((f g) a b c "hello" d e 10))
(pop pList) $B"*(B (f g)
(pop pList) $B"*(B a
plist $B"*(B (b c "hello" d e 10)
(pop pList 3) $B"*(B d
(pop pList 100) $B"*(B 10
pList $B"*(B (b c "hello" e)
(pop pList -1) $B"*(B e
pList $B"*(B (b c "hello")
(pop pList -2) $B"*(B c
pList $B"*(B (b "hello")
On 2008-02-29 00:54:19 -0500, William James <·········@yahoo.com> said:
> NewLisp:
>
> ; inserting in front
> (set 'pList '(b c)) → (b c)
> (push 'a pList) → a
> pList → (a b c)
Is NewLisp still dynamically scoped?
Does it have bignums yet? [1]
Can more than one variable point to the same datum yet?
Can it do shared structure yet?
Or circular lists?
It's easy to be "simple" when you don't care about being correct.
[1] yes, there's a binding for gmp, but there's no automatic detection
of integer overflow that triggers the use of gmp, and all args to the
gmp functions must be strings, not integers.
On Feb 29, 7:34 am, Raffael Cavallaro <················@pas-d'espam-
s'il-vous-plait-mac.com> wrote:
> On 2008-02-29 00:54:19 -0500, William James <·········@yahoo.com> said:
>
> > NewLisp:
>
> > ; inserting in front
> > (set 'pList '(b c)) $B"*(B (b c)
> > (push 'a pList) $B"*(B a
> > pList $B"*(B (a b c)
>
> Is NewLisp still dynamically scoped?
Don't feed the trolls. W. J. is a waste of oxygen.
William James <·········@yahoo.com> writes:
> [...]
> NewLisp:
>
> ; inserting in front
> (set 'pList '(b c)) → (b c)
> (push 'a pList) → a
> pList → (a b c)
>
> ; insert at index
> (push "hello" pList 2) → "hello"
> pList → (a b "hello" c)
>
> ; optimized appending at the end
> (push 'z pList -1) → z
> pList → (a b "hello" c z)
How is it optimized?
(time (push 'z (make-list 1) -1))
(time (push 'z (make-list 1000) -1))
(time (push 'z (make-list 1000000) -1))
?
--
__Pascal Bourguignon__
On Feb 27, 4:31 pm, vanekl <·····@acd.net> wrote:
> Hah!
> Necessity and constraints truly are the mothers and fathers
> of invention.
Here is improved code, by the way. Shorter, with clearer logic and
hygiene issues addressed.
(defmacro pop-dequeue (facing-piece other-piece)
(let ((facing (gensym "FACING"))
(other-rev (gensym "OTHER-REV")))
`(let ((,facing ,facing-piece))
(if (null ,facing)
(let ((,other-rev (nreverse ,other-piece)))
(prog1
(first ,other-rev)
(setf ,other-piece nil)
(setf ,facing-piece (rest ,other-rev))))
(prog1
(first ,facing)
(setf ,facing-piece (rest ,facing)))))))
How do you reason about this? This is one of those algorithms that has
simple, O(1) operations which sometimes turn into O(N). You need
tricks like amortized analysis. But that can't be done for arbitrary
use patterns. You make assumptions like this: suppose the queue is N
items long, and you keep repeating the pair of operations: add to
front, remove from back. Each time you do this N times, the items flip
from one list to the other. So the operations are mostly O(1) except
that with a frequency of 1/N they are O(N). That amortizes down to
O(1). Thus doing M such operations is O(M), independently of any
choice of N. Asymptotically, when operating as a queue, this deque is
as efficient as a circular buffer or doubly-linked list.
But there is a degenerate case. Start with a dequeue of N items where
the front list is empty and the back has all N. Then pop an item from
the front. The deque flips, O(N). Now push the item back on the same
side. Then, pop one from the back. The deque flips again: O(N). Push
the item back on the same side where it came from. Repeat. So now you
can make an sequence of M elementary operations which costs O(M * N).
Here is an idea for defending against this attack: suppose that
instead of simply flipping the list from one side to the other, we
chop it exactly in half, and move half the nodes. That costs O(N),
like the full flip, but it ensures that O(N) pop operations must now
be done from either side before another flip takes place. It makes
sense: since the ``enemy'' can symmetrically attack your deque from
either side, your must defend each side equally. No algorithm which
unevenly distributes the nodes between the two sides can guard better
than this against an arbitrary chosen sequence of operations.
We know from a link-list-based merge sort algorithm that partitioning
a linked list into two halves is easy. You have two iterators: one
which moves by two nodes on each iteration (cddr), and one which moves
by a single node (cdrr). When the double stepper reaches the end of
the list, the single stepper is in the middle.
If half the nodes are always moved, that doesn't change the amortized
analysis for the circular queue operation. It just means that a full
scan takes place twice as often. It's still O(1), but slower by a
constant factor.
How about popping all the nodes from a dequeue containing N, where
they all start out in the back list? This is similar to hash table
doubling on insertion or halving on deletion, and the reasoning is
similar. The cost of a pop amortizes to O(1).
On Feb 28, 12:19 am, Kaz Kylheku <········@gmail.com> wrote:
> On Feb 27, 4:31 pm, vanekl <·····@acd.net> wrote:
>
> > Hah!
> > Necessity and constraints truly are the mothers and fathers
> > of invention.
>
> Here is improved code, by the way. Shorter, with clearer logic and
> hygiene issues addressed.
>
> (defmacro pop-dequeue (facing-piece other-piece)
> (let ((facing (gensym "FACING"))
> (other-rev (gensym "OTHER-REV")))
> `(let ((,facing ,facing-piece))
> (if (null ,facing)
> (let ((,other-rev (nreverse ,other-piece)))
> (prog1
> (first ,other-rev)
> (setf ,other-piece nil)
> (setf ,facing-piece (rest ,other-rev))))
> (prog1
> (first ,facing)
> (setf ,facing-piece (rest ,facing)))))))
Here is a version with a smaller macro-expansion footprint:
(eval-when (:compile-toplevel :load-toplevel :execute)
(defun pop-dequeue-helper (facing-piece other-piece)
(if (null facing-piece)
(let ((other-rev (nreverse other-piece)))
(values (first other-rev) (rest other-rev) nil))
(values (first facing-piece) (rest facing-piece) other-piece))))
(defmacro pop-dequeue (facing-piece other-piece)
(let ((result (gensym))
(new-facing (gensym))
(new-other (gensym)))
`(multiple-value-bind (,result ,new-facing ,new-other)
(pop-dequeue-helper ,facing-piece ,other-
piece)
(psetf ,facing-piece ,new-facing
,other-piece ,new-other)
,result)))
The work is done with a helper function now with an interface that
allows you to replace it with that bisective strategy for moving nodes
from one list to the other without recompiling the macro expansions.
Kaz Kylheku wrote:
> On Feb 28, 12:19 am, Kaz Kylheku <········@gmail.com> wrote:
>> On Feb 27, 4:31 pm, vanekl <·····@acd.net> wrote:
>>
>>> Hah!
>>> Necessity and constraints truly are the mothers and fathers
>>> of invention.
>> Here is improved code, by the way. Shorter, with clearer logic and
>> hygiene issues addressed.
>>
>> (defmacro pop-dequeue (facing-piece other-piece)
>> (let ((facing (gensym "FACING"))
>> (other-rev (gensym "OTHER-REV")))
>> `(let ((,facing ,facing-piece))
>> (if (null ,facing)
>> (let ((,other-rev (nreverse ,other-piece)))
>> (prog1
>> (first ,other-rev)
>> (setf ,other-piece nil)
>> (setf ,facing-piece (rest ,other-rev))))
>> (prog1
>> (first ,facing)
>> (setf ,facing-piece (rest ,facing)))))))
>
> Here is a version with a smaller macro-expansion footprint:
>
> (eval-when (:compile-toplevel :load-toplevel :execute)
> (defun pop-dequeue-helper (facing-piece other-piece)
> (if (null facing-piece)
> (let ((other-rev (nreverse other-piece)))
> (values (first other-rev) (rest other-rev) nil))
> (values (first facing-piece) (rest facing-piece) other-piece))))
>
> (defmacro pop-dequeue (facing-piece other-piece)
> (let ((result (gensym))
> (new-facing (gensym))
> (new-other (gensym)))
> `(multiple-value-bind (,result ,new-facing ,new-other)
> (pop-dequeue-helper ,facing-piece ,other-piece)
> (psetf ,facing-piece ,new-facing
> ,other-piece ,new-other)
> ,result)))
>
> The work is done with a helper function now with an interface that
> allows you to replace it with that bisective strategy for moving nodes
> from one list to the other without recompiling the macro expansions.
Thanks, I'm using this version now.
-lv
On Feb 28, 12:19 am, Kaz Kylheku <········@gmail.com> wrote:
> Here is an idea for defending against this attack: suppose that
> instead of simply flipping the list from one side to the other, we
> chop it exactly in half, and move half the nodes.
Here is an implementation which moves just one half the nodes from the
opposite stack, if that stack is longer than 10 elements, otherwise
the whole thing.
(eval-when (:compile-toplevel :load-toplevel :execute)
(defun bisect-list (list &optional (minimum-length 0))
(do ((double-skipper (cddr list) (cddr double-skipper))
(single-skipper list (cdr single-skipper))
(length 2 (+ length (if (cdr double-skipper) 2 1))))
((null double-skipper)
(cond
((< length minimum-length)
(values list nil))
((consp single-skipper)
(multiple-value-prog1
(values list (cdr single-skipper))
(setf (cdr single-skipper) nil)))
(t (values list nil))))))
(defun pop-deque-helper (facing-piece other-piece)
(if (null facing-piece)
(multiple-value-bind (head tail) (bisect-list other-piece 10)
(let ((remaining (if tail head))
(moved (nreverse (or tail head))))
(values (first moved) (rest moved) remaining)))
(values (first facing-piece) (rest facing-piece) other-piece))))
(defmacro pop-deque (facing-piece other-piece)
(let ((result (gensym))
(new-facing (gensym))
(new-other (gensym)))
`(multiple-value-bind (,result ,new-facing ,new-other)
(pop-deque-helper ,facing-piece ,other-
piece)
(psetf ,facing-piece ,new-facing
,other-piece ,new-other)
,result)))
thus spoke vanekl <·····@acd.net>:
> What is the recommended way to Push/Pop for the tail end of lists?
> I've come up with the following. I know the pop-end implementation
> isn't the most efficient, but simple imp is important to me, too.
Go for tail-consing.
(defmacro with-collect ((fn) &body body)
(let ((last-name (gensym "LAST-NAME"))
(list-name (gensym "LIST-NAME")))
`(let* ((,list-name (list nil))
(,last-name ,list-name))
(flet ((,fn (obj)
(setq ,last-name (setf (cdr ,last-name) (cons obj nil)))
(cdr ,list-name)))
(declaim (inline ,fn))
,@body)
(cdr ,list-name))))
> BTW, is there any advantage to making these inline functions instead
> of macros? Wouldn't the two techniques pretty much accomplish the
> same in this case?
Inline functions can be called indirectly. However, in the case where a
variable binding has its value modified by a macro, it can't be replaced
by a function, inline or not.
--
Nawet świnka wejdzie na drzewo kiedy ją chwalą.
thus spoke vanekl <·····@acd.net>:
> What is the recommended way to Push/Pop for the tail end of lists?
> I've come up with the following. I know the pop-end implementation
> isn't the most efficient, but simple imp is important to me, too.
This is rather unusual use for lists. If you only need to append to the
end, tail-consing is the way:
(defmacro with-collect ((fn) &body body)
(let ((last-name (gensym "LAST-NAME"))
(list-name (gensym "LIST-NAME")))
`(let* ((,list-name (list nil))
(,last-name ,list-name))
(flet ((,fn (obj)
(setq ,last-name (setf (cdr ,last-name) (cons obj nil)))
(cdr ,list-name)))
(declaim (inline ,fn))
,@body)
(cdr ,list-name))))
If tail-popping is also required, it might be more sensible to use the
standard PUSH/POP macros and NREVERSE at the end of the function.
> BTW, is there any advantage to making these inline functions instead
> of macros? Wouldn't the two techniques pretty much accomplish the
> same in this case?
Inline functions can be called indirectly. However, in the case where a
variable binding has its value modified by a macro (as in the code
snippet), it can't be replaced by a function, inline or not.
--
Nawet świnka wejdzie na drzewo kiedy ją chwalą.
Stanisław Halik wrote:
> thus spoke vanekl <·····@acd.net>:
>
>> What is the recommended way to Push/Pop for the tail end of lists?
>> I've come up with the following. I know the pop-end implementation
>> isn't the most efficient, but simple imp is important to me, too.
>
> This is rather unusual use for lists. If you only need to append to the
> end, tail-consing is the way:
>
> (defmacro with-collect ((fn) &body body)
> (let ((last-name (gensym "LAST-NAME"))
> (list-name (gensym "LIST-NAME")))
> `(let* ((,list-name (list nil))
> (,last-name ,list-name))
> (flet ((,fn (obj)
> (setq ,last-name (setf (cdr ,last-name) (cons obj nil)))
> (cdr ,list-name)))
> (declaim (inline ,fn))
> ,@body)
> (cdr ,list-name))))
>
[snip]
I guess I should have been explicit by saying that
the data structure has to expand and contract from both
ends, and by the time the algorithm has finished running
the data structure is discarded.
Sorry for the confusion.
-lv
vanekl <·····@acd.net> wrote:
+---------------
| I guess I should have been explicit by saying that
| the data structure has to expand and contract from both
| ends, and by the time the algorithm has finished running
| the data structure is discarded.
+---------------
I think you want this:
http://en.wikipedia.org/wiki/Linked_list#Doubly-linked_list
or maybe this:
http://en.wikipedia.org/wiki/Linked_list#Doubly-circularly-linked_list
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
vanekl <·····@acd.net> writes:
> What is the recommended way to Push/Pop for the tail end of lists?
> I've come up with the following. I know the pop-end implementation
> isn't the most efficient, but simple imp is important to me, too.
> BTW, is there any advantage to making these inline functions instead
> of macros? Wouldn't the two techniques pretty much accomplish the
> same in this case?
> Thanks
> -lv
>
>
> (defmacro push-end (list item)
> `(if (null ,list)
> (setf ,list (list ,item))
> (nconc ,list (list ,item))))
>
>
> (defmacro pop-end (place)
> `(prog1
> (first (last ,place))
> (if (null (second ,place))
> (setf ,place nil)
> (rplacd (last ,place 2) nil))))
What about this API:
(let ((my-list (list 'a 'b 'c 'd 'e)))
(WITH-LIST-TAIL my-list
(loop :repeat 3 :do (POP my-list))
(loop :for i :from 0 :to 5 :do (PUSH i my-list)))
my-list)
--> (A B 0 1 2 3 4 5)
If you could cope with this API, then POP and PUSH are O(1), and
WITH-LIST-TAIL is O(N), with the constant equal to about 2, which
would be much faster than PUSH-END and POP-END in a loop...
(defmacro with-list-tail (list-var &body body)
`(unwind-protect
(progn (setf ,list-var (reverse ,list-var))
,@body)
(setf ,list-var (nreverse ,list-var))))
--
__Pascal Bourguignon__
Pascal J. Bourguignon wrote:
> vanekl <·····@acd.net> writes:
>
>> What is the recommended way to Push/Pop for the tail end of lists?
>> I've come up with the following. I know the pop-end implementation
>> isn't the most efficient, but simple imp is important to me, too.
>> BTW, is there any advantage to making these inline functions instead
>> of macros? Wouldn't the two techniques pretty much accomplish the
>> same in this case?
>> Thanks
>> -lv
>>
>>
>> (defmacro push-end (list item)
>> `(if (null ,list)
>> (setf ,list (list ,item))
>> (nconc ,list (list ,item))))
>>
>>
>> (defmacro pop-end (place)
>> `(prog1
>> (first (last ,place))
>> (if (null (second ,place))
>> (setf ,place nil)
>> (rplacd (last ,place 2) nil))))
>
>
> What about this API:
>
> (let ((my-list (list 'a 'b 'c 'd 'e)))
> (WITH-LIST-TAIL my-list
> (loop :repeat 3 :do (POP my-list))
> (loop :for i :from 0 :to 5 :do (PUSH i my-list)))
> my-list)
> --> (A B 0 1 2 3 4 5)
[snip]
Interesting solution, but I'm working with a deque
(I guess I should have mentioned this--sorry),
so this doesn't help me in this situation.
Have to work both ends of list.
vanekl <·····@acd.net> writes:
> Pascal J. Bourguignon wrote:
>> vanekl <·····@acd.net> writes:
>>
>>> What is the recommended way to Push/Pop for the tail end of lists?
>>> I've come up with the following. I know the pop-end implementation
>>> isn't the most efficient, but simple imp is important to me, too.
>>> BTW, is there any advantage to making these inline functions instead
>>> of macros? Wouldn't the two techniques pretty much accomplish the
>>> same in this case?
>>> Thanks
>>> -lv
>>>
>>>
>>> (defmacro push-end (list item)
>>> `(if (null ,list)
>>> (setf ,list (list ,item))
>>> (nconc ,list (list ,item))))
>>>
>>>
>>> (defmacro pop-end (place)
>>> `(prog1
>>> (first (last ,place))
>>> (if (null (second ,place))
>>> (setf ,place nil)
>>> (rplacd (last ,place 2) nil))))
>> What about this API:
>> (let ((my-list (list 'a 'b 'c 'd 'e)))
>> (WITH-LIST-TAIL my-list
>> (loop :repeat 3 :do (POP my-list))
>> (loop :for i :from 0 :to 5 :do (PUSH i my-list)))
>> my-list)
>> --> (A B 0 1 2 3 4 5)
> [snip]
>
> Interesting solution, but I'm working with a deque
> (I guess I should have mentioned this--sorry),
> so this doesn't help me in this situation.
> Have to work both ends of list.
Well, then I would just introduce the data type, and keep a pointer to the end of the list.
See for example: http://darcs.informatimago.com/lisp/common-lisp/queue.lisp
--
__Pascal Bourguignon__
Pascal J. Bourguignon wrote:
> vanekl <·····@acd.net> writes:
>
>> Pascal J. Bourguignon wrote:
>>> vanekl <·····@acd.net> writes:
>>>
>>>> What is the recommended way to Push/Pop for the tail end of lists?
>>>> I've come up with the following. I know the pop-end implementation
>>>> isn't the most efficient, but simple imp is important to me, too.
>>>> BTW, is there any advantage to making these inline functions instead
>>>> of macros? Wouldn't the two techniques pretty much accomplish the
>>>> same in this case?
>>>> Thanks
>>>> -lv
>>>>
>>>>
>>>> (defmacro push-end (list item)
>>>> `(if (null ,list)
>>>> (setf ,list (list ,item))
>>>> (nconc ,list (list ,item))))
>>>>
>>>>
>>>> (defmacro pop-end (place)
>>>> `(prog1
>>>> (first (last ,place))
>>>> (if (null (second ,place))
>>>> (setf ,place nil)
>>>> (rplacd (last ,place 2) nil))))
>>> What about this API:
>>> (let ((my-list (list 'a 'b 'c 'd 'e)))
>>> (WITH-LIST-TAIL my-list
>>> (loop :repeat 3 :do (POP my-list))
>>> (loop :for i :from 0 :to 5 :do (PUSH i my-list)))
>>> my-list)
>>> --> (A B 0 1 2 3 4 5)
>> [snip]
>>
>> Interesting solution, but I'm working with a deque
>> (I guess I should have mentioned this--sorry),
>> so this doesn't help me in this situation.
>> Have to work both ends of list.
>
> Well, then I would just introduce the data type, and keep a pointer to the end of the list.
> See for example: http://darcs.informatimago.com/lisp/common-lisp/queue.lisp
Yeah, I think I can convert this to a deque easy enough.
I like the ascii art, but you sure shout a lot when you code :)
vanekl <·····@acd.net> writes:
> Pascal J. Bourguignon wrote:
>> vanekl <·····@acd.net> writes:
>>
>>> Pascal J. Bourguignon wrote:
>>>> vanekl <·····@acd.net> writes:
>>>>
>>>>> What is the recommended way to Push/Pop for the tail end of lists?
>>>>> I've come up with the following. I know the pop-end implementation
>>>>> isn't the most efficient, but simple imp is important to me, too.
>>>>> BTW, is there any advantage to making these inline functions instead
>>>>> of macros? Wouldn't the two techniques pretty much accomplish the
>>>>> same in this case?
>>>>> Thanks
>>>>> -lv
>>>>>
>>>>>
>>>>> (defmacro push-end (list item)
>>>>> `(if (null ,list)
>>>>> (setf ,list (list ,item))
>>>>> (nconc ,list (list ,item))))
>>>>>
>>>>>
>>>>> (defmacro pop-end (place)
>>>>> `(prog1
>>>>> (first (last ,place))
>>>>> (if (null (second ,place))
>>>>> (setf ,place nil)
>>>>> (rplacd (last ,place 2) nil))))
>>>> What about this API:
>>>> (let ((my-list (list 'a 'b 'c 'd 'e)))
>>>> (WITH-LIST-TAIL my-list
>>>> (loop :repeat 3 :do (POP my-list))
>>>> (loop :for i :from 0 :to 5 :do (PUSH i my-list)))
>>>> my-list)
>>>> --> (A B 0 1 2 3 4 5)
>>> [snip]
>>>
>>> Interesting solution, but I'm working with a deque
>>> (I guess I should have mentioned this--sorry),
>>> so this doesn't help me in this situation.
>>> Have to work both ends of list.
>> Well, then I would just introduce the data type, and keep a pointer
>> to the end of the list.
>> See for example: http://darcs.informatimago.com/lisp/common-lisp/queue.lisp
>
> Yeah, I think I can convert this to a deque easy enough.
> I like the ascii art, but you sure shout a lot when you code :)
Yep, nostalgy; it's to make it appear older ;-)
If you want to downcase it easily have a look at downcase-lisp and upcase-lisp in:
http://darcs.informatimago.com/emacs/pjb-sources.el
--
__Pascal Bourguignon__
PJB> If you could cope with this API, then POP and PUSH are O(1), and
PJB> WITH-LIST-TAIL is O(N), with the constant equal to about 2, which
PJB> would be much faster than PUSH-END and POP-END in a loop...
i think we should distinguish O(N) run time from O(N) consing amount.
"Alex Mizrahi" <········@users.sourceforge.net> writes:
> PJB> If you could cope with this API, then POP and PUSH are O(1), and
> PJB> WITH-LIST-TAIL is O(N), with the constant equal to about 2, which
> PJB> would be much faster than PUSH-END and POP-END in a loop...
>
> i think we should distinguish O(N) run time from O(N) consing amount.
Right. I introduced a O(N) consing for security. But if you're sure
you're working with reversable lists, you can use NREVERSE instead.
Perhaps a NWITH-LIST-TAIL...
--
__Pascal Bourguignon__
Den Wed, 27 Feb 2008 04:03:39 -0800 skrev vanekl:
> What is the recommended way to Push/Pop for the tail end of lists? I've
> come up with the following. I know the pop-end implementation isn't the
> most efficient, but simple imp is important to me, too. BTW, is there
> any advantage to making these inline functions instead of macros?
> Wouldn't the two techniques pretty much accomplish the same in this
> case?
Take a look at http://www.tfeb.org/lisp/hax.html#COLLECTING , too. I
guess the macro shouldn't be too hard to extend to allow popping as well.
Cheers,
Maciej