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).
E = b
R = [a, c]
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.
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 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 for efficiency switch among different implementation, but should be possible model the relation testing the instantiation where needed.
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)
).
the test L == [] is required to insert.
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.
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 .
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
First, decompose the problem into smaller constituent parts. To select the Nth item from a list is easy. Collection the difference is less so.
Therefore, break it down into two parts:
First, burst the list into a prefix, the desired item and the suffix.
Next, concatenate the prefix and suffix via append/3 to form the remainder list.
Your my_nth1\4 predicate should therefore look something like so:
nth1( N , List , Nth, Rest ) :-
burst( N , List , Pfx , Nth , Sfx ) ,
append( Pfx , Sfx , Rest )
.
% ------------------------------------------------------------------------------
% burst a list into 3 parts - a prefix, an item and a suffix
% based on the specified offset N (where 0 indicates the first item of the list)
%
% The prefix is built up using a "difference list" as we recurse down looking
% for the Nth item.
% ------------------------------------------------------------------------------
burst( 0 , [L|Ls] , [] , L , Ls ).
burst( N , [L|Ls] , [L|Pfx] , Nth , Sfx ) :-
N > 0 ,
N1 is N - 1 ,
burst( N1 , Ls , Pfx , Nth , Sfx )
.
