How to delete the last element from a list in Prolog?

Question

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.

Answer 1

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.

Answer 2

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