在SWI Prolog中实现nth1列表操作 [英] Implementing nth1 list operation in SWI prolog

问题描述

您将如何在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列表操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！