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.

Answer 2

Just like my previous answer, the following answer is based on library(reif)—and uses it in a somewhat more idiomatic way.

:- use_module(library(reif)).

list_uniques([], []).
list_uniques([V|Vs], Xs) :-
   tpartition(=(V), Vs, Equals, Difs),
   if_(Equals = [], Xs = [V|Xs0], Xs = Xs0),
   list_uniques(Difs, Xs0).

While this code does not improve upon my previous one regarding efficiency / complexity, it is arguably more readable (fewer arguments in the recursion).

Answer 3

In this solution a slightly modified version of tpartition is used to have more control over what happens when an item passes the condition (or not):

tpartition_p(P_2, OnTrue_5, OnFalse_5, OnEnd_4, InitialTrue, InitialFalse, Xs, RTrue, RFalse) :-
   i_tpartition_p(Xs, P_2, OnTrue_5, OnFalse_5, OnEnd_4, InitialTrue, InitialFalse, RTrue, RFalse).

i_tpartition_p([], _P_2, _OnTrue_5, _OnFalse_5, OnEnd_4, CurrentTrue, CurrentFalse, RTrue, RFalse):-
  call(OnEnd_4, CurrentTrue, CurrentFalse, RTrue, RFalse).
i_tpartition_p([X|Xs], P_2, OnTrue_5, OnFalse_5, OnEnd_4, CurrentTrue, CurrentFalse, RTrue, RFalse):-
   if_( call(P_2, X)
      , call(OnTrue_5, X, CurrentTrue, CurrentFalse, NCurrentTrue, NCurrentFalse)
      , call(OnFalse_5, X, CurrentTrue, CurrentFalse, NCurrentTrue, NCurrentFalse) ),
   i_tpartition_p(Xs, P_2, OnTrue_5, OnFalse_5, OnEnd_4, NCurrentTrue, NCurrentFalse, RTrue, RFalse).

InitialTrue/InitialFalse and RTrue/RFalse contains the desired initial and final state, procedures OnTrue_5 and OnFalse_5 manage state transition after testing the condition P_2 on each item and OnEnd_4 manages the last transition.

With the following code for list_uniques/2:

list_uniques([], []).
list_uniques([V|Vs], Xs) :-
   tpartition_p(=(V), on_true, on_false, on_end, false, Difs, Vs, HasDuplicates, []),
   if_(=(HasDuplicates), Xs=Xs0, Xs = [V|Xs0]),
   list_uniques(Difs, Xs0).


on_true(_, _, Difs, true, Difs).

on_false(X, HasDuplicates, [X|Xs], HasDuplicates, Xs).

on_end(HasDuplicates, Difs, HasDuplicates, Difs).

When the item passes the filter (its a duplicate) we just mark that the list has duplicates and skip the item, otherwise the item is kept for further processing.

Answer 4

This answer goes similar ways as this previous answer by @gusbro.

However, it does not propose a somewhat baroque version of tpartition/4, but instead an augmented, but hopefully leaner, version of tfilter/3 called tfilter_t/4 which can be defined like so:

tfilter_t(C_2, Es, Fs, T) :-
   i_tfilter_t(Es, C_2, Fs, T).

i_tfilter_t([], _, [], true).
i_tfilter_t([E|Es], C_2, Fs0, T) :-
   if_(call(C_2,E), 
       ( Fs0 = [E|Fs], i_tfilter_t(Es,C_2,Fs,T) ),
       ( Fs0 = Fs, T = false, tfilter(C_2,Es,Fs) )).

Adapting list_uniques/2 is straightforward:

list_uniques([], []).
list_uniques([V|Vs], Xs) :-
   if_(tfilter_t(dif(V),Vs,Difs), Xs = [V|Xs0], Xs = Xs0),
   list_uniques(Difs, Xs0).

Save scrollbars. Stay lean! Use filter_t/4.

Answer 5

You have problems already in the first predicate, noDupl/2.

The first clause, noDupl([], []). looks fine. The second clause is wrong.

noDupl([H|T],L):-
    \+member(H,T),
    noDupl(T,[H|T]).

What does that really mean I leave as an exercise to you. If you want, however, to add H to the result, you would write it like this:

noDupl([H|T], [H|L]) :-
    \+ member(H, T),
    noDupl(T, L).

Please look carefully at this and try to understand. The H is added to the result by unifying the result (the second argument in the head) to a list with H as the head and the variable L as the tail. The singleton variable L in your definition is a singleton because there is a mistake in your definition, namely, you do nothing at all with it.

The last clause has a different kind of problem. You try to clean the rest of the list from this one element, but you never return to the original task of getting rid of all duplicates. It could be fixed like this:

noDupl([H|T], L) :-
    member(H, T),
    helper(T, H, T0),
    noDupl(T0, L).

Your helper/3 cleans the rest of the original list from the duplicate, unifying the result with T0, then uses this clean list to continue removing duplicates.

Now on to your helper. The first clause seems fine but has a singleton variable. This is a valid case where you don't want to do anything with this argument, so you "declare" it unused for example like this:

helper([], _, []).

The second clause is problematic because it removes a single occurrence. What should happen if you call:

?- helper([1,2,3,2], 2, L).

The last clause also has a problem. Just because you use different names for two variables, this doesn't make them different. To fix these two clauses, you can for example do:

helper([H|T], H, L) :-
    helper(T, H, L).
helper([H|T], X, [H|L]) :-
    dif(H, X),
    helper(T, X, L).

These are the minimal corrections that will give you an answer when the first argument of noDupl/2 is ground. You could do this check this by renaming noDupl/2 to noDupl_ground/2 and defining noDupl/2 as:

noDupl(L, R) :-
    must_be(ground, L),
    noDupl_ground(L, R).

Try to see what you get for different queries with the current naive implementation and ask if you have further questions. It is still full of problems, but it really depends on how you will use it and what you want out of the answer.