Definite Logic Program

Question

The aim is to implement the predicate noDupl/2.

The first argument of this predicate is the list to analyze and second argument is the list of numbers which are no duplicate.

I could not understand code below and when I compiled it, it gave an error message that contained is undefined procedure, however as a hint it is written that we can use as predefined predicate contained and notContained. I think I need to define contained and notContained.

noDupl(XS, Res):-
   help( XS, [],Res).

help([],_,[]).
help([X|XS],Seen,[X|Res]):-
   notContained(X,XS),
   notContained(X,Seen), 
   help(XS, [X|Seen], Res).
help([X|XS],Seen,Res):-
   contained(X,Seen),
   help(XS, Seen, Res).
help([X|XS],Seen,Res):-
   contained(X,XS),
   help(XS, [X|Seen], Res).

Could someone please explain me the problem.

Answer 1

The missing definitions might be:

contained(X,[X|_]).
contained(X,[E|Es]) :-
   dif(X, E),
   contained(X, Es).

notContained(_X, []).
notContained(X, [E|Es]) :-
   dif(X, E),
   notContained(X, Es).

(I like to call these relations rather memberd/2 and non_member/2.)

The definition you gave extends the relation with an extra argument for the elements considered so far.

To understand the meaning of each clause, read each right-to-left in the direction of the arrow (the :- is a 1970's ASCII-fication of ←). Let's take the first rule:

Provided, that X is not an element of XS, and
provided, that X is not an element of Seen, and
provided, that help(X, [X|Seen], Res) is true,

---

then also help([X|XS],Seen,[X|Res]) is true.

In other words, if X is neither in the list of visited elements Seen nor in the elements yet to be visited XS, then it does not possess a duplicate.

What is a bit difficult to understand is whether or not the clauses you gave are mutually exclusive - this is, strictly speaking, not your concern, as long as you are only interested in declarative properties, but it is a good idea to avoid such redundancies.

Here is a case, where such redundancy shows:

?- noDupl([a,a,a],U).
   U = []
;  U = []
;  false.

Ideally, the system would give one determinate answer:

?- noDupl([a,a,a], U).
   U = [].

Personally, I do not like a lot to split things into too many cases. Essentially, we could have two: it is a duplicate, and it is none.

It is possible to provide a definition that is correct and still fully determinate for the cases where determinism is possible - such as when the first argument is "sufficiently instantiated" (which includes a ground list). Let's see if there are some answers into that direction.