问题描述
您将如何在Prolog中编码自己的谓词，以完全执行nth1函数的作用?
How would you code your own predicate in Prolog, to do exactly what the nth1 function does?
对于不熟悉该功能的用户，最好通过示例来显示其功能:
For those not familiar with that function, its power is best displayed through an example:
?-nth1(2，[a，b，c]，E，R).
?- nth1(2, [a,b,c], E, R).
E = b
R = [a，c]
R = [a, c]
调用nth1函数并传递以下内容时:-一个元素的索引，将从列表中删除该元素(请注意，它不是零索引的，这里我们传递的是索引2)-列表(在这种情况下，它是[a，b，c])-E，将分配从列表中删除的元素-R，一个新列表，它将保存新列表，减去已删除的一个元素.
When the nth1 function is called, and is passed the following:- an index of an element, of which is to be removed from the list (note that it is not zero-indexed, and that here, we are passing index 2)- the list (in this case, it is [a,b,c])- E, which will be assigned the element that was removed from the list- R, a new list, which will hold the new list, minus that one element that was removed.
我对如何开始感到很沮丧.任何意见，将不胜感激.我知道应该可以在SWI-Prolog中使用大约3或4行递归来实现，我只是不知道从哪里开始.
I'm stomped on how to start. Any advice would be appreciated. I know that it should be do-able using recursion in about 3 or 4 lines in SWI-Prolog, I just have no idea where to start.
推荐答案
@EMS回答是相当不错的，但是正确实现谓词可能很棘手.我们必须考虑对关系nth1/4有意义的每个实例化模式，因为该问题要求恰好具有相同的内在行为.因此nth1还可以在位置搜索元素和插入.
@EMS answer is fairly good, but implementing correctly that predicate can be tricky. We must consider each instantiation pattern that make sense over the relation nth1/4, cause the question requires exactly the same builtin' behaviour. So nth1 can also search elements and insert at position.
SWI-Prolog用于在不同的实现之间进行效率切换，但是应该可以在需要的地方对关系进行建模以测试实例化.
SWI-Prolog for efficiency switch among different implementation, but should be possible model the relation testing the instantiation where needed.
我将其称为nth1，而不是nth1.
Instead of nth1 I called it mth1.
mth1(1, [X|R], X, R).
mth1(_, L, _, _) :-
L == [], % (==)/2 fails when L is a var
!, fail.
mth1(P, [H|T], X, [H|R]) :-
( var(P) % are we searching the position?
-> mth1(Q, T, X, R),
P is Q + 1
; Q is P - 1,
mth1(Q, T, X, R)
).
测试L == []是插入所必需的.
当然调试是必须的，这里有一些简单的测试:
Of course debugging it is mandatory, here some simple test:
?- mth1(2,[a,b,c,d,e],X,Y).
X = b,
Y = [a, c, d, e] ;
false.
?- mth1(X,[a,b,c,d,e],b,Y).
X = 2,
Y = [a, c, d, e] ;
false.
?- mth1(2,X,b,[a,c,d,e]).
X = [a, b, c, d, e] ;
false.
您应该检查是否覆盖了SWI-Prolog允许的所有实例化模式...
You should check if all instantiation patterns allowed by SWI-Prolog are covered...
如何执行这种简单的想法?这是基本测试
How does perform this simple minded implementation? Here a basic test
test_performance(N) :-
numlist(1, N, L),
time(test_performance(L, N, nth1)),
time(test_performance(L, N, mth1)).
test_performance(L, N, P) :-
writeln(P),
writeln('access last'),
time((call(P, N, L, X, _), assertion(X == N))),
writeln('find position of last'),
time((call(P, Z, L, N, _), assertion(Z == N))),
writeln('add tail'),
time(call(P, N, _, tail, L)).
令我惊讶的是，窥视元素并在尾部添加元素(略)更快，而查找位置却要慢得多(因为错过尾部递归?):
To my surprise, peeking the element and adding at tail are (slightly) faster, while find position is way slower (because of miss tail recursion?):
?- test_performance(1000000).
nth1
access last
% 1,000,011 inferences, 0,624 CPU in 0,626 seconds (100% CPU, 1602617 Lips)
find position of last
% 1,000,003 inferences, 0,670 CPU in 0,671 seconds (100% CPU, 1493572 Lips)
add tail
% 1,000,009 inferences, 0,482 CPU in 0,484 seconds (100% CPU, 2073495 Lips)
% 3,000,243 inferences, 1,777 CPU in 1,781 seconds (100% CPU, 1688815 Lips)
mth1
access last
% 1,000,002 inferences, 0,562 CPU in 0,563 seconds (100% CPU, 1779702 Lips)
find position of last
% 2,000,001 inferences, 1,998 CPU in 2,003 seconds (100% CPU, 1001119 Lips)
add tail
% 1,000,000 inferences, 0,459 CPU in 0,460 seconds (100% CPU, 2179175 Lips)
% 4,000,223 inferences, 3,019 CPU in 3,027 seconds (100% CPU, 1324901 Lips)
true .
实际上，具有较长列表的位置搜索使用传统的StackOverflow来显示其效率低下:
Indeed, with longer lists the position search shows its inefficiency, with a classic StackOverflow:
?- test_performance(2000000).
nth1
access last
% 2,000,011 inferences, 1,218 CPU in 1,221 seconds (100% CPU, 1641399 Lips)
find position of last
% 2,000,003 inferences, 1,327 CPU in 1,330 seconds (100% CPU, 1507572 Lips)
add tail
% 2,000,009 inferences, 0,958 CPU in 0,960 seconds (100% CPU, 2088038 Lips)
% 6,000,243 inferences, 3,504 CPU in 3,511 seconds (100% CPU, 1712549 Lips)
mth1
access last
% 2,000,002 inferences, 1,116 CPU in 1,118 seconds (100% CPU, 1792625 Lips)
find position of last
% 1,973,658 inferences, 2,479 CPU in 2,485 seconds (100% CPU, 796219 Lips)
% 3,973,811 inferences, 3,595 CPU in 3,603 seconds (100% CPU, 1105378 Lips)
ERROR: Out of local stack
这篇关于在SWI Prolog中实现nth1列表操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！