How to delete the last element from a list in Prol

问题:

I am in the following situation: I have a list and I would to delete from it only the last element.

I have implement the following rule (that don't work well):

deleteLastElement([Only],WithoutLast) :-
    !,
    delete([Only],Only,WithoutLast).
deleteLastElement([_|Tail],WithoutLast) :-
    !,
    deleteLastElement(Tail,WithoutLast).

The problem is that when I call it, all the element in the list are deleted, in fact if I execute the following statement I obtain:

[debug]  ?- deleteLastElement([a,b,c], List).
List = [].

Looking at the trace I think that is clear the cause of this problem:

[trace]  ?- deleteLastElement([a,b], List).
   Call: (7) deleteLastElement([a, b], _G396) ? creep
   Call: (8) deleteLastElement([b], _G396) ? creep
   Call: (9) lists:delete([b], b, _G396) ? creep
   Exit: (9) lists:delete([b], b, []) ? creep
   Exit: (8) deleteLastElement([b], []) ? creep
   Exit: (7) deleteLastElement([a, b], []) ? creep
List = [].

When the base case is reached, the WithoutLast list is unified with the empty list [] and when backtracking is performed the WithoutLast still remain the empty list.

This is not good.

I was thinking to implement it doing the following operation:

1. Count the number of element in the list before call the predicate that delete the last element.
2. Iterate by recursion and decrement the value of the number of element each time
3. If it is true that the number of element is 0 it means that this is the last element so I delete it from the original list

But this seems to me not clear and not so good, I would know if there is a declarative good solution for this problem.

回答1:

To prevent the creation of useless choicepoints, use lagging to benefit from first argument indexing:

list_butlast([X|Xs], Ys) :-                 % use auxiliary predicate ...
   list_butlast_prev(Xs, Ys, X).            % ... which lags behind by one item

list_butlast_prev([], [], _).
list_butlast_prev([X1|Xs], [X0|Ys], X0) :-  
   list_butlast_prev(Xs, Ys, X1).           % lag behind by one

Sample queries:

?- list_butlast([], Xs).
false.

?- list_butlast([1], Xs).
Xs = [].                                    % succeeds deterministically

?- list_butlast([1,2], Xs).
Xs = [1].                                   % succeeds deterministically

?- list_butlast([1,2,3], Xs).
Xs = [1,2].                                 % succeeds deterministically

How about the other direction?

?- list_butlast(Xs, []).
Xs = [_A].

?- list_butlast(Xs, [1,2,3]).
Xs = [1,2,3,_A].

What about the most general query?

?- list_butlast(Xs, Ys).
   Xs = [_A]            , Ys = []
;  Xs = [_A,_B]         , Ys = [_A]
;  Xs = [_A,_B,_C]      , Ys = [_A,_B]
;  Xs = [_A,_B,_C,_D]   , Ys = [_A,_B,_C]
;  Xs = [_A,_B,_C,_D,_E], Ys = [_A,_B,_C,_D]
⋯

回答2:

I find your analysis a bit overly complex. Let's start from the base case:

without_last([_], []).

When you are at the last element, the result should be the empty list.

The inductive case must therefore be the case where we are not at the last element. In the case where I have some element attached to an arbitrarily long list, that list without the last element is just the tail of the list without the last element with the current element on front. Or:

without_last([X|Xs], [X|WithoutLast]) :- 
    without_last(Xs, WithoutLast).

This works in every direction.

?- without_last([1,2,3,4], X).
X = [1, 2, 3] ;
false.

?- without_last([1,2], X).
X = [1] .

?- without_last([1], X).
X = [] ;
false.

?- without_last([], X).
false.

?- without_last(X, [1,2,3]).
X = [1, 2, 3, _G294].

?- without_last([1,2,3,4], [1,2,3]).
true.

?- without_last([1,2,3,X], [1,2,3]).
true.

回答3:

If you develop a recursive procedure, which goes through every element of the input list, your base case would stop when you find the last element unifying the resulting list with the empty list. Then, returning from the recursive call you just add every other item to the resulting list:

Without using the cut:

deleteLastElement([_], []).
deleteLastElement([Head, Next|Tail], [Head|NTail]):-
  deleteLastElement([Next|Tail], NTail).

The first clause (base case) unifies the second argument with the empty list when there is only one element in the first argument list.

The second clause states that when the first argument is a list with at least two elements, then you recursively call itself (without the head), an add the Head to the second argument returned by that call.

In fact you don't need to make explicit in the second clause that the list needs to have at least two elements,

deleteLastElement([Head|Tail], [Head|NTail]):-
  deleteLastElement(Tail, NTail).

And, of course, you could also have used append/3 to remove the last item from a list:

append(WithoutLast, [_], List).

回答4:

@repeat's implementation is certainly the most efficient one with current Prolog processors, still I like to use DCGs for this purpose - secretly hoping that one day implementation technology will be good enough to run this with comparable (space) efficiency.

list_butlast(Xs, Ys) :-
   phrase( ( seq(Ys), [_] ), Xs).

seq([]) -->
   [].
seq([E|Es]) -->
   [E],
   seq(Es).