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.

Bradshaw

Found this: computer-programming-forum.com/55-prolog/d2b17b566dad6b41.htm – Bradshaw

Answer 1

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.

Weighty

@Pulsar Added an improved version. – Weighty

Your second version is very nice because it just reuses existing recursive predicates, but is not itself recursive. However, there is a (procedural) price to pay for this elegance! unique(a,[a,a|_]) does not terminate. – Pulsar

@Pulsar Yes, it has problems if L is not sufficiently ground. Your version is the better implementation, though this one is much more readable for a beginner while working for an acceptable subset of possible situations. – Weighty

Minor comment: select(X, L, R) is more common (I did not know nth0/4 at all). – Pulsar

Answer 2

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) ).

Pulsar

Probably overkill for a beginner, but this is good reference for a "correct" implementation of this. – Weighty

@Fatalize: The only overkill I see is that iwhen/2 is not readily available. – Pulsar

The 2nd implementation of iwhen/2 should probably test acyclic_term(Cond) and throw an error(type_error(acyclic_term, Cond), _) in case of failure. – Hinshaw

@repeat: Not sure - why should acyclic terms be specific to iwhen/2? – Pulsar

when/2 reports an error in case the condition is a cyclic term. So does the 1st implementation of iwhen/2... shouldn't the 2nd implementation behave the same? – Hinshaw

@repeat: Which when/2 are you referring to? X = s(X), when(ground(X),false). just fails – Pulsar

I'm talking about conditions like in C = (C,C), when(C, false). or C = (C ; bad). when/2 rejects these, so should iwhen/2 (2nd impl). – Hinshaw

I was wrong, at least in part. It's not quite as easy as I saw it... Some cyclic terms should be rejected, others must be permitted. – Hinshaw

@repeat: I only see this error in SWI, but not in SICStus 4.41 – Pulsar

@repeat: only C=(C,C),when(C,false) in error in SWI, but not in SICStus 4.4.1- is 4.5 better? Difficult to give it a good error. Still, type_error(callable,(C,C)) per analogiam 7.8.3.3 c seems more appropriate. – Pulsar

SICStus 4.5.0 is no different here than 4.4.1. Actually, the error given by SWI (type error acyclic_term expected) confused me. – Hinshaw

Rather something like when_condition(Cond, _) :- var(Cond), !, throw(error(instantiation_error,_)). when_condition(ground(_), _). when_condition(nonvar(_), _). when_condition(?=(_, _), _). when_condition(Cond, Conds0) :- ( Cond = ( A, B ) -> true ; Cond = ( A ; B ) ), ( member(Cond0, Conds0), Cond0 == Cond -> false /* TODO: raise proper error */ ; Conds = [Cond|Conds0], when_condition(A, Conds), when_condition(B, Conds) ). – Hinshaw

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).

Multiflorous

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).

Reticent