2

为了更好地理解序言、列表和递归作为一个整体，我正在完成分配给自己的各种简单任务。其中包括从列表中删除重复条目。

我定义了一个规则：

is_on(Item, [Ah|At]) :- Ah = Item; is_on(Item, At).

这将检查“项目”是否在列表 X 上。所以我想我可以扩展它来定义一个 filter_double 谓词：

filter_doubles([Ah|At], Result) :-
    (not(is_on(Ah, At)) ->
        Result = [Ah|Result]
    ;
        filter_doubles(At, Result)
    ).

这对我来说非常有意义：如果 Ah 没有出现在列表的其余部分（它的尾部）中，则使用列表构造将 a 添加到结果的前面，否则递归列表的其余部分。显然Prolog不这么认为：

47 ?- filter_doubles([1,2,3,3,4,2,1,1], Z).
Z = [3|**].

我在这方面想得太迫切了吗？

4

2 回答 2

3

在逻辑编程中，谓词中的递归通常使用多个规则来处理。第一条规则描述了递归基本情况，即它的停止条件；其他规则，或者可能只是第二个规则，描述了递归步骤。

因此，您的is_on规则（我已重命名contains）通常以以下方式编写：

contains(Item, [Item | _]).
contains(Item, [_ | Tail]) :- contains(Item, Tail).

filter_double谓词可能会经历类似的重写。首先，一个空列表将对应一个空结果。

filter_doubles([], []).

然后，如果Item出现在Rest列表中，则在列表中重复Rest，删除出现的Item。

filter_doubles([Item | Rest], Result) :-
    contains(Item, Rest), !,
    filter_doubles(Rest, Result).

最后，如果列表Item中没有出现Rest（因为前面的规则已经检查了这种情况），您可以Item使用列表构造将其放在结果的前面，然后继续过滤Rest列表的.

filter_doubles([Item | Rest], [Item | Tail]) :- filter_doubles(Rest, Tail).

Please note that when you attempt to perform accumulation with an expression such as Result = [Ah|Result], Prolog creates an infinitely recursive data structure: Result is unified with a list having Ah as head and Result as tail, which is unified with a list having Ah as head and Result as tail, which is unified with a list having Ah as head and Result as tail, and so on, and so on, and so on.

于 2011-03-07T10:05:37.647 回答
2

您需要在两个分支中进行递归，并且需要一个基本案例：

filter_doubles([], []).
filter_doubles([X|L], Result) :-
    (memberchk(X,L) ->
        filter_doubles(L, Result)
    ;
        filter_doubles(L, Result0),
        Result = [X|Result0]
    ).

Result = [Ah|Result]确实似乎是命令式思维的一个例子。Prolog 中的意思是“Result与具有Result作为其第二个参数的术语统一”，它要么失败（与发生检查统一）要么产生“有理树”（在大多数 Prolog 中具有循环的图结构）。

练习：使我发布的代码尾递归。

请注意，这将删除每个项目的最后一次出现之外的所有内容。

于 2011-03-07T09:55:24.577 回答