Finding Unique Items in a List

Question

I'm trying to write a rule which decides whether an item X occurs exactly one in a list L.

unique(X, [X|T]):- !, \+ member(X, T).
unique(X, [_|T]):- unique(X, T).

The rule works for determining whether a value is unique within a list or nor, but when I try to get unique values within a list using unique(X, [1,2,3,1,3,2,5,4,3,8]). it returns just false. What I expected is this (like member(X, list).:

X = 5 ;
X = 4 ;
X = 8 ;

I'm a complete beginner and I don't know what I am doing wrong.

Answer 1

You have been using cut and an unsafe form of negation. Both have to be used with extreme care. An immediate fix would be to guard your program against uses it is not designed for:

unique(X, Xs) :-
   when_si(ground(X+Xs), your_unique(X, Xs)).

This uses when_si/2 (formerly called iwhen/2) which is similar to when/2 except that it does not delay:

:- meta_predicate(when_si(+, 0)).

when_si(Cond, G_0) :-
   when(Cond, ( Called = true, G_0 ) ),
   ( var(Called) -> throw(error(instantiation_error,_)) ; true ).

Above works for systems providing when/2. Below is for any ISO conforming system:

when_si(Cond, G_0) :-
   (  when_condition(Cond)
   -> ( Cond -> G_0 ; throw(error(instantiation_error,_)) )
   ;  throw(error(domain_error(when_condition, Cond),_))
   ).

when_condition(C) :-
   var(C),
   !,
   throw(error(instantiation_error,_)).
when_condition(ground(_)).
when_condition(nonvar(_)).
when_condition(?=(_, _)).
when_condition(( A, B )) :-
   when_condition(A),
   when_condition(B).
when_condition(( A ; B )) :-
   when_condition(A),
   when_condition(B).

On the other hand, it gets quite frustrating receiving instantiation errors all the time instead of real answers. So, let's make your program really pure!

Your second rule

unique(X, [_|Es]) :-
   unique(X, Es).

reads declaratively, right-to-left (that :- is an ←)

Provided X is a unique element of the list Es, then X is a unique element of the list [_|Es].

in other words: Whenever I know that X is unique in Es, it will be also unique with any further element in Es. That conclusion is not true, consider to extend the list by X! You need some extra condition. Also, your first rule needs to be reformulated. This uses non_member/2:

unique(X, [X|Es]) :-
   non_member(X, Es).
unique(X, [E|Es]) :-
   dif(X, E),
   unique(X, Es).

And here is another way using tfilter/3:

unique(X, Es) :-
   tfilter(=(X), Es, [_]).

The most efficient is probably the following which uses if_/3 of library(reif):

unique(X, [E|Es]) :-
   if_(X = E, non_member(E, Es), unique(X, Es) ).

Answer 2

Here is a simple solution using nth0/4 (or select/3 as pointed out by @false):

unique(X, L) :-
    nth0(_, L, X, R),
    \+ member(X, R).

nth0/4 4th argument R is the list L with the element X removed. We simply check then that X is not in R.

Better version

unique(X, L) :-
    nth0(_, L, X, R),
    maplist(dif(X), R).

This fixes the problem pointed out by @false, though since you are a beginner I doubt this is of much interest to you.

This has the advantage of working in situations like this one:

?- unique(b, [X, Y, a]).
X = b,
dif(Y, b) ;
Y = b,
dif(X, b) ;
false.

Answer 3

This sounds like a homework question.

Try something like this.

unique(M, L) :- member(M, L), count(M, L, 1).  
count(M, [H|T], C) :- M = H, count(M, T, C1), C is C + 1.
...

When completed this gives...

?- unique(X, [1,2,3,1,3,2,5,4,3,8]).
X = 5 ;
X = 4 ;
X = 8 ;
false.

Edit: Since answers have already been given... here's the slick one.

unique(Item, List) :-
  select(Item, List, L2),
  \+ member(Item, L2).

Answer 4

Easy and pure method:

unique_elem_in_list(Elem, Lst) :-
    select(Elem, Lst, Rem),
    maplist(dif(Elem), Rem).

Result in swi-prolog:

?- unique_elem_in_list(E, [A,B,C]).
E = A,
dif(A, B),
dif(A, C) ;
E = B,
dif(B, A),
dif(B, C) ;
E = C,
dif(C, A),
dif(C, B).