Remove last element in a list

Remove last element in a list

[Nordlöw]

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

Thanks,
Nordlöw

Re: Remove last element in a list

[LanX]

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

Reverse pop, return value

[LanX]

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

Re: Reverse pop, return value

[Lennart Borgman]

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

Re: Reverse pop, return value

[David Kastrup]

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

Re: Reverse pop, return value

[LanX]

Thanx Lennart!

Thats what I was looking for! 8)

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

bye
  rolf

Re: Reverse pop, return value

[LanX]

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

Re: Remove last element in a list

[Barry Margolin]

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

Re: Reverse pop, return value

[Barry Margolin]

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

Re: Reverse pop, return value

[LanX]

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

Re: Reverse pop, return value

[Barry Margolin]

[-- 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 ***