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

list, prolog

Solution

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

Problem

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: - Count the number of element in the list before call the predicate that delete the last element. - Iterate by recursion and decrement the value of the number of element each time - 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.

Original source