Finding Unique Items in a List

by

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) :-
   iwhen(ground(X+Xs), your_unique(X, Xs)).

This uses iwhen/2 which is similar to when/2 except that it does not delay:

:- meta_predicate iwhen(+, 0).

iwhen(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:

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

More Related Contents:

  1. Prolog map procedure that applies predicate to list elements
  2. What is the difference between ‘ and ” in Prolog?
  3. Definition of a path/trail/walk
  4. Definition of Reflexive Transitive Closure
  5. Most general higher-order constraint describing a sequence of integers ordered with respect to a relation
  6. Delete vowels in a list
  7. Reification of term equality/inequality
  8. Prolog successor notation yields incomplete result and infinite loop
  9. Prolog: a person is a sibling of himself?
  10. What is the logical ‘not’ in Prolog?
  11. Stack overflow in Prolog DCG grammar rule: how to handle large lists efficiently or lazily
  12. Using a constrained variable with `length/2`
  13. Einsteins Riddle Prolog
  14. Safer type tests in Prolog
  15. Complexity of ISO Prolog predicates
  16. Explanation of a Prolog algorithm to append two lists together
  17. list of the values in the leaf nodes of binary tree T
  18. Meaning of instantiation mode indicators in arguments of Prolog predicates
  19. reversible “binary to number” predicate
  20. Collect all “minimum” solutions from a predicate
  21. Using \==/2 or dif/2
  22. Knowing when to use cut in prolog
  23. Good beginners material on Prolog [closed]
  24. ‘if’ in prolog?
  25. Should I avoid tail recursion in Prolog and in general?
  26. Prolog append with cut operator
  27. Define graph in Prolog: edge and path, finding if there is a path between two vertices
  28. Can you write between/3 in pure prolog?
  29. PROLOG: Determining if elements in list are equal if order does not matter
  30. GNU Prolog assert error

Leave a Comment