CODEWITHSUNDEEP
prolog
Andrew Burgess
Andrew Burgess

Reputation: 1797

Find all positions of a value in a list in Prolog

My assignment is this: Write a program that reads an integer x and a list of integers L; then locate the list of all positions of x into L, and return the resulting list. For example, for x=2 and L=[1,2,3,4,2,5,2,6] the program should return the list R=[2,5,7].

So far, I've been able to write an indexOf predicate:

indexOf([E|_], E, 1).
indexOf([_|T], E, I) :- indexOf(T, E, I2), I is I2 + 1.

However, this doesn't "return" a list. So:

indexOf([a,b,c,a,d], a, R).
R = 1;
R = 4

I'd like to do something like this:

findAll([a,b,c,a,d], a, R).
R = [1, 4]

But I'm not sure how to collect the values into a list.

This is a school assignment, so I'd appreciate just a nudge in the right direction.

Upvotes: 3

Views: 3325

Answers (1)

user1812457
user1812457

Reputation:

A nudge: you find the indices, but you don't collect them.

indices(List, E, Is) :-
    indices_1(List, E, Is, 1).

For an empty list, the list of indices is empty, and the element doesn't matter

indices_1([], _, [], _).

If the element is like the head, collect the index.

indices_1([E|Xs], E, [I|Is], I) :-
    I1 is I + 1,
    indices_1(Xs, E, Is, I1).

This needs another clause to work properly.

EDIT:

One way to do it would be:

indices_1([X|Xs], E, Is, I) :- dif(X, E),
    I1 is I + 1,
    indices_1(Xs, E, Is, I1).

In the previous clause, the head of the list and the Element are unified. In this clause, they are explicitly different. This means that only one of the two clauses can be true for an element of the list in the first arguemnt.

EDIT:

Another way to do that is to use findall and nth1:

indices(List, E, Is) :-
    findall(N, nth1(N, List, E), Is).

Upvotes: 2

Related Questions