了解 Prolog 列表 [英] Understanding Prolog Lists

问题描述

我正在尝试了解 Prolog 列表，以及如何在递归函数结束时返回"/实例化值.

I am trying to understand Prolog lists, and how values are 'returned' / instantiated at the end of a recursive function.

我正在看这个简单的例子:

I am looking at this simple example:

val_and_remainder(X,[X|Xs],Xs).
val_and_remainder(X,[Y|Ys],[Y|R]) :-
   val_and_remainder(X,Ys,R).

如果我调用 val_and_remainder(X, [1,2,3], R). 那么我将得到以下输出:

If I call val_and_remainder(X, [1,2,3], R). then I will get the following outputs:

X = 1, R = [2,3]; 
X = 2, R = [1,3];
X = 3, R = [1,2];
false.

但我很困惑为什么在基本情况下 (val_and_remainder(X,[X|Xs],Xs).) Xs 必须像它一样出现.

But I am confused as to why in the base case (val_and_remainder(X,[X|Xs],Xs).) Xs has to appear as it does.

如果我要调用 val_and_remainder(2, [1,2,3], R). 那么在我看来它会像这样运行整个程序:

If I was to call val_and_remainder(2, [1,2,3], R). then it seems to me as though it would run through the program as:

% Initial call
val_and_remainder(2, [1,2,3], R).

val_and_remainder(2, [1|[2,3]], [1|R]) :- val_and_remainder(2, [2,3], R).

% Hits base case
val_and_remainder(2, [2|[3]], [3]).

如果上述运行是正确的，那么它如何获得 R 的正确值?在上面的例子中，R 的值应该是 R = [1,3].

If the above run through is correct then how does it get the correct value for R? As in the above case the value of R should be R = [1,3].

推荐答案

在 Prolog 中，您需要将 谓词 视为函数，而不像通常在其他语言中那样.谓词描述可能包含有助于定义该关系的参数的关系.

In Prolog, you need to think of predicates not as functions as you would normally in other languages. Predicates describe relationships which might include arguments that help define that relationship.

以这个简单的案例为例:

For example, let's take this simple case:

same_term(X, X).

这是一个谓词，用于定义两个参数之间的关系.unification 是说如果第一个和第二个参数是统一的，那么它们是相同的(这个定义取决于我们，谓词的作者).因此，same_term(a, a) 会成功，same_term(a, b) 会失败，而 same_term(a, X) 会成功X = a.

This is a predicate that defines a relationship between two arguments. Through unification it is saying that the first and second arguments are the same if they are unified (and that definition is up to us, the writers of the predicate). Thus, same_term(a, a) will succeed, same_term(a, b) will fail, and same_term(a, X) will succeed with X = a.

你也可以用更明确的形式来写:

You could also write this in a more explicit form:

same_term(X, Y) :-
    X = Y.  % X and Y are the same if they are unified

现在让我们看看您的示例，val_and_remainder/3.首先，它是什么意思?

Now let's look at your example, val_and_remainder/3. First, what does it mean?

val_and_remainder(X, List, Rest)

这意味着 X 是 List 的一个元素，Rest 是一个由所有其余元素组成的列表(没有 <代码>X).(注意:您没有立即解释此含义，但我正在根据您的示例的实现来确定此含义.)

This means that X is an element of List and Rest is a list consisting of all of the rest of the elements (without X). (NOTE: You didn't explain this meaning right off, but I'm determining this meaning from the implementation your example.)

现在我们可以写出来描述规则了.首先，一个简单的基本情况:

Now we can write out to describe the rules. First, a simple base case:

val_and_remainder(X,[X|Xs],Xs).

这说明:

Xs 是列表 [X|Xs] 没有 X 的剩余部分.

Xs is the remainder of list [X|Xs] without X.

根据 Prolog 中列表的 [X|Xs] 语法定义，该语句应该非常明显.您需要所有这些参数，因为第三个参数 Xs 必须与列表 [X|Xs] 的尾部(其余部分)统一，后者也是 Xs(根据定义，同名变量是统一的).和以前一样，您可以更详细地将其写成:

This statement should be pretty obvious by the definition of the [X|Xs] syntax for a list in Prolog. You need all of these arguments because the third argument Xs must unify with the tail (rest) of list [X|Xs], which is then also Xs (variables of the same name are, by definition, unified). As before, you could write this out in more detail as:

val_and_remainder(X, [H|T], R) :-
    X = H,
    R = T.

但其实简写更清晰.

现在递归子句说:

val_and_remainder(X, [Y|Ys], [Y|R]) :- 
    val_and_remainder(X, Ys, R).

所以这意味着:

[Y|R] 是列表 [Y|Ys] 的剩余部分，没有 X if R 是列表 Ys 的剩余部分，没有元素 X.

[Y|R] is the remainder of list [Y|Ys] without X if R is the remainder of list Ys without the element X.

您需要考虑该规则以说服自己它在逻辑上是正确的.Y 在第二个和第三个参数中是相同的，因为它们指的是同一个元素，所以它们必须统一.

You need to think about that rule to convince yourself that it is logically true. The Y is the same in second and third arguments because they are referring to the same element, so they must unify.

因此，这两个谓词子句形成了涵盖这两种情况的两条规则.第一种情况是 X 是列表的第一个元素的简单情况.第二种情况是 X 不是第一个元素时的递归定义.

So these two predicate clauses form two rules that cover both cases. The first case is the simple case where X is the first element of the list. The second case is a recursive definition for when X is not the first element.

当您进行查询时，例如 val_and_remainder(2, [1,2,3], R). Prolog 会查看它是否可以统一该术语val_and_remainder(2, [1,2,3], R) 带有一个事实或一个谓词子句的头部.它尝试与 val_and_remainder(X,[X|Xs],Xs) 统一失败，因为它需要将 X 与 2 统一，这意味着它需要将 [1,2,3] 与 [2|Xs] 统一起来，因为 [1,2,2,3] 是 1，但是 [2|Xs] 的第一个元素是 2.

When you make a query, such as val_and_remainder(2, [1,2,3], R). Prolog looks to see if it can unify the term val_and_remainder(2, [1,2,3], R) with a fact or the head of one of your predicate clauses. It fails in its attempt to unify with val_and_remainder(X,[X|Xs],Xs) because it would need to unify X with 2, which means it would need to unify [1,2,3] with [2|Xs] which fails since the first element of [1,2,3] is 1, but the first element of [2|Xs] is 2.

所以 Prolog 继续前进并成功地统一了 val_and_remainder(2, [1,2,3], R) 和 val_and_remainder(X,[Y|Ys],[Y|R]) 通过将 X 与 2、Y 与 1、Ys 与 [2,3] 统一起来, 和 R 与 [Y|R] (注意，这很重要，您调用中的 R 变量与 <谓词定义中的 code>R 变量，因此我们应该将其命名为 R1 以避免这种混淆).我们将您的 R 命名为 R1 并说 R1 与 [Y|R] 是统一的.

So Prolog moves on and successfully unifies val_and_remainder(2, [1,2,3], R) with val_and_remainder(X,[Y|Ys],[Y|R]) by unifying X with 2, Y with 1, Ys with [2,3], and R with [Y|R] (NOTE, this is important, the R variable in your call is NOT the same as the R variable in the predicate definition, so we should name this R1 to avoid that confusion). We'll name your R as R1 and say that R1 is unified with [Y|R].

当第二个子句的主体被执行时，它调用val_and_remainder(X,Ys,R).，或者换句话说，val_and_remainder(2, [2,3],R).现在这将与第一个子句统一起来，并为您提供 R = [3].当你展开所有这些时，你会得到，R1 = [Y|[3]]，并且回想一下 Y 被绑定到 1，结果是 R1= [1,3].

When the body of the second clause is executed, it calls val_and_remainder(X,Ys,R). or, in other words, val_and_remainder(2, [2,3], R). This will unify now with the first clause and give you R = [3]. When you unwind all of that, you get, R1 = [Y|[3]], and recalling that Y was bound to 1, the result is R1 = [1,3].

这篇关于了解 Prolog 列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！