prolog - Prolog 为一个查询写一个完整的搜索树

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)