Deterministically finding last element of a list in Prolog

user_1646086 0
Viewed 37

Finding the last element of a list in Prolog seems to be straightforward

my_last([A], A).
my_last([_,A|T], E) :-
    my_last([A|T], E).

Unfortunately, this predicate is non-deterministic, no matter how "instantiated" the actual parameters are.

?- my_last([1,2,3], 3).
true ;
false.

Looking at the implementation of the nth0/3 here https://github.com/mthom/scryer-prolog/blob/master/src/lib/lists.pl, there's a "trick" to guard the actual predicates with integer(N) -> which acts like a preprocessor and splits the predicate into a deterministic and a non-deterministic branches.

So how do I define such preprocessor conditions for my_last/2, in order to make it deterministic for the case where the tail of the list is not a variable? Can it be done efficiently?

prolog
1 Answers

Can see swi-prolog's code:

?- listing(last).
lists:last([X|Xs], Last) :-
    last_(Xs, X, Last).

?- listing(last_).
lists:last_([], Last, Last).
lists:last_([X|Xs], _, Last) :-
    last_(Xs, X, Last).

This is using empty list [] vs head-and-tail [Head|Tail] distinction in the first argument, to be deterministic. More info at Determining if a list is empty or not

user_176283360
Related