如何在Prolog中找到列表的第N个元素 [英] How to find the Nth element of a list in Prolog

问题描述

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

I am trying to write a Prolog code finding the n-th element of a list. I wrote the below code but it doesn't return the element right.

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 ，它总是返回列表的第一个元素.

In the first line I say, if the requested element number is equal to counter, then give the first element of the current list to the variable called MatchedNumber. This code returns the Num and Counter right but I don't know why when I want to set the MatchedNumber as Elem, it always returns the first element of the list.

1:此代码有什么问题?2:怎么说呢，而不是显示匹配的数字，而是将其从列表中删除?

1: what is wrong with this code? 2: How can I say instead of showing the matched number, remove it from list?

推荐答案

首先，有一个内置的 nth0/3 用于:

First of all, there is a builtin nth0/3 for that:

?- 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 个元素

问题在于归纳案例:

Get the i-th element

The problem is in the inductive case:

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 没有任何约束.

Prolog doesn't know anything about C so the last statement doens't force Prolog to return the i-th element. It can simply return any element because N will match with Num in the recursive call and then set C to Num+1 but that's not a problem because C is not bound by anything.

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

A better way to solve this, is using a decrement counter:

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 ，在这种情况下，您将返回 head ，否则将查询 i-1 -尾巴的第一个元素.这也是一种更具声明性的方法.

The base case is thus that the index is 0 in which case you return the head, otherwise you query for the i-1-th element of the tail. This is also a more declarative approach.

此方法还利用了 tail递归，通常可以显着提高性能.

This approach also makes use of tail recursion which in general will boost performance significantly.

使用迭代器和绑定是 un-Prolog ，通常使用反向迭代器.

It is rather un-Prolog to use an iterator and a bound, one in general uses a reverse iterator.

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

You can however modify the predicate as follows:

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<编号，
• 在进行递归调用之前，将计数器 Count1的增量设为Count + 1 ；和
• 用下划线 _ 替换所有您不使用的变量.

• Use a "cut" ! in the first clause: since if it matches, we know Prolog should not try the second one;
• Use MatchedNumber in the recursive call instead of Elem;
• Perform a bound check Count < Num,
• Do the increment of the counter Count1 is Count+1 before doing the recursive call; and
• Substitute all variables you do not use by underscores _.

然后是一个示例:

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

但是如前所述，传递附加参数等效率很低.

But as said before, it is inefficient to pass an additional argument, etc.

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

An almost equivalent approach can be used to remove the i-th element from the list:

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

这里的基本情况还是索引为 0 ，在这种情况下，列表的尾部被删除(因此删除了头部).归纳案例将列表的头部放在结果列表的头部，并将依靠递归调用从尾部删除正确的项.添加了另一种基本情况 removei([]，_，[])..这是因为 i 可能大于列表的长度，在这种情况下，该谓词将获胜.不要删除任何物品.

Here the base case is again that the index is 0 in which case the tail of the list is removed (thus dropping the head). The inductive case will place the head of the list in the head of the resulting list and will count on the recursive call to remove the correct item from the tail. Another base case removei([],_,[]). is added because it is possible that i is greater than the length of the list in which case this predicate won't remove any item.

示例

?- 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].

这篇关于如何在Prolog中找到列表的第N个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！