Пролог Напишите полное дерево поиска для запроса

Question

Поэтому для моего класса меня попросили написать целое дерево поиска для запроса ниже. Мне дали пример листа, однако, честно говоря, мои глаза смотрят на него. Может кто-нибудь шаг за шагом проведет меня через процесс и объяснит мне как можно лучше.

Это то, что мне дали:

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

И запрос

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

Answer 1

Чтобы создать дерево поиска, вы начинаете с запроса и перебираете предложения, выдавая себя за переводчика Prolog. Блоки в дереве представляют следующее предложение, которое нужно выполнить, а "ветви" дерева - это то, какие переменные создаются. Если этот случай сложный, начните с очень простого случая, чтобы получить представление. В Интернете есть несколько примеров.

Вот только один путь через дерево, и я оставлю его в качестве упражнения для заполнения остальных:

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

{Результат из первого соответствующего предложения: p([], _). }

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

{Результаты сопоставления второго q пункт, q(X, [_|T]), Первый q предложение не соответствует}

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

{Результаты сопоставления второго q пункт}

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

{Результаты сопоставления второго q пункт}

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

{Соответствует первому q пункт q(X, X). }

   |
   SUCCESS (X = [])

Есть еще одна ветвь в первом предложении, которая соответствует второму p предложение вместо первого:

?- 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)