list - 如何在Prolog中找到列表的第N个元素

Question

我正在尝试编写一个 Prolog 代码来查找列表的第 n 个元素。
我写了下面的代码，但它没有正确返回元素。

match([Elem|Tail],Num,Num,Elem).
match([Elem|Tail],Num,C,MatchedNumber):-
   match(Tail,Num,N,Elem),
   C is N+1.

在第一行我说，如果请求的元素编号等于 counter，则将当前列表的第一个元素给名为 MatchedNumber 的变量。 .此代码返回 Num和 Counter是的，但我不知道为什么要设置 MatchedNumber如 Elem ，它总是返回列表的第一个元素。

1:这段代码有什么问题？
2:我如何说而不是显示匹配的号码，而是将其从列表中删除？

Answer 1

首先，有一个内置 nth0/3为了那个原因:

?- nth0(0,[a,b,c],X).
X = a.

?- nth0(1,[a,b,c],X).
X = b.

?- nth0(2,[a,b,c],X).
X = c.

?- nth0(3,[a,b,c],X).
false.

获取第 i 个元素

问题是在归纳的情况下:

match([Elem|Tail],Num,Counter,MatchedNumber):-
    match(Tail,Num,N,Elem),
    C is N+1.

Prolog 对 C 一无所知所以最后一条语句不会强制 Prolog 返回第 i 个元素。它可以简单地返回任何元素，因为 N将与 Num 匹配在递归调用中然后设置 C至 Num+1但这不是问题，因为 C不受任何约束。

解决此问题的更好方法是使用递减计数器:

match([H|_],0,H) :-
    !.
match([_|T],N,H) :-
    N > 0, %add for loop prevention
    N1 is N-1,
    match(T,N1,H).

示例 :

?- match([a,b,c,d,e],0,X).
X = a.

?- match([a,b,c,d,e],1,X).
X = b.

?- match([a,b,c,d,e],2,X).
X = c.

?- match([a,b,c,d,e],3,X).
X = d.

?- match([a,b,c,d,e],4,X).
X = e.

?- match([a,b,c,d,e],5,X).
false.

因此，基本情况是指数为 0在这种情况下，您返回头部，否则查询尾部的第 i-1 个元素。这也是一种更具声明性的方法。

这种方法还利用了尾递归，这通常会显着提高性能。

修改原始谓词

使用迭代器和边界是相当不 Prolog 的，通常使用反向迭代器。

但是，您可以按如下方式修改谓词:

match([Elem|_],Num,Num,Elem) :-
    !.
match([_|Tail],Num,Count,MatchedNumber) :-
    Count < Num,
    Count1 is Count+1,
    match(Tail,Num,Count1,MatchedNumber).

所以有几个错误:

使用“剪切”!在第一个子句中:因为如果匹配，我们知道 Prolog 不应该尝试第二个；

使用 MatchedNumber在递归调用中而不是 Elem ;

执行边界检查 Count < Num ,

做计数器的增量Count1 is Count+1在进行递归调用之前；和

用下划线替换所有不使用的变量 _ .

一个例子是:

?- match([a,b,c,d,e],0,0,X).
X = a.

?- match([a,b,c,d,e],1,0,X).
X = b.

?- match([a,b,c,d,e],2,0,X).
X = c.

?- match([a,b,c,d,e],3,0,X).
X = d.

?- match([a,b,c,d,e],4,0,X).
X = e.

?- match([a,b,c,d,e],5,0,X).
false.

但如前所述，传递额外的参数等是低效的。

从列表中删除第 i 个元素

可以使用几乎等效的方法从列表中删除第 i 个元素:

removei([],_,[]).
removei([_|T],0,T) :-
    !.
removei([H|T],N,[H|TR]) :-
    N1 is N-1,
    removei(T,N1,TR).

这里的基本情况再次是索引为 0在这种情况下，列表的尾部将被删除(从而去掉头部)。归纳案例会将列表的头部放在结果列表的头部，并依靠递归调用从尾部移除正确的项目。另一个基本案例 removei([],_,[]).添加是因为 i 可能大于列表的长度，在这种情况下，此谓词不会删除任何项目。

示例

?- removei([a,b,c,d,e],0,X).
X = [b, c, d, e].

?- removei([a,b,c,d,e],1,X).
X = [a, c, d, e].

?- removei([a,b,c,d,e],2,X).
X = [a, b, d, e].

?- removei([a,b,c,d,e],3,X).
X = [a, b, c, e].

?- removei([a,b,c,d,e],4,X).
X = [a, b, c, d].

?- removei([a,b,c,d,e],5,X).
X = [a, b, c, d, e].

?- removei([a,b,c,d,e],6,X).
X = [a, b, c, d, e].