Geek asks and answers

How to remove the last item from a list in Prolog?

I am in the following situation: I have a list, and I should remove only the last item from it.

I implement the following rule (this does not work):

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

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

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

Looking at the trail, I think this is understandable, 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 list Without list is unified with the empty list [], and when the reverse tracking is performed, Without Lust remain empty.

This is not good.

I thought to implement it by doing the following operation:

  • Count the number of items in a list before calling a predicate that removes the last item.
  • , 0, , ,

, , .

+5
4

, , :

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

:

?- list_butlast([], _).
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

?

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

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

?

?- 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]
...
+6

. :

without_last([_], []).

, .

, . , , , - . :

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

.

?- 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.
+10

, , , , . , , :

:

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

( ) , .

, , , ( ), Head , .

, ,

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

, , append/3 :

append(WithoutLast, [_], List).
+7

The @repeat implementation is by far the most efficient with current Prolog processors, but I still prefer to use DCG for this purpose - secretly hoping that one day the implementation technology will be good enough to run with comparable (spatial) efficiency.

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

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

More articles:


All Articles