delete last element
sam...@cruzio.santa-cruz.ca.us
> How does one write a prolog program removing the last element of a list.
> I have it this way but it doesn't work. L is the original list. L1 is the
> final.
>
> cutlast([H|T],T1):- T \=[], cutlast(T,T1).
>
> Is this correct?
> The Renegade
Well yes, this is correct, except you need a clause for when T is null
cutlast(H|[],[]).
I wouldn't swear in court that this is correct, because I haven't used prolog
for 6 years.
..
Bill Hogan
NS> How does one write a prolog program removing the last element
NS> of a list. I have it this way but it doesn't work. L is the
NS> original list. L1 is the final.
NS> cutlast([H|T],T1):- T \=[], cutlast(T,T1).
NS> Is this correct?
% Let getlast(L,X) iff X is last element of nonempty list L,
getlast([X],X).
getlast([_,Y|L],X) :- getlast([Y|L],X).
<B
BILL HOGAN
* Origin: PCUG BBS - San Francisco HST/V.32 415-621-2609 (8:914/201.0)
Lars-Henrik Eriksson
cutlast(H|[],[]).
The first clause is incorrect, because it throws away H. You do need
the second clause (but that the syntax is wrong).
This program could be written most cleanly as:
cutlast([H, H2 | T], [H |T2]) :- cutlast([H2 | T], T2).
cutlast([H], []).
Many (most?) prolog systems would do construct an unnecessary term
when executing the first clause, so in practice one would probably
want to write it as:
cutlast([H | T], [H | T2]) :- T = [_|_], cutlast(T, T2).
Note that using inequality of T and [] is not a good idea, since its
behaviour when T is unbound will be wrong, unless the particular
Prolog has some kind of constraint system. Of course, if you never
intend to call this predicate with a first argument that is either an
unbound variable or a list with an unbound variable as tail, then it
doesn't matter.
--
Lars-Henrik Eriksson, Wilhelm-Schickard-Institut, Tuebingen University
On leave from the Swedish Institute of Computer Science until Oct. 20, 1993.
Internet: l...@logik.informatik.uni-tuebingen.de Phone: +49 7071 294284
At SICS: l...@sics.se Phone: +46 8 752 15 09
Anish Mahesh Mathuria
>How does one write a prolog program removing the last element of a list.
>I have it this way but it doesn't work. L is the original list. L1 is the
>final.
>cutlast([H|T],T1):- T \=[], cutlast(T,T1).
>Is this correct?
> The Renegade
No. You haven't included the following clause for the base case:
cutlast([H], []).
Also, the recursive clause should read as:
cutlast([H|T], [H|T1]) :-
cutlast(T, T1).
----------------------
Anish Mathuria
g931...@cs.uow.edu.au
----------------------
William Clocksin
> How does one write a prolog program removing the last element of a list.
Do not write the program as specified. Instead, write a program that maps a
list A onto a list B, in which list B is the same as A except has the last
element missing.
W.F. Clocksin
Joachim Schimpf
>
>Do not write the program as specified. Instead, write a program that maps a
>list A onto a list B, in which list B is the same as A except has the last
>element missing.
e.g. (not the most efficient, but the shortest solution :-)
allbutlast(A, B) :- append(B, [_], A).
---------------------------------------------------------------------------
Joachim Schimpf Email joa...@ecrc.de
European Computer-Industry Research Centre Phone +49 89 92699 111
Arabellastrasse 17, D-81925 Munich, Germany Fax +49 89 92699 170
Francois-Michel Lang
>In article 24...@infodev.cam.ac.uk, w...@cl.cam.ac.uk (William Clocksin) writes:
>>
>>Do not write the program as specified. Instead, write a program that maps a
>>list A onto a list B, in which list B is the same as A except has the last
>>element missing.
>
>e.g. (not the most efficient, but the shortest solution :-)
>
>allbutlast(A, B) :- append(B, [_], A).
As so often happens in Prolog, a great logical specification
makes a terrible program! Here's my attempt. Forgive me
if this is bogus...it's been well over 2 years since I did
anything serious in Prolog.
% del_last(+List, -NewList) instantiates NewList
% to the list List with its last element removed
del_last([], []).
del_last([H|T], List) :- del_last1(T, H, List).
% auxiliary predicate used by del_last/2...
del_last1([], _, []).
del_last1([H|T], Prev, [Prev|List]) :- del_last1(T, H, List).
The above is just an extension of the following:
% last(+List, -Element) instantiates Element
% to the last element of the list List
last([], []).
last([H|T], Last) :- last1(T, H, Last).
% auxiliary predicate used by last/2 to take advantage of first-arg indexing
last1([], Last, Last).
last1([H|T], _, Last) :- last1(T, H, Last).
---
------------------------------------------------------------------
Francois-Michel Lang (202) 752-6067 FAX: (202) 752-4530
alu...@fnma.com ............. Fannie Mae; Asset/Liability Strategy
la...@linc.cis.upenn.edu ..... Dept of Comp & Info Science, U of PA
Lars-Henrik Eriksson
In article A...@ecrc.de, joa...@ecrc.de (Joachim Schimpf) writes:
>In article 24...@infodev.cam.ac.uk, w...@cl.cam.ac.uk (William Clocksin) writes:
>>
>>Do not write the program as specified. Instead, write a program that maps a
>>list A onto a list B, in which list B is the same as A except has the last
>>element missing.
>
>e.g. (not the most efficient, but the shortest solution :-)
>
>allbutlast(A, B) :- append(B, [_], A).
As so often happens in Prolog, a great logical specification
makes a terrible program! Here's my attempt. Forgive me
if this is bogus...it's been well over 2 years since I did
anything serious in Prolog.
...Prolog program omitted...
The single-line program above is not at all terrible. Apart from the
lack of first-argument indexing (since the input argument to
allbutlast becomes the last argument to append), it will run as fast
as your program! It performs exactly as many procedure calls and
leaves exactly as many choicepoints.
As O'Keefe has pointed out: "elegance is not optional".
Francois-Michel Lang
>The single-line program above is not at all terrible. Apart from the
>lack of first-argument indexing (since the input argument to
>allbutlast becomes the last argument to append), it will run as fast
>as your program! It performs exactly as many procedure calls and
>leaves exactly as many choicepoints.
You're right. Sorry. The program
allbutlast(A, B) :- append(B, [_], A).
isn't inefficient. I guess I've just seen too many things like
sort(List, Sorted) :-
permutation(List, Sorted),
ordered(Sorted).
where clean specifications do not map into efficient programs.
WFC's example is a clean specification that DOES map into a good prg.
sam...@cruzio.santa-cruz.ca.us
I posted a follow-up in this duscussion (as far as I know the first follow up)
but subsequently my newsfeed was down so I missed part of the discussion. I
am back up again and th
all that terrible...". [A
Could someone e-mail me the articles I missed on this topic?
Thank you.