CODEWITHSUNDEEP
prolog
Manuel Selva
Manuel Selva

Reputation: 19050

How compute Index of element in a list?

I am starting to play with prolog, and with a Java background it's really difficult for me so here is a silly question:

How will you write an indexOf predicate able to give the index of a given element in a given list ?

My first question is about the predicate arity: I guess it should be 3 such as:

indexOf(List,Element, Index) :- ......

Am I right ? May be this already exists in built-in libraries but I want to learn how to write it. Thanks for your help.

Upvotes: 12

Views: 35946

Answers (3)

ToonAlfrink
ToonAlfrink

Reputation: 2626

I made this in successor notation and it's quite concise and neat:

index([V|_],V,0).
index([_|T],V,s(I)) :- index(T,V,I).

sample outputs:

?- index([a,b,c,a],a,X).
X = 0 ;
X = s(s(s(0))) ;
false.

?- index(List,a,s(0)).
List = [_G1710, a|_G1714].

Upvotes: 1

Yeti
Yeti

Reputation: 2855

One should prefer to use tail-recursion:

indexOf(V, [H|T], A, I)
:-
    Value = H, A = I, !
;
    ANew is A + 1,
    indexOf(V, T, ANew, I)
.

indexOf(Value, List, Index)
:-
    indexOf(Value, List, 0, Index)
.

indexOfWithoutFailure(Value, List, Index)
:-
    indexOf(Value, List, 0, Index)
;
    Index = -1
.

Some example queries:

?- indexOf(d, [a, b, c, d, e, f], Index).
Index = 3.

?- indexOf(x, [a, b, c, d, e, f], Index).
false.

?- indexOfWithoutFailure(x, [a, b, c, d, e, f], Index).
Index = -1.

If you want to get all indexes of an element in a list, you should write another predicate for it without the cut named allIndexesOf or something.

Upvotes: 1

gusbro
gusbro

Reputation: 22585

You can do it recursively: Suppose 0-based index (otherwise just change the 0 with 1 on the first clause)

indexOf([Element|_], Element, 0). % We found the element
indexOf([_|Tail], Element, Index):-
  indexOf(Tail, Element, Index1), % Check in the tail of the list
  Index is Index1+1.  % and increment the resulting index

If you want only to find the first appearance, you could add a cut (!) to avoid backtracking.

indexOf([Element|_], Element, 0):- !.
indexOf([_|Tail], Element, Index):-
  indexOf(Tail, Element, Index1),
  !,
  Index is Index1+1.

Upvotes: 14

Related Questions