How to find the Nth element of a list in Prolog

Question

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.

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: what is wrong with this code? 2: How can I say instead of showing the matched number, remove it from list?

Answer 1

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.

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

Example:

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

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.

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

Modifying the original predicate

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

So a few errors:

• 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 _.

An example is then:

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

Remove the i-th element from the list

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

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.

Example

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

Answer 2

To find the nth element of a list (where n is relative to zero), something like this ought to suffice:

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

Similarly, to remove the nth element of a list, something like this ought to suffice:

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