CODEWITHSUNDEEP
prolog
Nagham Al Halabi
Nagham Al Halabi

Reputation: 85

How to construct a list of positions for a certain element in a main list?

How can I write a predicate list_pos(B,E,L), that returns the positions of E in B, in a list named L (considering that the first element of B has position=0), i tried writing such a program but it didn't run successfully.Thanks

Upvotes: 4

Views: 149

Answers (5)

false
false

Reputation: 10142

Here is a general, and pure solution - I will put a bounty here to fit this into more convenient abstractions.

list_pos(Xs, E, Ps) :-
   list_pos(Xs, E, Ps, 0).

list_pos([], _E, [], _P).
list_pos([X|Xs], X, [P0|Ps], P0) :-
   P1 is P0 + 1,
   list_pos(Xs, X, Ps, P1).
list_pos([X|Xs], E, Ps, P0) :-
   dif(X, E),        % element must be different
   P1 is P0 + 1,
   list_pos(Xs, X, Ps, P1).

And here is a more compact and efficient way for list_pos/4 using if_/3 and reïfied equality (=)/3. Prolog's if_/3 is a bit different to traditional if-then-else, for it can opt for both the Then and the Else. Maybe just try out the if_/3:

?- if_( X=Y, Diagnosis=equal, Diagnosis=inequal).
   X = Y, Diagnosis = equal
;  Diagnosis = inequal, dif(X, Y).

Informally, what we ask here is:

Are X and Y equal or not?

And the Prolog answer is not just yes or no, but:

Yes, they are equal, if they are equal

AND

No, they are not equal, if they are different

Sounds irritating? Well, if we ask such general questions that do not contain sufficient information, we should not be surprised to get similarly general answers!

list_pos([], _E, [], _P).
list_pos([X|Xs], E, Ps0, P0) :-
   P1 is P0+1,
   if_(X = E, Ps0 = [P0|Ps1], Ps0 = Ps1),
   list_pos(Xs, E, Ps1, P1).

And now, lets try something very general!

How must a list [X,Y,Z] look like such that any element E occurs in it twice?

?- list_pos([X,Y,Z],E,[A,B]).
   X = Y, Y = E, % ... the first two are the same
   A = 0, B = 1,
   dif(Z, E)     % ... but the last is different
;  X = Z, Z = E, % ... the first and last are the same
   A = 0, B = 2,
   dif(Y, E)     % ... but the middle element is different
;  Y = Z, Z = E, % ... the last two are the same
   A = 1, B = 2,
   dif(X, E)     % ... and the first is different.
;  false.

Note that these answers comprise the full generality of all possible three element lists! All of them have been included.

Upvotes: 2

guest
guest

Reputation: 11

Thanks to @false and @Jerome I am learning a lot. Nevertheless, I will post my efforts:

    list_pos(List,Elem,Result) :-
            list_pos(List,Elem,[],-1,R),
            reverse(R,Result),
            !.

    list_pos([],_,W,_,W).
    list_pos([X|Xs],X,Zs,P,R) :-
            Pos is P + 1,
            list_pos(Xs,X,[Pos|Zs],Pos,R).
    list_pos([_|Xs],Y,Zs,P,R) :-
            Pos is P + 1,
            list_pos(Xs,Y,Zs,Pos,R).

Ex.

    ?- list_pos([],a,R).
    R = [].

    ?- list_pos([a,c,a,d,e,f],a,R).
    R = [0, 2].

    ?- list_pos([a,b,c,d,e,f,g],g,R).
    R = [6].

    ?- list_pos([a,a,a,a,a,a,a,a,a],a,R).
    R = [0, 1, 2, 3, 4, 5, 6, 7, 8].

Upvotes: 1

Jerome
Jerome

Reputation: 2370

To construct a list of all the results, use findall:

list_pos(List, Element, Result) :-
  findall(Position, nth0(Position, List, Element), Result).

Upvotes: 0

false
false

Reputation: 10142

Here is a solution which is slightly more general than @Jerome's:

list_pos(Xs, E, Ps) :-
   ( ground(Xs) -> true ; throw(error(instantiation_error,_)) ),
   ( length(Xs,_) -> true ; throw(error(type_error(list,Xs),_)) ),
   bagof(P, nth0(P, Xs, E), Ps).

?- list_pos([a,b,c,c,a,a], E, Rs).
   E = a, Rs = [0, 4, 5]
;  E = b, Rs = [1]
;  E = c, Rs = [2, 3].

So you do not even need to indicate the precise element you want. Instead, you ask:

What are the occurrences of the various elements?

This can be generalized even one step further ...

Upvotes: 2

guest
guest

Reputation: 1

I tried:

    list_pos(1,Match,[Match|_]).
    list_pos(Pos,Element,[_|Tail]) :-
             list_pos(P,Element,Tail),
             Pos is P + 1.

Ex.

    ?- list_pos(B,a,[a]).
    B = 1 .

    ?- list_pos(B,a,[b,a]).
    B = 2 .

    ?- list_pos(B,a,[b,c,d,e,a,f]).
    B = 5 .

Upvotes: 0

Related Questions