Am I allowed to use variables in my facts / rules?

user_7805710 0
Viewed 47

I'm working through the first problem in a famous collection of 99 Prolog problems. Here is the question:

Find the last element of a list. Example: ?- my_last(X,[a,b,c,d]). X = d

and here is my file of facts and rules:

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

and my query:

my_last(X, [a,b,c,d]).

My output is true, but I want my output to be the value of the variable X when the computer gets to the point that evaluates to true. I used trace, and I think the program works much as I expected it to. Basically, it runs through my_last(a, [b, c, d]) and so on until my_last(d, []), then evaluates to true and starts backing out of the recursion. But it still only evaluates to true! Why is this happening? Is it because I have variables in my facts/rules?

prolog
1 Answers

It is giving you just true because at the end there are no bindings performed.

The head of your second clause has an anonymous variable as the first argument, there is no instantiation of X in my_last(X, [a,b,c,d]).

You may rewrite your procedure to unify it with the last element of the list in the first clause, then chain it back all the way through the recursive step (second clause):

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

Sample run:

?- my_last(X, [a,b,c,d]).
X = d ;
false.

Note the choice point left in this program which eventually will fail upon backtracking for further solutions.

You may improve this program by letting first argument indexing kick in by rewriting the procedure like this:

my_last(X, [H|T]):-
  my_last(T, H, X).
  
my_last([], X, X).
my_last([H|T], _, X):-
  my_last(T, H, X).

which now gives us:

?- my_last(X, [a,b,c,d]).
X = d.
user_4632430
Related