1

I'm new to Prolog and I am trying to understand it.

I started with some simple program, this one should:

  • check if an element is contained in the rest of the list
    • if FALSE do nothing
    • if TRUE add it to a second list. (only one occurrence of a char should be added to the second list).

Some examples with expected results:

?- occ([a,b,c,a,a,b,e,f,g], Y).
Y = [a,b].

?- occ([a,a,a,a,a], Y).
Y = [a].

?- occ([a,b,c,d,e,f,g], Y).
Y = [].

Here's the code I wrote, but I have some problems (it always returns true).

occ([],[]).
occ([],_Y).
occ([X|Xs],[X|Y]) :-
   occ(Xs,Y),
   member(X,Xs),
   not(member(X,Y)),
   !.
occ([_X|_Xs],_Y).

I tried using the debugger and I found that the not(member(X,Y)) is always false and in the binding section there is only X and Xs and never Y. Any advice is much appreciated! Thank you.

UPDATE

I think I solved it, here's the code:

occ([],[]).
occ([X|Xs],[X|Y]) :-
   occ(Xs,Y),
   member(X,Xs),
   not(member(X,Y)),
   !.
occ([_X|_Xs],[]).

But I'm not really sure why it works now... in the 3-th occ I changed the _Y with [].. But why does it change the results?

repeat
  • 18,496
  • 4
  • 54
  • 166
Marcx
  • 6,806
  • 5
  • 46
  • 69
  • 1
    Your predicate always returns true because you have two clauses that, together, will accept any list arguments and succeed. `occ([], _Y).` will always succeed no matter what the second argument is if the first argument is the empty list `[]`. And `occ([_X|_Y], _Y).` will always succeed if the first argument is a list of at least one element, and no matter what the second argument is. What you want to do is make sure each clause makes sense on its own as far as expressing a valid rule about its arguments. – lurker Nov 26 '15 at 13:13
  • I tried changing my code but I could not achieve what I was expecting... could you please help me a little more? I think i'm missing something.. – Marcx Nov 26 '15 at 14:02
  • It could help if you edit your question with your latest changes to know where your current thinking is. – lurker Nov 26 '15 at 14:03
  • I updated my question, and I probably solved it... although I haven't really understood why it works now... can you better explain it to me please? edit2: i'm not sure it always works :\ – Marcx Nov 26 '15 at 15:31
  • I think it still has an issue. Your 3rd rule basically says *any* non-empty list should yield an empty list, which should not be true. Can you explain why you have that rule? Any rule you have you should be able to describe in words. That is what will help you understand your solution. Your first rule says, *The result of an empty list is the empty list* which certainly makes sense. Your 2nd rule says, *`[X|Y]` is the result of `[X|Xs]` if `Y` is the result of `Xs`, and `X` is a member of `Xs`, and `X` is not a member of `Y`*. – lurker Nov 26 '15 at 15:36

1 Answers1

2

In this answer we use tpartition/4 in combination with if_/3 and (=)/3.

We define list_duplicateset/2 like this:

list_duplicateset([], []).
list_duplicateset([E|Xs0], Ys0) :-
   tpartition(=(E), Xs0, Es, Xs),
   if_(Es = [],
       Ys0 = Ys,
       Ys0 = [E|Ys]),
   list_duplicateset(Xs, Ys).

First, we run a sample query taken from this answer to a similar question:

?- list_duplicateset([1,2,2,3,4,5,7,6,7], Xs). 
Xs = [2,7].

Next, let's run the queries the OP gave:

?- list_duplicateset([a,b,c,a,a,b,e,f,g], Xs).
Xs = [a, b].

?- list_duplicateset([a,a,a,a,a], Xs).
Xs = [a].

?- list_duplicateset([a,b,c,d,e,f,g], Xs).
Xs = [].

Note that all queries presented above give the expected answers and succeed deterministically.

Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166