序言:delete/3 是如何工作的? [英] Prolog: How does delete/3 works?

问题描述

肯定所有 Prolog 粉丝都听说过 delete 或 remove 谓词.

for sure all Prolog fans heard about the delete or remove predicate.

del(X,[X|Tail],Tail).
del(X,[H|Old],[H|New]) :- del(X,Old,New).

我无法理解发生了什么.如果列表中的第一个元素是搜索元素，则将使用第一行.然后列表将在 Head (X) 中被剪切，Tail 和 Tail 就是结果.但是在哪一点上第一个 X 将与 X|Tail 中的 X 进行比较?在第二行，我什至不明白，X和H什么时候比较，如果X = H?

I have problems to understand whats going on. The first row will be used, if the first element in the list is the searched element. Then the list will be cut in Head (X) and the Tail and Tail is the result. But at which point the first X will be compared with the X from the X|Tail? At the second row, i even don't understand, when the X and H will be compared, if X = H?

我希望有人能告诉 Prolog 初学者.

I hope someone can tell that for a Prolog beginner.

推荐答案

首先我们要注意，这个定义实现了一种非常特殊的删除元素的意义:del(Element, List, Rest) 只成功如果 Element 确实出现在 List 中，否则失败:

First let's note that this definition implements a very particular sense of deleting an element: del(Element, List, Rest) only succeeds if the Element actually appears in the List, otherwise it fails:

?- del(a, [a, b, c], Rest).
Rest = [b, c] ;
false.

?- del(x, [a, b, c], Rest).
false.

这会很重要.

但在哪一点上第一个 X 将与 X|Tail 中的 X 进行比较?

But at which point the first X will be compared with the X from the X|Tail?

X 在子句的头部出现两次，并且这两次出现必须统一.你可以阅读

X occurs twice in the head of the clause, and these two occurrences must unify. You could read

del(X, [X | Tail], Tail).

类似于:

del(X1, [X2 | Tail], Tail) :-
    X1 = X2.

所以比较"X 对自身的引用隐含在它在不同参数中多次出现的事实中.该子句不会匹配像 del(a, [b | Xs], Ys) 这样的目标，例如:Prolog 必须将第一次出现的 X 与 统一>a 和 X 与 b 的第二次出现，这是不可能的.因此，如果感兴趣的元素与列表的第一个元素不统一，则不能应用第一个子句.第二个条款必须适用.

So the "comparison" of X against itself is implicit in the fact that it occurs multiple times in different arguments. This clause will not match a goal like del(a, [b | Xs], Ys) for example: Prolog would have to unify the first occurrence of X with a and the second occurrence of X with b, and this is not possible. So if the element of interest is not unifiable with the first element of the list, the first clause cannot apply. The second clause must apply.

然而，如果元素确实与列表的第一个元素统一，那么剩下的列表就是Tail，即，如果第一个子句成功，然后它从给定的列表中删除一个匹配项.

If, however, the element does unify with the first element of the list, then the remaining list is just the Tail, i.e., if the first clause succeeds, then it deletes exactly one occurrence from the list it is given.

在第二行，我什至不明白，如果 X = H，什么时候会比较 X 和 H?

At the second row, i even don't understand, when the X and H will be compared, if X = H?

它们不会被比较！X 是否可以与 H 统一与这个子句无关.如果这个子句成功，那么列表的第一个元素将被保留，无论它是否等于X.然而，这是一个递归子句.只有当某个递归调用最终以成功的非递归子句结束时，它才能成功.唯一的非递归子句是第一个子句，我们知道它会删除一次出现的 X.所以第二个子句不需要关心它查看的列表元素，因为它的作用是保留所有未删除的元素.实际删除是第一个子句的作用.

They will not be compared! It doesn't matter to this clause whether X is unifiable with H or not. If this clause succeeds, then the first element of the list will be preserved, no matter if it is equal to X or not. However, this is a recursive clause. It can only succeed if some recursive call eventually ends in a non-recursive clause that succeeds. The only non-recursive clause is the first one, for which we know that it will delete exactly one occurrence of X. So the second clause doesn't need to care about the list element it looks at, because its role is to preserve all the non-deleted elements. Actual deletion is the role of the first clause.

然而，这种不关心元素的方法只有在第一个子句 will 成功时才会成功，只有当列表的其余部分包含可以删除的元素时才会出现这种情况.如果不是，则整个递归调用失败.这就是为什么要删除的元素必须存在于原始列表中这一有点不直观的行为的原因.

However, this not caring about the element only succeeds if the first clause will succeed, which is only the case if the rest of the list contains an element that can be deleted. If it does not, the entire recursive call fails. This is the reason for the somewhat unintuitive behavior that the element to be deleted must be present in the original list.

这篇关于序言:delete/3 是如何工作的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！