Index of Element 1

[avish12]

Hi,

I'm new here and with Prolog.
I have done some searching for several hours, including going over some useful threads in this forum, yet did not manage to find an example of the somewhat simple task in arrays: find the index of a given element in a list,
meaning:
index(List, Element, Index) where Index will be assigned with the index of element Element in list List.

Thanks in advance,
Avishay

 

[kahleen]

Your problem is solved easily by using the nth0 predicate in SWI-Prolog

Just type help(nth0) at the SWI-Prolog prompt and you will find out how to use it.

 

[avish12]

Wow do I feel stupid...
I have seen this predicate but didn't make the connection that if Index is left without a concrete value, it will return with the answer...
Thanks

 

[kahleen]

No need to feel stupid. We're here to learn from each other.

PS: There is also nth1 that counts indexes from 1 ...

 

[avish12]

Well, I seem to need more help in the problem which is the reason for my first question.

I want to write remove_elem(L, X, Ans), where Ans will get the list L after all element X's occurrences has been removed from it.
for example: remove_elem([6,5], 5, Ans) will cause Ans = [6].

I don't have an idea of how to do it directly, so I use a help method, remove_at(L, K, Ans), that removes the K'th element in L.

remove_at([X|Xs],1,Xs).
remove_at([Y|Xs],K,[Y|Ys]) :- K > 1,
K1 is K - 1, remove_at(Xs,K1,Ys).

So, my thinking was to do:
remove_elem([], _, []) :- !.
remove_elem(L, X, Ans) :-
nth1(Index, L, X),
remove_at(L, Index, Ans).

But it just doesn't work....
I guess for you, Prolog experts, it's right away clear what's my misunderstanding and where's the fix...
Please help me here
Thanks!

 

[kahleen]

Ok, your code deletes only one occurrence of the desired element. The nth1 predicate gives you the positions where some element X lies within a list, but it gives those positions one by one, not all at once. Each possibility for nth1 gives a new solution for the overall remove_elem predicate. So if an element X appears twice in a list, nth1 will offer 2 solutions and with each of them you go further to remove_at and get a separate overall solution

If you want to go with this solution of finding the position of X and then deleting the element at that position, what you need is to not let Prolog reach the end of remove_elem until you are sure you've deleted all the occurrences. You need to make remove_elem recursive ... find out the position of X using nth1 and:
- on success, remove that occurrence and make a recursive call to continue with the other occurrences, if there are
- on failure, there is no occurrence of X within the list so stop

remove_elem(L, X, Ans) :-
	nth1(Index, L, X), !,
	remove_at(L, Index, L_Without_First_X),
	remove_elem(L_Without_First_X, X, Ans).

remove_elem(L, _, L).

If nth1 succeeds (X exists in L), then the "!" symbol masks the last rule (like it doesn't exist at all in this step) and we go with the algorithm: delete first occurrence of X, then make a recursive call to delete the others

If nth1 fails (X does not exist in L) then the last rule comes in handy stating that the result is the entire list L.

PS: remove_at remains untouched since it works fine

 

[avish12]

That's great!
You've helped me a lot, I definitely starting to feel like I understand logic programming's concepts.
Thanks a lot!

 

[kahleen]

Just for the record, traversing the list to find the position of an element in it and then traversing the list again from the beginning to delete the element at that position will issue a bad performance on large lists. And that's only for one occurrence of the desired element, other occurrences will make the whole process restart.

It's great that you made it work this way, but maybe the actual solution that traverses the list only once (no matter how many occurrences of the desired element there are) will help you even more. Here it is:

remove_elem([], _, []).
remove_elem([Element | Rest], Element, Result) :-
	!,
	remove_elem(Rest, Element, Result).
remove_elem([X | Rest], Element, [X | Result]) :-
	remove_elem(Rest, Element, Result).

 

[avish12]

Thanks again