I want to implement the predicate noDupl/2 in Prolog & have trouble with singleton variables

Question

My confusion mainly lies around understanding singleton variables.

I want to implement the predicate noDupl/2 in Prolog. This predicate can be used to identify numbers in a list that appear exactly once, i. e., numbers which are no duplicates. The first argument of noDupl is the list to analyze. The second argument is the list of numbers which are no duplicates, as described below. As an example, for the list [2, 0, 3, 2, 1] the result [0, 3, 1] is computed (because 2 is a duplicate). In my implementation I used the predefined member predicate and used an auxiliary predicate called helper.

I'll explain my logic in pseudocode, so you can help me spot where I went wrong.

1. First off, If the first element is not a member of the rest of the list, add the first element to the new result List (as it's head).
2. If the first element is a member of T, call the helper method on the rest of the list, the first element H and the new list.

3. Helper method, if H is found in the tail, return list without H, i. e., Tail.

   noDupl([],[]).
   noDupl([H|T],L) :-
      \+ member(H,T),
       noDupl(T,[H|T]).
   noDupl([H|T],L) :-
      member(H,T),
      helper(T,H,L).
   
   helper([],N,[]).
   helper([H|T],H,T). %found place of duplicate & return list without it
   helper([H|T],N,L) :-
      helper(T,N,[H|T1]).%still couldn't locate the place, so add H to the new List as it's not a duplicate
   

While I'm writing my code, I'm always having trouble with deciding to choose a new variable or use the one defined in the predicate arguments when it comes to free variables specifically. Thanks.

Answer 1

Warnings about singleton variables are not the actual problem.

Singleton variables are logical variables that occur once in some Prolog clause (fact or rule). Prolog warns you about these variables if they are named like non-singleton variables, i. e., if their name does not start with a _.

This convention helps avoid typos of the nasty kind—typos which do not cause syntax errors but do change the meaning.

---

Let's build a canonical solution to your problem.

First, forget about CamelCase and pick a proper predicate name that reflects the relational nature of the problem at hand: how about list_uniques/2?

Then, document cases in which you expect the predicate to give one answer, multiple answers or no answer at all. How? Not as mere text, but as queries.

Start with the most general query:

?- list_uniques(Xs, Ys).

Add some ground queries:

?- list_uniques([], []).
?- list_uniques([1,2,2,1,3,4], [3,4]).
?- list_uniques([a,b,b,a], []).

And add queries containing variables:

?- list_uniques([n,i,x,o,n], Xs).
?- list_uniques([i,s,p,y,i,s,p,y], Xs).

?- list_uniques([A,B], [X,Y]).
?- list_uniques([A,B,C], [D,E]).
?- list_uniques([A,B,C,D], [X]).

Now let's write some code! Based on library(reif) write:

:- use_module(library(reif)).

list_uniques(Xs, Ys) :-
   list_past_uniques(Xs, [], Ys).

list_past_uniques([], _, []).           % auxiliary predicate
list_past_uniques([X|Xs], Xs0, Ys) :-
   if_((memberd_t(X,Xs) ; memberd_t(X,Xs0)),
       Ys = Ys0,
       Ys = [X|Ys0]),
   list_past_uniques(Xs, [X|Xs0], Ys0).

What's going on?

• list_uniques/2 is built upon the helper predicate list_past_uniques/3

• At any point, list_past_uniques/3 keeps track of:

  • all items ahead (Xs) and
  • all items "behind" (Xs0) some item of the original list X.

• If X is a member of either list, then Ys skips X—it's not unique!

• Otherwise, X is unique and it occurs in Ys (as its list head).

Let's run some of the above queries using SWI-Prolog 8.0.0:

?- list_uniques(Xs, Ys).
   Xs = [], Ys = []
;  Xs = [_A], Ys = [_A]
;  Xs = [_A,_A], Ys = []
;  Xs = [_A,_A,_A], Ys = []
...

?- list_uniques([], []).
true.
?- list_uniques([1,2,2,1,3,4], [3,4]).
true.
?- list_uniques([a,b,b,a], []).
true.

?- list_uniques([1,2,2,1,3,4], Xs).
Xs = [3,4].
?- list_uniques([n,i,x,o,n], Xs).
Xs = [i,x,o].
?- list_uniques([i,s,p,y,i,s,p,y], Xs).
Xs = [].

?- list_uniques([A,B], [X,Y]).
A = X, B = Y, dif(Y,X).
?- list_uniques([A,B,C], [D,E]).
false.
?- list_uniques([A,B,C,D], [X]).
   A = B, B = C, D = X, dif(X,C)
;  A = B, B = D, C = X, dif(X,D)
;  A = C, C = D, B = X, dif(D,X)
;  A = X, B = C, C = D, dif(D,X)
;  false.