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?

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

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

Solution 3

If for some reason you need to achieve this using no built-in predicates besides append here is my implementation:

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

and without 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

And without !:

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

Why would anyone need it? There is a specific professor at Poznan University of Technology that requires students to write predicates like this.

Comments

[Amir Jalilifard]

Thanks. Yes. I made a mistake. It is not "C". It is "Counter" variable. Now I changed it. So, how can I solve this problem using my code?

[Amir Jalilifard]

My question is just that, how can I edit my code to solve this problem?

[false]

These versions are not steadfast.

[Willem Van Onsem]

@AmirJalilifard: well thats explained in the remainder of this answer.

[Willem Van Onsem]

@false: indeed, one can use a negative index or use unbounded variables.

[Amir Jalilifard]

@ CommuSoft He just said what was the problem of just a part of this code. When I changed it, the code didn't work! This is why I am asking him to give me another hint!

[Willem Van Onsem]

Well the second hint is: which value do you want to compute with is? N or C...

[Amir Jalilifard]

I have a counter called C. I have a requested element number called N. now I want to check when N=C. When they are equal it means we are in the right place in the list. Now I just wanna show this value!

[false]

match([a|_], 0, b) loops whereas match([a|_],0,X), X=b fails.

[Willem Van Onsem]

@false: (1) modified with N > 0, (2) shouldn't the second fail?

[Amir Jalilifard]

Yes. Better. Thank you. But I've not get my answer yet! How can I modify my code to do this job for me?

[Willem Van Onsem]

@AmirJalilifard: I reformulated it in a list of items how you can modify your original predicate.