Prolog Write an entire search tree for a query

Question

So for my class I'm asked to write an entire search tree for the query below. I have been given an example sheet however to be honest my eyes glaze over looking at it. Can someone walk me through the process step by step and explain it to me as best you can much appreciated.

This is what I'm given:

p([], _). 
p([H|T], [H|T2]) :- p(T, T2). 
q(X, X). 
q(X, [_|T]) :- q(X, T).

And the query

 p(X, [a,b,c]), q(X, [a,b,c])

Answer 1

To create a search tree you start with your query and step through your clauses pretending to be the Prolog interpreter. The blocks in the tree represent the next clause to execute, and the "legs" of the tree are what variable instantiations are occurring. If this case is complex, start with a very simple case to get the idea. There are several examples online.

Here's just one path through the tree and I'll leave it as an exercise to fill in the rest:

?- p(X, [a,b,c]), q(X, [a,b,c])
   |
   | X = []

{ Result from the first matched clause: p([], _). }

   |
   q([], [a,b,c])   % `p` clause succeeded, moving on to `q` in the query
   |
   | [] = X, [a,b,c] = [_|T] (so T = [b,c])

{ Results from matching second q clause, q(X, [_|T]). First q clause did not match }

   |
   q([], [b,c])
   |
   | [] = X, [b,c] = [_|T] (so T = [c])

{ Results from matching second q clause }

   |
   q([], [c])
   |
   | [] = X, [c] = [_|T] (so T = [])

{ Results from matching second q clause }

   |
   q([], [])
   |
   | [] = X

{ Matches first q clause q(X, X). }

   |
   SUCCESS (X = [])

There's another branch off of the first clause to be followed, which corresponds to matching the second p clause instead of the first:

?- p(X, [a,b,c]), q(X, [a,b,c])
   |             \
   | X = []       \ X = [H|T] [a,b,c] = [H|T2] (H = a and T2 = [b,c])
   |               \  p([a|T], [a|[b,c]])   % matches second `p` clause  
   ...              \
   (first p match    ... (continue)
    shown above)