Rule matching regarding lists in SWI Prolog

Question

Recently I started learning Prolog and as an exercise I tried to implement a predicate penultimate/2 giving the penultimate element of a list that would not backtrack.

This problem is trivial when one use cuts, but I tried to implement a predicate in a similar way to SWI-Prolog implementation of last/2 predicate that would not use cuts:

penultimate([X1, X2 | Rest], Elem) :-
  penultimate_([X1, X2 | Rest], X1, X2, Elem).

penultimate_([], X1, _, X1).
penultimate_([_], _, X2, X2).
penultimate_([X1, X2 | Rest], _, _, Penultimate) :-
  penultimate_(Rest, X1, X2, Penultimate).

This code works as expected when the length of the list is even, but when fed with a list of odd length, I get the following result:

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

The only reason why this happens that I can come up with is that the SWI-Prolog matching system treats the rule in my program as a possibility for matching against a one-element list even though the list in the rule head requires at least 2 elements. Is this correct?

Paulo Moura Paulo Moura · Accepted Answer · 2019-08-13T07:25:12

Try:

penultimate([X1, X2 | Rest], Penultimate) :-
    penultimate(Rest, X1, X2, Penultimate).

penultimate([], Penultimate, _, Penultimate).
penultimate([X3| Rest], _, X2, Penultimate) :-
    penultimate([X2, X3| Rest], Penultimate).

Sample calls:

| ?- penultimate([1,2,3,4,5], P).

P = 4

yes
| ?- penultimate([1,2,3,4], P).  

P = 3

yes
| ?- penultimate([1,2,3], P).  

P = 2

yes
| ?- penultimate([1,2], P).  

P = 1

yes
| ?- penultimate([1], P).  

no

Indexing on most Prolog systems can distinguish between an empty list (an atom) or a non-empty list (a compound term) but usually would not perform deep-indexing in a list.

Rule matching regarding lists in SWI Prolog

1 Answers