How to delete the last element of a SKILL list

[Thomas]

what is the most effectiant way?

 

[Jimka]

the easiest way to do this is to build the list in the other
order. ask yourself why is the list in the order it is in, and
can it be built in the other order.

for example if you use push to add elements to a list
then you can use pop to pop them off. this is
very fast and memory efficient.

but in general to remove any element from a list with the
remove function.

x = (list 1 2 3 4 5 6 7)

now x has value (1 2 3 4 5 6 7)

if you want to remove 4 from x
(remove 4 x)

and x has value (1 2 3 5 6 7)

-jim

 

[Thomas]

In fact, the last element is useful at first. For some reason, I need
to delete it the later use.
Now I use car(last(my_List)) to get the
last element and remove it with remd(),

but I think such operation need to traverse the list two times, I want
to know whehter a single traversal is enough.

Jimkawrote:
the easiest way to do this is to build the list in the other
order. ask yourself why is the list in the order it is in, and
can it be built in the other order.

for example if you use push to add elements to a list
then you can use pop to pop them off. this is
very fast and memory efficient.

but in general to remove any element from a list with the
remove function.

x = (list 1 2 3 4 5 6 7)

now x has value (1 2 3 4 5 6 7)

if you want to remove 4 from x
(remove 4 x)

and x has value (1 2 3 5 6 7)

-jim

 

[Bernd Fischer]

What about
x = list( 1 2 3 4 5 6 7 )
remove( length( x ) x )


Bernd

 

[Jimka]

How did the element you want to remove get at the end of the list?
Why is it the last element you need to remove rather than the 13th for
example? Sometimes there are very good reasons for operating
on the last element, however it normally means you built the list
in the wrong order to begin with, or that you should be using a
different type of data structure than a list.

How did the element get to the end of the list anyway?
Why don't you already know its value without having to use
car(last(...))?

 

[Rajeswaran M]

It can simply be due to reading an input file, whose last column
may be irrelevent to the function he is working

Jimka wrote:

How did the element you want to remove get at the end of the list?
Why is it the last element you need to remove rather than the 13th for
example? Sometimes there are very good reasons for operating
on the last element, however it normally means you built the list
in the wrong order to begin with, or that you should be using a
different type of data structure than a list.

How did the element get to the end of the list anyway?
Why don't you already know its value without having to use
car(last(...))?

 

[Jimka]

yes you are right, as i said there are certainly very good reasons for
wanting
to do this. However, in my experience it is also quite often that
the programmer is going about the problem wrong, and it is really
much simpler. I.e., if his program put the element at the end of
the list, then simply avoid putting it there and the problem does
not arrise. If he knows what the last element is, he can remove it
with remove (assuming it only appears at the end and not also
somewhere in the middle).
list = ( 1 2 3 1 2 3 1 2 3 1 2 3 1 2)
(remove 2 list) will return ( 1 3 1 3 1 3 1 3 1)
which is probably not what you want.

If you really want to remove the last element of a list without
knowing what it is try this:

(defun remove_last (list)
(let ((new (list nil))) ; allocate a seed for tconc
(foreach map sublist list ; iterate over the cons cells
(when (cdr sublist) ; unless we are at the end of
the list
(tconc new (car sublist)))) ; efficiently append an element
(car new))) ; return the new list

this will also work, but consumes
a lot of memory for large lists.

(defun remove_last (list)
(reverse (cdr (reverse list))))

 

[Andrew Beckett]

On 6 Dec 2005 15:32:17 -0800, "Jimka" <jimka@rdrop.com> wrote:

yes you are right, as i said there are certainly very good reasons for
wanting
to do this. However, in my experience it is also quite often that
the programmer is going about the problem wrong, and it is really
much simpler. I.e., if his program put the element at the end of
the list, then simply avoid putting it there and the problem does
not arrise. If he knows what the last element is, he can remove it
with remove (assuming it only appears at the end and not also
somewhere in the middle).
list = ( 1 2 3 1 2 3 1 2 3 1 2 3 1 2)
(remove 2 list) will return ( 1 3 1 3 1 3 1 3 1)
which is probably not what you want.

If you really want to remove the last element of a list without
knowing what it is try this:

(defun remove_last (list)
(let ((new (list nil))) ; allocate a seed for tconc
(foreach map sublist list ; iterate over the cons cells
(when (cdr sublist) ; unless we are at the end of
the list
(tconc new (car sublist)))) ; efficiently append an element
(car new))) ; return the new list

this will also work, but consumes
a lot of memory for large lists.

(defun remove_last (list)
(reverse (cdr (reverse list))))

Here's a version that does it destructively, so avoids the need to
create a new list (but has the side effect of modifying the list in place,
so be warned):

(defun abRemoveLast (list)
(when (cdr list)
(foreach map sublist list
(unless (cddr sublist) (rplacd sublist nil))
)
)
)

Andrew.

 

[Thomas]

I certainly attempt to avoid dealing with the last element of the list
in my program,
but the list is symmetric and the status of the first element is same
as the last one, and so on.
All the elements is useful at first, then the first and last one need
to be deleted.
I know that deleting one element of a list in other programming
language is an trivial operation and a single traversal is enough.
I put forward the question since I am afraid of not reading the
documents of SKILL thoroughly.
It has nothing to do with the data structure and code style of my
program.

Jimkawrote:
yes you are right, as i said there are certainly very good reasons

for

wanting
to do this. However, in my experience it is also quite often that
the programmer is going about the problem wrong, and it is really
much simpler. I.e., if his program put the element at the end of
the list, then simply avoid putting it there and the problem does
not arrise. If he knows what the last element is, he can remove it
with remove (assuming it only appears at the end and not also
somewhere in the middle).
list = ( 1 2 3 1 2 3 1 2 3 1 2 3 1 2)
(remove 2 list) will return ( 1 3 1 3 1 3 1 3 1)
which is probably not what you want.

If you really want to remove the last element of a list without
knowing what it is try this:

(defun remove_last (list)
(let ((new (list nil))) ; allocate a seed for
tconc
(foreach map sublist list ; iterate over the cons
cells
(when (cdr sublist) ; unless we are at the end
of
the list
(tconc new (car sublist)))) ; efficiently append an
element
(car new))) ; return the new list

this will also work, but consumes
a lot of memory for large lists.

(defun remove_last (list)
(reverse (cdr (reverse list))))

 

[fogh]

Bernd Fischer > wrote:

What about
x = list( 1 2 3 4 5 6 7 )
remove( length( x ) x )

try it with
x=list( a b c d )

 

[Andrew Beckett]

On Wed, 07 Dec 2005 06:28:31 +0000, Andrew Beckett
<andrewb@DcEaLdEeTnEcTe.HcIoSm> wrote:

Here's a version that does it destructively, so avoids the need to
create a new list (but has the side effect of modifying the list in place,
so be warned):

(defun abRemoveLast (list)
(when (cdr list)
(foreach map sublist list
(unless (cddr sublist) (rplacd sublist nil))
)
)
)

Andrew.

Whilst the above traverses the list just once, it has repeated
calls to cddr - which has to look at the pointer of the next list cell,
so has to follow two pointers (if you like), so it's doing as many list
hops as traversing the list twice. Another formulation would be to do:

(defun abRemoveLast (list)
(let ((prevsub list))
(when (cdr list)
(foreach map sublist list
(unless (cdr sublist) (rplacd prevsub nil))
(setq prevsub sublist)
)
)
)
)

I just tried profiling this with a 10 million element list. This gives:

Function Name Total Inside
------------- ----- ------
TOTAL CPU Time (secs) 8.65 8.65
toplevel 8.65 0.01
map 8.64 6.63
abRemoveLast 8.64 0.00
cdr 2.01 2.01

Whereas the previous version gave:

Function Name Total Inside
------------- ----- ------
TOTAL CPU Time (secs) 9.37 9.37
map 9.37 6.12
abRemoveLast 9.37 0.00
toplevel 9.37 0.00
cddr 3.25 3.25

I started trying to profile Jim's version, but with such a long list it
was so slow I decided not to wait for the results... of course, it's
a reasonable option if you want it not to be destructive.

Of my two versions, the newer one above is (very slightly) quicker, but this
is going to be pretty marginal in most normal cases!

Andrew.

 

[Bernd Fischer]

I had in mind that 'remove' needs an 'index' and not a
'value' as first arg, SORRY my mistake.

Bernd

fogh wrote:

Bernd Fischer > wrote:

What about
x = list( 1 2 3 4 5 6 7 )
remove( length( x ) x )


try it with
x=list( a b c d )

 

[Jimka]

another way to do it would work if you can always remember
how long the list is. Since you are removing items in pairs,
first and last, the length decreases by 2 each time.

you can use (rplacd (nthcdr N the_list))

(nthcdr 0 ...) returns the list
(nthcdr 1 ...) returns the list after the first element
(nthcdr 2 ...) returns the list after the 2nd element

(sorry, i might be off by 1 in the index....)

so to remove everything after the Nth element (zero
based) you can use (rplacd (nthcdr N the_list))

 

[Andrew Beckett]

On 7 Dec 2005 11:24:33 -0800, "Jimka" <jimka@rdrop.com> wrote:

another way to do it would work if you can always remember
how long the list is. Since you are removing items in pairs,
first and last, the length decreases by 2 each time.

you can use (rplacd (nthcdr N the_list))

(nthcdr 0 ...) returns the list
(nthcdr 1 ...) returns the list after the first element
(nthcdr 2 ...) returns the list after the 2nd element

(sorry, i might be off by 1 in the index....)

so to remove everything after the Nth element (zero
based) you can use (rplacd (nthcdr N the_list))

I just profiled this:

(defun abQuickList (list)
(when (cdr list)
(rplacd (nthcdr (difference (length list) 2) list) nil)
list
)
)

Function Name Total Inside
------------- ----- ------
TOTAL CPU Time (secs) 0.48 0.48
abQuickList 0.48 0.00
toplevel 0.48 0.00
length 0.24 0.24
nthcdr 0.24 0.24

So whilst the list is being traversed twice - by length and nthcdr - it's done
very quickly. So this one wins so far - and it would be quicker still
if you already knew how long the list is. Not exactly bad for a list with
10 million elements in!

This shows the benefits of profiling - sometimes the most efficient is not
always the one that jumps out at you. Of course, if you're only dealing with
lists with a few elements in, pretty much any of the approaches would do,
unless you're doing this repeatedly.

Andrew.

 

[fogh]

It can also be argued that you should make 2 lists then. So that you would only
have to deal with 2 cars, not remq(car(last] or such. Then again... using 2 cars
is not a responsible attitude, especially SUVs (or cadence BMWs).

Thomas wrote:

I certainly attempt to avoid dealing with the last element of the list
in my program,
but the list is symmetric and the status of the first element is same
as the last one, and so on.
All the elements is useful at first, then the first and last one need
to be deleted.
I know that deleting one element of a list in other programming
language is an trivial operation and a single traversal is enough.
I put forward the question since I am afraid of not reading the
documents of SKILL thoroughly.
It has nothing to do with the data structure and code style of my
program.


Jimkawrote:

yes you are right, as i said there are certainly very good reasons
for

wanting
to do this. However, in my experience it is also quite often that
the programmer is going about the problem wrong, and it is really
much simpler. I.e., if his program put the element at the end of
the list, then simply avoid putting it there and the problem does
not arrise. If he knows what the last element is, he can remove it
with remove (assuming it only appears at the end and not also
somewhere in the middle).
list = ( 1 2 3 1 2 3 1 2 3 1 2 3 1 2)
(remove 2 list) will return ( 1 3 1 3 1 3 1 3 1)
which is probably not what you want.

If you really want to remove the last element of a list without
knowing what it is try this:

(defun remove_last (list)
(let ((new (list nil))) ; allocate a seed for

tconc

(foreach map sublist list ; iterate over the cons

cells

(when (cdr sublist) ; unless we are at the end

of

the list
(tconc new (car sublist)))) ; efficiently append an

element

(car new))) ; return the new list

this will also work, but consumes
a lot of memory for large lists.

(defun remove_last (list)
(reverse (cdr (reverse list))))