Prolog membership operation on a list which returns the index of the found element

Question

I have currently started with PROLOG and I want to write a predicate which checks if a given object is in this list or not. If the object is in the list the predicate should return the index of the element. If the element is not found it should return 0.

It should work like this: find(3,[1,4,5,3,2,3],N). -> yes. N / 4 find(2,[1,3,4,5,6,7],N). -> yes. N / 0

But I have problems with counting up the index N and maybe someone here can help. I've seen many different ways on how to traverse a list but I found so many different ways and I wasn't able to understand how they work. I would be really happy if someone can provide a solution and explain how it works and why.

This is what I wrote so far:

find(X, [X|TAIL], N) :- N is 1, write(N).
find(X, [], N) :- N is 0, write(N).

find(X, [_|TAIL], N) :- find(X, TAIL, N + 1).

It is working for the basecases:

find(a, [a, b, c, d, e, f, g], N) -> yes. N / 1.
find(j, [a, b, c, d, e, f, g], N) -> yes. N / 0.

But when it is starting with recursion It is not working anymore and I don't understand what's going wrong.

For the recursion case it gives me this: find(b, [a, b, c, d, e, f, g], N) -> no.

I am thankful for every answer and every comment!

Requirements:

• If an element is not in the list it should output yes. N = 0. Examples: ?- find(a, [], N) -> yes. N = 0. and ?- find(a, [b,c,d], N) -> yes. N = 0.
• If an element is in the list it should output the index of that element (start counting with 1). Examples: ?- find(a, [a, b, c], N) -> yes. N = 1 and ?- find(a, [b,c,a,d], N) -> yes. N = 3.
• If there is the element more than one time it should only output the index of the first appearance of the element. Example: ?- find(a, [a,b,c,a], N) -> yes. N = 1.
• It should always only give on answer.
• If possible no libraries should be used.
• The query ?- find(a, [a, b,c], 0) and ?- find(a, [b, a, c], 0) and every other query where a is in the list should be answered with no.
• The query ?- find(a, [a, b, c, a], 4) should be answered with no because the a with index 4 is not the first apperance of a.

Answer 1

Note: This solution yields every index where Item is found upon backtracking and unifies Index with 0 only when no item unifies with the target item, and is not exactly what OP has now explicitly stated in his requirements.

item_index(Item, L, Index):-
  item_index(L, Item, 1, Index).
  
item_index([], _, _, 0).
item_index([Item|L], Item, CurIndex, Index):-
  item_index1(L, Item, CurIndex, Index).
item_index([CurItem|L], Item, CurIndex, Index):-
  dif(CurItem, Item),
  succ(CurIndex, CurIndex1),
  item_index(L, Item, CurIndex1, Index).

item_index1(_, _, Index, Index).
item_index1(L, Item, CurIndex, Index):-
  succ(CurIndex, CurIndex1),
  item_index2(L, Item, CurIndex1, Index).

item_index2([Item|L], Item, CurIndex, Index):-
  item_index1(L, Item, CurIndex, Index).
item_index2([CurItem|L], Item, CurIndex, Index):-
  dif(CurItem, Item),
  succ(CurIndex, CurIndex1),
  item_index2(L, Item, CurIndex1, Index).

---

Explanation:

This answer goes through different procedures to maintain the state of whether any solution has been already found. So when traversing the list in item_index/4 there has been no match. After the first match (and upon every further match) item_index1/4 is called which will unify Index with the current index and upon backtracking continue traversing the list in item_index2/4.

When there are no more items to traverse it will unify Index with 0 only if there has been no previous matches (this is done in the first clause of item_index/4).

Sample runs:

?- item_index(A, [a,b,c,d,a,b,c], X).
A = a,
X = 1 ;
A = a,
X = 5 ;
A = b,
X = 2 ;
A = b,
X = 6 ;
A = c,
X = 3 ;
A = c,
X = 7 ;
A = d,
X = 4 ;
X = 0,
dif(A, a),
dif(A, c),
dif(A, b),
dif(A, a),
dif(A, d),
dif(A, c),
dif(A, b).

?- item_index(d, [a,b,c], X).
X = 0.    

?- item_index(A, [a,b,a], X).
A = a,
X = 1 ;
A = a,
X = 3 ;
A = b,
X = 2 ;
X = 0,
dif(A, a),
dif(A, a),
dif(A, b).

?- item_index(a, [a,b,C], X).
X = 1 ;
C = a,
X = 3 ;
false.

Answer 2

Two pure solutions using the library reif:

first_index(E0, Es, N) :-
    first_index_(E0, Es, 0, N).

first_index_(_, [], _, none).
first_index_(E0, [E|Es], I0, N) :-
    if_(
        E0 = E,
        N = some(I0),
        (   succ(I0, I),
            first_index_(E0, Es, I, N)
        )
    ).

index(E0, Es, none) :-
    maplist(dif(E0), Es).
index(E0, Es, some(I)) :-
    nth0(I, Es, E0).

This query succeeds deterministically:

?- L = [a,a], N = some(0), first_index(a, L, N).
   L = "aa", N = some(0).

This query fails:

?- L = [a,a], N = some(1), first_index(a, L, N).
   false.

While with index/3:

?- L = [a,a], index(a, L, some(0)), index(a, L, some(1)).
   L = "aa".

The question:

find_first(E, Es, N) :-
    first_index(E, Es, I),
    conversion(I, N).

find(E, Es, N) :-
    index(E, Es, I),
    conversion(I, N).

conversion(none, 0).
conversion(some(I), N) :-
    succ(I, N).

---

For now I don't have a better name.

Answer 3

Using the argument order of nth1/3

nth1_once_else_0(Nth1, Lst, Elem) :-
    nth1_once_else_0_when_(Lst, Elem, 1, Nth1).

nth1_once_else_0_thaw_([H|_], Elem, Upto, Nth1) :-
    Upto == Nth1,
    !,
    H = Elem.   
nth1_once_else_0_thaw_(L, _Elem, _Upto, Nth1) :-
    L == [],
    !,
    Nth1 = 0.
nth1_once_else_0_thaw_(L, Elem, _Upto, Nth1) :-
    Nth1 == 0,
    !,
    nth1_once_else_0_thaw_0_(L, Elem).
nth1_once_else_0_thaw_(_L, _Elem, Upto, Nth1) :-
    % If gone past Nth1, fail
    nonvar(Nth1),
    Nth1 =< Upto,
    !,
    fail.
nth1_once_else_0_thaw_([H|T], Elem, Upto, Nth1) :-
    (   nonvar(Nth1),
        Nth1 > Upto -> true
    ;   H \= Elem
    ),
    !,
    % Elements must be different
    dif(H, Elem),
    Upto1 is Upto + 1,
    nth1_once_else_0_when_(T, Elem, Upto1, Nth1).
nth1_once_else_0_thaw_([H|_], Elem, Upto, Nth1) :-
    ?=(H, Elem),
    % Able to compare
    H = Elem,
    !,
    % Elements match
    Upto = Nth1.
nth1_once_else_0_thaw_([H|T], Elem, Upto, Nth1) :-
    % Wait for possible comparison
    when(
        (?=(H, Elem) ; nonvar(Nth1)),
        nth1_once_else_0_thaw_([H|T], Elem, Upto, Nth1)
    ).

nth1_once_else_0_when_(L, Elem, Upto, Nth1) :-
    var(L),
    !,
    when(
        (nonvar(L), nonvar(Elem) ; nonvar(Nth1)),
        nth1_once_else_0_thaw_(L, Elem, Upto, Nth1)
    ).
nth1_once_else_0_when_([], _Elem, _Upto, 0).
nth1_once_else_0_when_([H|T], Elem, Upto, Nth1) :-
    when(
        (nonvar(H), nonvar(Elem) ; nonvar(Nth1)),
        nth1_once_else_0_thaw_([H|T], Elem, Upto, Nth1)
    ).

% Remainder of list does not match
nth1_once_else_0_thaw_0_(L, Elem) :-
    var(L),
    !,
    freeze(L, nth1_once_else_0_thaw_0_(L, Elem)).
nth1_once_else_0_thaw_0_([], _Elem).
nth1_once_else_0_thaw_0_([H|T], Elem) :-
    dif(H, Elem),
    freeze(T, nth1_once_else_0_thaw_0_(T, Elem)).

Using swi-prolog's unit test ability:

:- begin_tests(nth1_once_else_0).

test(1) :-
    nth1_once_else_0(2, [a, b], B), B == b.
test(2) :-
    nth1_once_else_0(N, [a, b, c, d, e, f, g], a), N == 1.
test(3) :-
    nth1_once_else_0(N, [a, b, c, d, e, f, g], j), N == 0.
test(4) :-
    nth1_once_else_0(N, [a, b, c, d, e, f, g], b), N == 2.
test(5) :-
    nth1_once_else_0(N, [], a), N == 0.
test(6) :-
    nth1_once_else_0(N, [], _), N == 0.
test(7) :-
    nth1_once_else_0(N, [a, b, c, a, b, c], a), N == 1.
test(8) :-
    \+ nth1_once_else_0(6, [a, b, c, a, b, c], c).
test(9) :-
    nth1_once_else_0(N, L, b), L = [a, b], N == 2.
test(10) :-
    \+ nth1_once_else_0(0, [a, b], b).
test(11) :-
    nth1_once_else_0(N, [a, b, c, a], a), N == 1.
test(12) :-
    nth1_once_else_0(N, [a, b, c], d), N == 0.
test(13) :-
    nth1_once_else_0(N, [a, b], X), X = b, N == 2.
test(14) :-
    nth1_once_else_0(N, L, X), L = [a, b|_], X = b, N == 2.
test(15) :-
    nth1_once_else_0(N, L, X), L = [a, b|_], N = 2, X == b.
test(16) :-
    nth1_once_else_0(N, L, X), L = [a, b|_], X = z, N = 0.
test(17) :-
    L = [a, a], nth1_once_else_0(1, L, a), \+ nth1_once_else_0(2, L, a).
test(18) :-
    nth1_once_else_0(N, L, X), L = [a, b|_], L = [a,b,c], N = 0, \+ X = a.
test(19) :-
    nth1_once_else_0(N, L, X), L = [a, b|_], X = z, L = [a, b], N == 0.
test(20) :-
    nth1_once_else_0(N, L, X), nth1(2, L, b), nth1(1, L, a), X = z, L = [a, b], N == 0.
test(21) :-
    nth1_once_else_0(N, L, X), nth1(2, L, b), nth1(1, L, a), L = [a, b], X = a, N == 1.
test(22) :-
    nth1_once_else_0(N, L, X), X = a, nth1(2, L, b), nth1(1, L, a), N == 1.
test(23) :-
    nth1_once_else_0(N, L, X), X = b,  nth1(2, L, b), nth1(1, L, a), N == 2.
test(24) :-
    nth1_once_else_0(3, L, c), nth1(3, L, C), C == c.
test(25) :-
    nth1_once_else_0(3, L, C), C = c, nth1(3, L, Z), Z == c.
test(26) :-
    nth1_once_else_0(N, L, c),  N = 3, nth1(N, L, C), C == c.
test(27) :-
    nth1_once_else_0(N, L, C), C = c, N = 3, nth1(N, L, Z), Z == c.
test(28) :-
    nth1_once_else_0(N, [a, b, c|_], c), N == 3.
test(29) :-
    \+ nth1_once_else_0(3, [_, _], z).
test(30) :-
    nth1_once_else_0(N, [-_, -_], +_), N == 0.
test(31) :-
    nth1_once_else_0(N, L, X), nth1(2, L, b), nth1(1, L, a), X = a, N == 1.
test(32) :-
    nth1_once_else_0(N, L, f(b)), L = [f(Z)|T], Z = g(_), T = [f(B)|_], B = b, N == 2.
test(33) :-
    nth1_once_else_0(N, L, f(a)), L = [f(A)|_], A = a, N == 1.
test(34) :-
    nth1_once_else_0(N, L, f(b)), L = [f(_)|_], N = 2, nth1(2, L, B), B == f(b).

:- end_tests(nth1_once_else_0).

Result:

?- run_tests.
% All 34 tests passed

Answer 4

Using a descriptive predicate name:

nth1_once_else_0(Elem, Lst, Nth1) :-
    % Start at element 1
    nth1_once_else_0_(Lst, Elem, 1, Nth1),
    % Stop after finding 1 solution
    !.
% Otherwise, succeed with 0
nth1_once_else_0(_Elem, _Lst, 0).

% Using Upto and Nth1 arguments, rather than unnecessary & slow recursion
nth1_once_else_0_([Elem|_], Elem, Nth1, Nth1).
nth1_once_else_0_([_|T], Elem, Upto, Nth1) :-
    % Loop through the list elements
    Upto1 is Upto + 1,
    nth1_once_else_0_(T, Elem, Upto1, Nth1).

Results in swi-prolog:

?- nth1_once_else_0(c, [a, b, c, a, b, c], Nth1).
Nth1 = 3.

?- nth1_once_else_0(z, [a, b, c, a, b, c], Nth1).
Nth1 = 0.

?- nth1_once_else_0(Char, [a, b, c, a, b, c], Nth1).
Char = a,
Nth1 = 1.

?- nth1_once_else_0(Char, [a, b, c, a, b, c], 2).
Char = b.

?- nth1_once_else_0(b, [a, b, c, a, b, c], 3).
false.

Below is an improved version:

nth1_once_else_0(Elem, Lst, Nth1) :-
    % Start at element 1
    nth1_once_else_0_(Lst, Elem, 1, Nth1),
    % Stop after finding 1 solution
    !.
% Otherwise, succeed with 0
nth1_once_else_0(_Elem, _Lst, 0).

% Using Upto and Nth1 arguments, rather than unnecessary & slow recursion
nth1_once_else_0_([Elem|_], Elem, Upto, Nth1) :-
    % Found first match on element
    !,
    Upto = Nth1.
nth1_once_else_0_([_|T], Elem, Upto, Nth1) :-
    % Loop through the list elements
    Upto1 is Upto + 1,
    nth1_once_else_0_(T, Elem, Upto1, Nth1).

... to prevent going past the first element match:

?- nth1_once_else_0(c, [a, b, c, a, b, c], 6).
false.

?- nth1_once_else_0(c, [a, b, c, a, b, c], Nth1).
Nth1 = 3.

?- nth1_once_else_0(z, [a, b, c, a, b, c], Nth1).
Nth1 = 0.