试图理解递归prolog过程



这是教授讲座中的一个例子:

append([ ], A, A).
append([A|B], C, [A|D]) :- append(B,C,D).
Build a list:
?- append([a],[b],Y).
Y = [ a,b ]
Break a list into constituent parts:
?- append(X,[b],[a,b]).
X = [ a ]
?- append([a],Y,[a,b]).
Y = [ b ]

我花了三个小时试图抓住它,但我做不到。在这张幻灯片之前的任何序言概念都没有遇到任何问题。没有提供进一步的解释,也没有其他信息。这就是全部。如果有人能告诉我这个过程是如何运作的,我会爱他们,直到死亡把我们分开。

首先要理解的是:-运算符。

this_will_be_true :- if_this_is_true

基本上,:-右边的任何东西都是先决条件。一个很好的例子是:

sibling(X, Y) :- parent_child(Z, X), parent_child(Z, Y).

这基本上意味着,如果存在父母Z,那么X和Y是兄弟姐妹,Z是X和Y的父母。

append([ ], A, A).

这一行基本上意味着将某个东西附加到空列表中会返回某个东西。这是递归的基本情况。

append([A|B], C, [A|D]) :- append(B,C,D).

这一行的意思是,将C附加到具有A和B的现有列表会返回具有A和D的列表,假定将C附加在B会返回D。

Build a list:
?- append([a],[b],Y).
Y = [ a,b ]

因此,在给定两个初始值的情况下,Prolog返回Y的唯一可能值,该值满足这两个规则。让我们想想这是怎么发生的。这需要首先通过第二条规则进行评估。所以[A|B]就是[a]C就是[b]

所以对于[A|B],我们必须回到第一条规则,因为B是空列表(它是[ ])。第一条规则基本上说,我们可以把[a]写成[a|[ ]],它们是一样的。现在我们可以回到第二条规则。AaB[ ]C[b]

现在让我们检查append(B, C, D)的前提条件。这是append([ ], [b], D)。再次使用第一条规则,我们可以看到D也是[b]

因此,根据第二个规则定义,Y就是[A|D]。既然我们知道D就是[b],我们就知道Y就是[a, b]

我只做其中一个,因为它们基本上是一样的。

?- append(X,[b],[a,b]).
X = [ a ]

因此,在这里,Prolog将返回X的唯一可能值,以便该语句返回true。让我们来看看第二条规则。所以我们知道[a, b]就是[A|D]。这意味着Aa,而D[b]。我们还知道C就是[b]。所以现在,我们需要看看先决条件来弄清楚B是什么。append(B, C, D)翻译成append(B, [b], [b])。现在,使用第一条规则,我们知道B必须是[ ]。所以现在我们知道[A|B]就是[a|[ ]],和[a]是一样的。因此,X必须是[a]

我希望这是一个足够详细的解释。

以下是我自己的理解。

您的代码描述了List的追加操作。

首先,这里有一个缩写,可以帮助您理解序言中的列表以及|:的含义

[X1|[...[Xn|[]] = [X1,...Xn]

append(A,B,C)意味着将列表B附加到C中的A结果上

将A附加到空列表会导致A:

append([ ], A, A).

如果要将Y附加到X,请说append(X,Y,_)。除非X是[],否则prolog不会知道该做什么。你必须告诉prolog规则:

append([A|B], C, [A|D]) := append(B, C, D)

然后prolog将尝试将X拆分为形式[A|B]。那么Y将是A|D,其中D是C定义的列表,附加到B。append(B, C, D)是我们告诉prolog这个事实的方式。

最新更新