如何在 Prolog 中查找列表的第 N 个元素
How to find the Nth element of a list in Prolog
我正在尝试编写一个 Prolog 代码来查找列表的第 n 个元素。
我写了下面的代码，但 return 元素不正确。
match([Elem|Tail],Num,Num,Elem).
match([Elem|Tail],Num,C,MatchedNumber):-
match(Tail,Num,N,Elem),
C is N+1.
第一行我说，如果请求的元素个数等于counter，那么把当前列表的第一个元素赋给变量MatchedNumber。此代码 return 是 Num 和 Counter 正确的，但我不知道为什么当我想将 MatchedNumber 设置为 Elem 时，它总是 return是列表的第一个元素。
1：这段代码有什么问题？
2: 我怎么能说不显示匹配的号码，而是将其从列表中删除？
首先，有一个内置的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 return 第 i 个元素。它可以简单地 return 任何元素，因为 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，在这种情况下，您 return head，否则您查询 i-1-尾部的第一个元素。这也是一种更具声明性的方法。
这种方法还利用了尾递归，这通常会显着提高性能。
修改原始谓词
使用迭代器和绑定更像是un-Prolog，一个通常使用反向迭代器。
但是您可以按如下方式修改谓词：
match([Elem|_],Num,Num,Elem) :-
!.
match([_|Tail],Num,Count,MatchedNumber) :-
Count < Num,
Count1 is Count+1,
match(Tail,Num,Count1,MatchedNumber).
所以有几个错误：
- 在第一个子句中使用 "cut"
!：因为如果它匹配，我们知道 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].
要找到列表的第 n 个元素（其中 n 是相对于零的），这样的事情应该就足够了：
find_nth_element_of_list( 0 , X , [X|_] ) .
find_nth_element_of_list( N , X , [_|Xs] ) :-
N > 0 ,
N1 is N-1 ,
find_nth_element_of_list( N1 , X , Xs )
.
类似地，要删除列表的第 n 个元素，像这样的东西应该就足够了：
remove_nth_element_of_list( 0 , [_|Xs] , Xs ) . % at n=0, toss the head and unify the tail with the result set
remove_nth_element_of_list( N , [X|Xs] , [X|Ys] ) :- % at n>0, prepend the head to the result and recurse down.
N > 0 ,
N1 is N-1 ,
remove_nth_element_of_list( N1 , Xs , Ys )
.
如果出于某种原因您需要使用除 append 之外的内置谓词来实现此目的，这是我的实现：
my_length([], 0).
my_length([_|T], N1) :- my_length(T, N), N1 is N + 1.
% Nth
my_nth(N, List, H) :-
append(L1, [H|_], List),
my_length(L1, N),
!.
test_my_nth(X, Y, Z) :-
my_nth(0, [123, 456, 789], X),
my_nth(1, [123, 456, 789], Y),
my_nth(2, [123, 456, 789], Z).
% X = 123
% Y = 456
% Z = 789
没有append:
my_length([], 0).
my_length([_|T], N1) :- my_length(T, N), N1 is N + 1.
% Nth
my_nth(0, [H|_], H) :- !.
my_nth(N, [_|T], Result) :-
N1 is N - 1,
my_nth(N1, T, Result),
!.
test_my_nth(X, Y, Z) :-
my_nth(0, [123, 456, 789], X),
my_nth(1, [123, 456, 789], Y),
my_nth(2, [123, 456, 789], Z).
% X = 123
% Y = 456
% Z = 789
没有!:
my_length([], 0).
my_length([_|T], N1) :- my_length(T, N), N1 is N + 1.
% Nth
my_nth(N, [_|T], Result) :-
N > 0,
N1 is N - 1,
my_nth(N1, T, Result).
my_nth(0, [H|_], H).
test_my_nth(X, Y, Z) :-
my_nth(0, [123, 456, 789], X),
my_nth(1, [123, 456, 789], Y),
my_nth(2, [123, 456, 789], Z).
% X = 123
% Y = 456
% Z = 789
为什么会有人需要它？波兹南理工大学有专门教授要求学生这样写谓词
我正在尝试编写一个 Prolog 代码来查找列表的第 n 个元素。 我写了下面的代码，但 return 元素不正确。
match([Elem|Tail],Num,Num,Elem).
match([Elem|Tail],Num,C,MatchedNumber):-
match(Tail,Num,N,Elem),
C is N+1.
第一行我说，如果请求的元素个数等于counter，那么把当前列表的第一个元素赋给变量MatchedNumber。此代码 return 是 Num 和 Counter 正确的，但我不知道为什么当我想将 MatchedNumber 设置为 Elem 时，它总是 return是列表的第一个元素。
1：这段代码有什么问题？ 2: 我怎么能说不显示匹配的号码，而是将其从列表中删除？
首先，有一个内置的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 return 第 i 个元素。它可以简单地 return 任何元素，因为 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，在这种情况下，您 return head，否则您查询 i-1-尾部的第一个元素。这也是一种更具声明性的方法。
这种方法还利用了尾递归，这通常会显着提高性能。
修改原始谓词
使用迭代器和绑定更像是un-Prolog，一个通常使用反向迭代器。
但是您可以按如下方式修改谓词：
match([Elem|_],Num,Num,Elem) :-
!.
match([_|Tail],Num,Count,MatchedNumber) :-
Count < Num,
Count1 is Count+1,
match(Tail,Num,Count1,MatchedNumber).
所以有几个错误：
- 在第一个子句中使用 "cut"
!：因为如果它匹配，我们知道 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].
要找到列表的第 n 个元素（其中 n 是相对于零的），这样的事情应该就足够了：
find_nth_element_of_list( 0 , X , [X|_] ) .
find_nth_element_of_list( N , X , [_|Xs] ) :-
N > 0 ,
N1 is N-1 ,
find_nth_element_of_list( N1 , X , Xs )
.
类似地，要删除列表的第 n 个元素，像这样的东西应该就足够了：
remove_nth_element_of_list( 0 , [_|Xs] , Xs ) . % at n=0, toss the head and unify the tail with the result set
remove_nth_element_of_list( N , [X|Xs] , [X|Ys] ) :- % at n>0, prepend the head to the result and recurse down.
N > 0 ,
N1 is N-1 ,
remove_nth_element_of_list( N1 , Xs , Ys )
.
如果出于某种原因您需要使用除 append 之外的内置谓词来实现此目的，这是我的实现：
my_length([], 0).
my_length([_|T], N1) :- my_length(T, N), N1 is N + 1.
% Nth
my_nth(N, List, H) :-
append(L1, [H|_], List),
my_length(L1, N),
!.
test_my_nth(X, Y, Z) :-
my_nth(0, [123, 456, 789], X),
my_nth(1, [123, 456, 789], Y),
my_nth(2, [123, 456, 789], Z).
% X = 123
% Y = 456
% Z = 789
没有append:
my_length([], 0).
my_length([_|T], N1) :- my_length(T, N), N1 is N + 1.
% Nth
my_nth(0, [H|_], H) :- !.
my_nth(N, [_|T], Result) :-
N1 is N - 1,
my_nth(N1, T, Result),
!.
test_my_nth(X, Y, Z) :-
my_nth(0, [123, 456, 789], X),
my_nth(1, [123, 456, 789], Y),
my_nth(2, [123, 456, 789], Z).
% X = 123
% Y = 456
% Z = 789
没有!:
my_length([], 0).
my_length([_|T], N1) :- my_length(T, N), N1 is N + 1.
% Nth
my_nth(N, [_|T], Result) :-
N > 0,
N1 is N - 1,
my_nth(N1, T, Result).
my_nth(0, [H|_], H).
test_my_nth(X, Y, Z) :-
my_nth(0, [123, 456, 789], X),
my_nth(1, [123, 456, 789], Y),
my_nth(2, [123, 456, 789], Z).
% X = 123
% Y = 456
% Z = 789
为什么会有人需要它？波兹南理工大学有专门教授要求学生这样写谓词