unofficial mirror of help-gnu-emacs@gnu.org
 help / color / mirror / Atom feed
* Remove last element in a list
@ 2009-11-17 13:11 Nordlöw
  2009-11-17 14:20 ` LanX
  0 siblings, 1 reply; 11+ messages in thread
From: Nordlöw @ 2009-11-17 13:11 UTC (permalink / raw)
  To: help-gnu-emacs

How do I most efficiently remove the last element in a list?

Thanks,
Nordlöw


^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Remove last element in a list
  2009-11-17 13:11 Remove last element in a list Nordlöw
@ 2009-11-17 14:20 ` LanX
  2009-11-17 15:32   ` Reverse pop, return value LanX
  2009-11-17 21:26   ` Remove last element in a list Barry Margolin
  0 siblings, 2 replies; 11+ messages in thread
From: LanX @ 2009-11-17 14:20 UTC (permalink / raw)
  To: help-gnu-emacs

----------- M-x ielm
ELISP> list
(a b c d e f g h i)

ELISP> (nbutlast list 1)
(a b c d e f g h)

ELISP> list
(a b c d e f g h)
-------------

see  "5.3 Accessing Elements of Lists" in  Elisp-Info

HTH
  LanX


^ permalink raw reply	[flat|nested] 11+ messages in thread

* Reverse pop, return value
  2009-11-17 14:20 ` LanX
@ 2009-11-17 15:32   ` LanX
  2009-11-17 15:48     ` Lennart Borgman
                       ` (2 more replies)
  2009-11-17 21:26   ` Remove last element in a list Barry Margolin
  1 sibling, 3 replies; 11+ messages in thread
From: LanX @ 2009-11-17 15:32 UTC (permalink / raw)
  To: help-gnu-emacs

Hi

I tried to realize a reverse pop which pops from the end of the list,
but the code get's "lengthy"....

I need to define a local variable to hold the return value... is there
a more elegant way to do it?

 ----------- M-x ielm
ELISP> (defun rpop (LIST)
	 "reverse pop"
	 (let
            ( (ret (car (last LIST))) )
            (nbutlast LIST 1)
	    ret
	 )
       )
rpop
ELISP> (setq list '(a b c d e f g h i j))
(a b c d e f g h i j)

ELISP> (rpop list)
j
ELISP> (rpop list)
i
ELISP> (rpop list)
h
 -------------

There must be a technique to simplify this !?!
Thanx
  Rolf


^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Reverse pop, return value
  2009-11-17 15:32   ` Reverse pop, return value LanX
@ 2009-11-17 15:48     ` Lennart Borgman
  2009-11-17 16:53     ` David Kastrup
       [not found]     ` <mailman.10897.1258472938.2239.help-gnu-emacs@gnu.org>
  2 siblings, 0 replies; 11+ messages in thread
From: Lennart Borgman @ 2009-11-17 15:48 UTC (permalink / raw)
  To: LanX; +Cc: help-gnu-emacs

On Tue, Nov 17, 2009 at 4:32 PM, LanX <lanx.perl@googlemail.com> wrote:
> Hi
>
> I tried to realize a reverse pop which pops from the end of the list,
> but the code get's "lengthy"....
>
> I need to define a local variable to hold the return value... is there
> a more elegant way to do it?
>
>  ----------- M-x ielm
> ELISP> (defun rpop (LIST)
>         "reverse pop"
>         (let
>            ( (ret (car (last LIST))) )
>            (nbutlast LIST 1)
>            ret
>         )
>       )

prog1




^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Reverse pop, return value
  2009-11-17 15:32   ` Reverse pop, return value LanX
  2009-11-17 15:48     ` Lennart Borgman
@ 2009-11-17 16:53     ` David Kastrup
  2009-11-17 17:33       ` LanX
       [not found]     ` <mailman.10897.1258472938.2239.help-gnu-emacs@gnu.org>
  2 siblings, 1 reply; 11+ messages in thread
From: David Kastrup @ 2009-11-17 16:53 UTC (permalink / raw)
  To: help-gnu-emacs

LanX <lanx.perl@googlemail.com> writes:

> Hi
>
> I tried to realize a reverse pop which pops from the end of the list,
> but the code get's "lengthy"....

Don't do that.  If you really need to process the list in reverse order,
_first_ reverse it, then process it from the front.

Reversing is O(n), popping from the front O(1), so working off the whole
list is O(n).  Popping from the end is O(n), making work on the whole
list O(n^2).

-- 
David Kastrup


^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Reverse pop, return value
       [not found]     ` <mailman.10897.1258472938.2239.help-gnu-emacs@gnu.org>
@ 2009-11-17 17:20       ` LanX
  2009-11-17 21:34         ` Barry Margolin
  0 siblings, 1 reply; 11+ messages in thread
From: LanX @ 2009-11-17 17:20 UTC (permalink / raw)
  To: help-gnu-emacs

Thanx Lennart!

Thats what I was looking for! 8)

---------------
(defun rpop (LIST)
	 "reverse pop"
	 (prog1
            (car (last LIST))
            (nbutlast LIST 1)
	 )
       )
--------------

bye
  rolf



^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Reverse pop, return value
  2009-11-17 16:53     ` David Kastrup
@ 2009-11-17 17:33       ` LanX
  0 siblings, 0 replies; 11+ messages in thread
From: LanX @ 2009-11-17 17:33 UTC (permalink / raw)
  To: help-gnu-emacs

Hi

On 17 Nov., 17:53, David Kastrup <d...@gnu.org> wrote:
> Reversing is O(n), popping from the front O(1), so working off the whole
> list is O(n).  Popping from the end is O(n), making work on the whole
> list O(n^2).

Thx David, good point!

I will keep it in mind for cases where I can't control that lists are
short.

Anyway my motivation was more to learn basic things like (prog1)!

Personally I prefer to delay optimizations (and potential complication
of the code) to the point when profiling shows the need for it.

But just from curiosity, having a FIFO stack situation (without
clearly separated IN/OUT-phases where I can just reverse once) , whats
the optimized way to push and pop then?

Maybe always keeping a pointer to the end of the list?

cheers
  Rolf


^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Remove last element in a list
  2009-11-17 14:20 ` LanX
  2009-11-17 15:32   ` Reverse pop, return value LanX
@ 2009-11-17 21:26   ` Barry Margolin
  1 sibling, 0 replies; 11+ messages in thread
From: Barry Margolin @ 2009-11-17 21:26 UTC (permalink / raw)
  To: help-gnu-emacs

In article 
<f1412cfb-1d34-40b3-8192-e528d912cc46@e23g2000yqd.googlegroups.com>,
 LanX <lanx.perl@googlemail.com> wrote:

> ----------- M-x ielm
> ELISP> list
> (a b c d e f g h i)
> 
> ELISP> (nbutlast list 1)
> (a b c d e f g h)
> 
> ELISP> list
> (a b c d e f g h)
> -------------
> 
> see  "5.3 Accessing Elements of Lists" in  Elisp-Info
> 
> HTH
>   LanX

ELISP> list
(a)

ELISP> (nbutlast list 1)
nil

ELISP> list
(a)

Moral: always assign the result back to the variable, even when using 
destructive operations, e.g.

ELISP> (setq list (nbutlist list 1))
nil

ELISP> list
nil

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***


^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Reverse pop, return value
  2009-11-17 17:20       ` LanX
@ 2009-11-17 21:34         ` Barry Margolin
  2009-11-18  0:28           ` LanX
  0 siblings, 1 reply; 11+ messages in thread
From: Barry Margolin @ 2009-11-17 21:34 UTC (permalink / raw)
  To: help-gnu-emacs

In article 
<9af6462e-4a2e-4325-b11d-9d8a6c2686b5@r24g2000yqd.googlegroups.com>,
 LanX <lanx.perl@googlemail.com> wrote:

> Thanx Lennart!
> 
> Thats what I was looking for! 8)
> 
> ---------------
> (defun rpop (LIST)
> 	 "reverse pop"
> 	 (prog1
>             (car (last LIST))
>             (nbutlast LIST 1)
> 	 )
>        )
> --------------
> 
> bye
>   rolf

As I mentioned in the "remove last element in a list" thread, this won't 
work when the list gets down to 1 element.  nbutlast works by changing 
the cdr of the 2nd-to-last cons cell in the list to point to nil.  But 
if there's only 1 element, there's no 2nd-to-last cons cell to modify.  
You need to assign to the original variable, and this can only be done 
using a macro (that's why push and pop are macros).

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***


^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Reverse pop, return value
  2009-11-17 21:34         ` Barry Margolin
@ 2009-11-18  0:28           ` LanX
  2009-11-19 13:41             ` Barry Margolin
  0 siblings, 1 reply; 11+ messages in thread
From: LanX @ 2009-11-18  0:28 UTC (permalink / raw)
  To: help-gnu-emacs

Hi

On 17 Nov., 22:34, Barry Margolin <bar...@alum.mit.edu> wrote:
> As I mentioned in the "remove last element in a list" thread, this won't
> work when the list gets down to 1 element.  nbutlast works by changing
> the cdr of the 2nd-to-last cons cell in the list to point to nil.  But
> if there's only 1 element, there's no 2nd-to-last cons cell to modify.  

Thx, so this is the way to go?

(defmacro rpop (LIST)
         "reverse pop"
         `(prog1
            (car (last ,LIST))
	   (setq ,LIST (butlast ,LIST 1))
	   )
	 )

> You need to assign to the original variable, and this can only be done
> using a macro (that's why push and pop are macros).

Hmm, for better understanding, could it be done with a defun if I pass
a quoted symbol?

something like:

(rpop-symb 'list)

Cheers
  Rolf


^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Reverse pop, return value
  2009-11-18  0:28           ` LanX
@ 2009-11-19 13:41             ` Barry Margolin
  0 siblings, 0 replies; 11+ messages in thread
From: Barry Margolin @ 2009-11-19 13:41 UTC (permalink / raw)
  To: help-gnu-emacs

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1231 bytes --]

In article 
<ef7158e9-63ef-4be8-bdca-72d0155a1943@c3g2000yqd.googlegroups.com>,
 LanX <lanx.perl@googlemail.com> wrote:

> Hi
> 
> On 17 Nov., 22:34, Barry Margolin <bar...@alum.mit.edu> wrote:
> > As I mentioned in the "remove last element in a list" thread, this won't
> > work when the list gets down to 1 element.  nbutlast works by changing
> > the cdr of the 2nd-to-last cons cell in the list to point to nil.  But
> > if there's only 1 element, there's no 2nd-to-last cons cell to modify.  
> 
> Thx, so this is the way to go?
> 
> (defmacro rpop (LIST)
>          "reverse pop"
>          `(prog1
>             (car (last ,LIST))
> 	   (setq ,LIST (butlast ,LIST 1))
> 	   )
> 	 )

Yes.

> 
> > You need to assign to the original variable, and this can only be done
> > using a macro (that's why push and pop are macros).
> 
> Hmm, for better understanding, could it be done with a defun if I pass
> a quoted symbol?
> 
> something like:
> 
> (rpop-symb 'list)

Yes, that would work.  That's why add-to-list requires a quoted symbol.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***


^ permalink raw reply	[flat|nested] 11+ messages in thread

end of thread, other threads:[~2009-11-19 13:41 UTC | newest]

Thread overview: 11+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2009-11-17 13:11 Remove last element in a list Nordlöw
2009-11-17 14:20 ` LanX
2009-11-17 15:32   ` Reverse pop, return value LanX
2009-11-17 15:48     ` Lennart Borgman
2009-11-17 16:53     ` David Kastrup
2009-11-17 17:33       ` LanX
     [not found]     ` <mailman.10897.1258472938.2239.help-gnu-emacs@gnu.org>
2009-11-17 17:20       ` LanX
2009-11-17 21:34         ` Barry Margolin
2009-11-18  0:28           ` LanX
2009-11-19 13:41             ` Barry Margolin
2009-11-17 21:26   ` Remove last element in a list Barry Margolin

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).