I have a problem solving the difference list problem with paper-pencil not by the helping of SWI Prolog ( in these days i am preparing my logic programming exam).
Here is the question:
q(X) :- p(X - []).
p([X|Y] - Y).
p([X|Y] - Z) :- p(Y - [X|Z]).
Explicitly give the set of all ground terms t for which the query ?- q(t). succeeds. State a formal definition of the set in closed form (i.e., do not use a recursive definition).
Answer is :
{[t1, . . . , tn−1, tn, tn−1, . . . , t1] | n > 0, ti is a ground term for all i ∈ {1, . . . , n}}
I used [1,2,3,2,1] and it gave me true as an expected answer.
I could not understand what the steps are in order to solve this?
Let t = [t1,t2,t3, ... , tn] be a list.
q(t). will succeed if p(t - []). succeeds.
p(t - []). succeeds if p([t2,t3,...,tn] - [t1]). succeeds (third rule).
p([t2,t3,...,tn] - [t1]). succeeds if p([t3,...,tn] - [t2,t1]) succeeds, etc.
This will actually only end up succeeding if at one point the second rule gets applied (otherwise we will end up calling p([] - _). which does not match any rule available), that is if we have p([ti,ti+1,...,tn] - [ti+1,...,tn])..
The second list [ti+1,...,tn] is actually [ti-1,ti-2,...,t2,t1] according to the way it is constructed in the third rule.
Therefore q(t). succeeds iff ti-1 = ti+1, ti-2 = ti+2, ..., t2 = tn-1, t1 = tn, which means t = [t1,t2,...,ti-1,ti,ti-1,...,t2,t1].