Prolog: Checking if something is the last item in the list?

Question

I am new to prolog and am basically trying to write a clause that would evaluate as true if a given item is the last item in a given list. Here is what I have:

last(X,[Y|X]).
last(X,[Y|Z]) :- last(X,Z).

I thought this would do the trick, but when I ask prolog:

?- last(c,[a,b,c]).

Prolog returns false. I tried the following query to see what Prolog thinks should fit my definition of last:

?- last(c,X).
X = [_G530|c] ;
X = [_G530, _G533|c] ;
X = [_G530, _G533, _G536|c]

So, what I am not sure about is why the "|" symbol is still in the list?

Update: last([c],[a,b,c]) produces the desired behavior. However, I'm not sure why my 1st argument has to be a list?

traitor · Answer 1 · 2014-02-11T07:48:48.390

You might want this:

 last(X,[X]).
 last(X,[_|Z]) :- last(X,Z).

The | denotes a 'tail' or 'the rest of the list.'

With ?- last(c,X). Prolog produces lists (according to your first definition) that have c as the last item.

When you query ?- last(c,[a,b,c])., it returns false because you haven't defined a case for a list of only one item [X] or [X|[]]. So it fails when list is shorter than two items.

However, last([c],[a,b,c]) succeeds because you get [b|_29] or whatever denoting that the tail part might be any list. So it '_29' can be '[c]', satisfying the first definition like last([c],[b|[c]]). Remember that a nonempty list in Prolog is actually a pair of the first list item (head) and a list of the rest (tail). Usually written as [head|tail].

best to avoid singletons: `last(X,[_|Z]) :- last(X,Z).` – CapelliC Feb 11 '14 at 07:12 — CapelliC, Feb 11 '14 at 07:12
True. Especially when warnings might confuse a beginner. – traitor Feb 11 '14 at 07:14 — traitor, Feb 11 '14 at 07:14

score 3 · Answer 2 · answered Feb 11 '14 at 10:02

3

Why not view things from a grammatical viewpoint. So what is the last element in a list?

last(X, Xs) :-
   phrase( ( ..., [X] ), Xs).

... --> [] | [_], ... . % any sequence

answered Feb 11 '14 at 10:02

false

10,264
13
101
209

I get `2 ?- last(X, [1,2,3]).
X = 3 ;
false.`. Is this to be expected? – Will Ness Feb 11 '14 at 11:15
hmm. I expected it should be deterministic, but now that I try, I can't make it so without using a cut - `last(X,[_|B]):- B=[_|_],!, last(X,B).`, `last(X,[X]):- !.`. this is unexpected. – Will Ness Feb 11 '14 at 14:33
1

@WillNess: Let's not confuse logical determinism with a concrete performance feature. With ! as you indicate, you are sacrificing logical completeness for "performance". `last(X,[X|Xs])` should succeed for infinitely many answers. – false Feb 11 '14 at 14:40
@WillNess: Clever usage of ! might be possible, but it is a nightmare, and definitely not worth the effort. After all: There is a single choice point that is superfluous. It would be something else if there would be as many choicepoints as elements in the list. That would be serious, indeed. The Prolog convention to put the recursive rule last avoids that sometimes. – false Feb 11 '14 at 14:50
A perfect implementation is in: It does not use *any* cuts and avoids the superflous choice point. http://stackoverflow.com/questions/11734986/implementing-last-in-prolog – false Feb 11 '14 at 14:56

Dylon Dickinson · Answer 3 · 2018-11-03T06:35:56.810

3

Why not just use append?

last(X,Y) :-
    append(_,[X],Y).

http://www.swi-prolog.org/pldoc/man?predicate=append/3

edited Nov 03 '18 at 06:35

answered Nov 03 '18 at 06:30

Dylon Dickinson

31
2

score 2 · Answer 4 · edited May 23 '17 at 12:34

Because the tail of a list is a list itself.

A list in Prolog can be seen as [H | T], where H is the first element (the head), and T (the tail) is a list of all other elements.

Your list [a, b, c] is actually [a | [b | [c | [] ] ] ] when you decompose it (the last tail is always an empty list):

List: [a, b, c]   Head: a   Tail: [b, c]
List: [b, c]      Head: b   Tail: [c]
List: [c]         Head: c   Tail: []

So when you get to the point where you're asking if last(c, [b, c]), that decomposes to last(c, [b|[c]]), which is why the first clause can't be instantiated, because X can't be both c and [c]. That is why it did work when you asked last([c],[a,b,c]).

The version proposed by alpha works, because it takes this into account:

% A list ends with an element if contains exactly that element.
last(X,[X]).

% A list ends with an element if its tail ends with that element.
% (Since we don't care about the head, we use an underscore).
last(X,[_|T]) :- last(X,T).

score 0 · Answer 5 · edited Jan 28 '22 at 13:06

0

Pic of Question

(a) using concatenation,

conc(_,[Item],List)

(b) Using without concatenation,

Last([Item],[Item]) :- Last(Item,[H|T]) , Last(Item,T)

edited Jan 28 '22 at 13:06

ouflak

2,458
10
44
49

answered Jan 28 '22 at 05:43

praveen bhawantha

21
4

Prolog: Checking if something is the last item in the list?

5 Answers5