序言； if 和（停止）递归

Question

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

我定义了一条规则：

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

检查“Item”是否在列表 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|**]. 

我是否对此想得太迫切了？

Answer 1

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

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

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

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

filter_doubles([], []).

然后，如果 Item 出现在列表的 Rest 中，则您会在列表的 Rest 上重复出现，并删除该出现的 项目。

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).

请注意，当您尝试使用 Result = [Ah|Result] 等表达式执行累加时，Prolog 会创建一个无限递归的数据结构：Result 与列表统一以Ah为头，Result为尾，统一为Ah为头，Result为列表tail，它统一为一个以 Ah 为头、以 Result 为尾的列表，依此类推。

Answer 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 中，in 的含义是“将 Result 与以 Result 作为第二个参数的术语统一”，该术语要么失败（与发生检查统一），要么产生“有理数”树”（在大多数 Prolog 中带有循环的图形结构）。

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

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