SWI-Prolog predicate example part 2

Question

Can someone please help me in transforming this to match this updated requirement?

Define a predicate strikeDuplicates(X,Y) that succeeds if and only the list Y would be obtained if one were to remove the second and subsequent occurrences of each element from list X. (You might read strikeDuplicates (X,Y) as list X without duplicates is list Y.) The strikeDuplicates/2 predicate need not work well when X is an unbound variable.

I asked a similar question two days ago asking this:

Define a predicate strike(X,Y,Z) that succeeds if and only if the list Z would be obtained if one were to remove all occurrences of element X from list Y. The strike/3 predicate need not work well when Y is an unbound variable.

No one helped me so I had to do it by myself. That answer was this:

strike( _ , []    , []    ) .
strike( X , [X|T] , Z     ) :-            strike(X,T,Z) .
strike( X , [A|T] , [A|Z] ) :- dif(X,A) , strike(X,T,Z) .

dif(X,A).

Answer 1

A simple solution that doesn't preserve order is:

strike_duplicates([], []).
strike_duplicates([X| Xs], List) :-
    (   member(X, Xs) ->
        strike_duplicates(Xs, List)
    ;   List = [X| Tail],
        strike_duplicates(Xs, Tail)
    ).

To preserve order, you need to keep track of the elements found so far while you traverse the list. A solution would be:

strip_duplicates(List, Set) :-
    strip_duplicates(List, [], Set).

strip_duplicates([], _, []).
strip_duplicates([X| Xs], Found, List) :-
    (   member(X, Found) ->
        strip_duplicates(Xs, Found, List)
    ;   List = [X| Tail],
        strip_duplicates(Xs, [X| Found], Tail)
    ).

The predicate member/2 is usually either a built-in predicate or available as a library predicate. Check your Prolog system documentation if necessary.

Answer 2

Well, the easy way would be to use the built-in predicate setof/3, but I suspect that's not what your professor wants.

Think about the problem for a second or two. A clear problem statement is often helpful (and in Prolog is often the solution itself):

To make the source list a set (unique elements) instead of a bag (allows duplication), you'll have to

• Iterate over the source list
• Track items you've already seen (the 'visited' list)
• Add each item to the visited list only if the visited list doesn't already contain it.

Once you've done that you've got the desired result.

Here's a hint: a very common prolog idiom is the use of helper predicates that carry with it an accumulator. Often the helper predicate has the same functor, but a different arity. For example, to sum the values in a list (sum/2) we can use a helper sum/3 that carries an accumulator, seeded with 0:

sum(Xs,N) :- sum(Xs,0,N).

sum([],S,S).
sum([N|Ns],T,S) :-
  T1 is T+N,
  sum(Ns,T1,S)
  .

You'll notice how unfication with the result is deferred until the final value has been computed.

You need to do something like that but using as an accumulator an [empty] list that will be extended with the unique values you discover.

Another hint: the built-in predicate member/2 will check if a term is a member of a list. It's written

member(X,[X|Xs]).
member(X,[_|Xs]) :- member(X,Xs).

So member(2,[1,2,3]) is true whilst member(2,[1,3]) is false.

Conversely, one can use member/2 to successively return each element of a list via backtracking: member(X,[1,2,3]) produces

X = 1 ;
X = 2 ;
X = 3 ;
false

Given those two notions, you should be able to figure out the solution. Come back and show us your code and we can help you. There is one other little gotcha, but I'm sure you'll figure it out.