I am completely new to Prolog and trying some exercises. One of them is:
Write a predicate set(InList,OutList) which takes as input an arbitrary list, and returns a list in which each element of the input list appears only once.
Here is my solution:
member(X,[X|_]).
member(X,[_|T]) :- member(X,T).
set([],[]).
set([H|T],[H|Out]) :-
not(member(H,T)),
set(T,Out).
set([H|T],Out) :-
member(H,T),
set(T,Out).
I'm not allowed to use any of built-in predicates (It would be better even do not use not/1
). The problem is, that set/2
gives multiple same solutions. The more repetitions in the input list, the more solutions will result. What am I doing wrong? Thanks in advance.
This predicate can be used to select an element from a list, delete an element or insert it. The definition of this Prolog library predicate is: delete(A, [A|B], B). delete(A, [B, C|D], [B|E]) :- delete(A, [C|D], E).
You are getting multiple solutions due to Prolog's backtracking. Technically, each solution provided is correct, which is why it is being generated. If you want just one solution to be generated, you are going to have to stop backtracking at some point. This is what the Prolog cut is used for. You might find that reading up on that will help you with this problem.
Update: Right. Your member()
predicate is evaluating as true
in several different ways if the first variable is in multiple positions in the second variable.
I've used the name mymember()
for this predicate, so as not to conflict with GNU Prolog's builtin member()
predicate. My knowledge base now looks like this:
mymember(X,[X|_]).
mymember(X,[_|T]) :- mymember(X,T).
not(A) :- \+ call(A).
set([],[]).
set([H|T],[H|Out]) :-
not(mymember(H,T)),
set(T,Out).
set([H|T],Out) :-
mymember(H,T),
set(T,Out).
So, mymember(1, [1, 1, 1]).
evaluates as true
in three different ways:
| ?- mymember(1, [1, 1, 1]).
true ? a
true
true
no
If you want to have only one answer, you're going to have to use a cut. Changing the first definition of mymember()
to this:
mymember(X,[X|_]) :- !.
Solves your problem.
Furthermore, you can avoid not()
altogether, if you wish, by defining a notamember()
predicate yourself. The choice is yours.
A simpler (and likely faster) solution is to use library predicate sort/2 which remove duplicates in O(n log n). Definitely works in Yap prolog and SWIPL
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With