List containing indexes of equal elements

Question

I'm trying to define a predicate that takes 3 lists as parameters and the third list contains the indexes where the elements in the other two lists are the same.

This is my attempt at solving the problem.

sameIndex(List1, List2, List3) :- findIndex(List1,List2,0, List3).

% Helper Function 

% Base cases
findIndex([],_,_,[]).
findIndex(_,[],_,[]).

findIndex([Head1|Tail1], [Head2|Tail2], Count, List4):-
    Head1 == Head2, append([Count], List4, FinalList), NewCount is Count+1,
    findIndex(Tail1,Tail2,NewCount,FinalList); NewCount is Count+1,
    findIndex(Tail1,Tail2,NewCount, List4).

Sample test case:

sameIndex([1,2,3,4], [6,2,4,4], List)

should return

List = [1,3]

My logic is : if the heads of the lists are equal then append Count (keeps track of the index we're at) to our empty List4, increment Count, and recursively call the predicate with the tails of the two lists. Otherwise, increment Count and recursively call the predicate with the tails.

I'm assuming my code has improper use of arithmetic in prolog but I just can't get it to work. Any suggestions/help is appreciated.

What you need here is an accumulator pattern, such that at each recursive step you're building a list of valid indices that is then passed to the next step. Your List4 should then be something that gets unified to the accumulated list once you've reached the base case. The way you're doing it here, List4 is whatever you passed in initially, and then stuff gets appended to it, which is not what you want. Let alone that, even if you call it with a variable, you never attempt to unify List4 with anything. — Tasos Papastylianou

CapelliC CapelliC · Accepted Answer · 2017-04-11T05:55:27

Here is your code corrected - and reformatted, using 'standard' indentation

findIndex([Head1|Tail1], [Head2|Tail2], Count, List4):-
    ( Head1 == Head2,
      append([Count], FinalList, List4),
      NewCount is Count+1,
      findIndex(Tail1,Tail2,NewCount,FinalList)
    ; NewCount is Count+1,
      findIndex(Tail1,Tail2,NewCount, List4)
    ).

Your error was to invert the arguments to append/3. Another problem it's returning multiple solutions - some of them wrong, so you should use the if/then/else construct, and discriminate the 2 base cases:

findIndex([],_,_,[]) :- !.
findIndex(_,[],_,[]).

findIndex([Head1|Tail1], [Head2|Tail2], Count, List4):-
    ( Head1 == Head2
    ->append([Count], FinalList, List4),
      NewCount is Count+1,
      findIndex(Tail1,Tail2,NewCount,FinalList)
    ; NewCount is Count+1,
      findIndex(Tail1,Tail2,NewCount, List4)
    ).

But the code can be far simpler, using some library helpers:

sameIndex(List1, List2, List3) :-
  findall(P, (nth0(P,List1,E), nth0(P,List2,E)), List3).

Differently from your solution, this one will work for any length lists...

List containing indexes of equal elements

1 Answers