前言;如果和(停止)递归 [英] Prolog; if and (stopping) recursion

问题描述

为了更好地理解序言，列表和递归，我正在逐步完成分配给自己的各种简单任务. 除其他外，还有从列表中删除重复条目.

In trying to better understand prolog, lists and recursion as a whole I'm working my way through various simple tasks I've assigned to myself. Among others is removing double entries from a list.

我已经定义了一条规则:

I've defined a rule:

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

这将检查'Item'是否在列表X中.所以我想我可以扩展它来定义filter_double谓词:

This checks if 'Item' is on the list X or not. So I thought I could expand this to define a filter_double predicate as well:

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

这对我来说非常合理:如果Ah不在列表的其余部分(其尾部)中出现，请使用列表构造在结果的前面添加a，否则递归到列表的其余部分. 显然Prolog认为不是这样:

This made perfect sense to me: if Ah doesn't occur in the rest of the list (its tail), then add a to the front of result using list construction, otherwise recurse over the rest of the list. Apparently Prolog thinks otherwise:

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

我对此是否认为势在必行?

Am I thinking too imperative on this?

推荐答案

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

You need recursion in both branches, and you need a base case:

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

Result = [Ah|Result] indeed seems to be a case of imperative thinking. What in means in Prolog is "unify Result with a term that has Result as its second argument," which either fails (in unification with occurs check) or produces a "rational tree" (an graph structure with a loop, in most Prologs).

锻炼:使我发布的代码尾部递归.

Exercise: make the code I posted tail-recursive.

请注意，这会删除每个项目中除最后一次出现以外的所有内容.

Note that this removes all but the last occurrence of each item.

这篇关于前言;如果和(停止)递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！