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)