CODEWITHSUNDEEP
listprolog
Cypher236
Cypher236

Reputation: 527

Could someone explain how exactly this predicate is working?

So I have the following predicate which takes a list of symbols as its first parameter, then outputs this list with all of the duplicates removed:

removeDups([], []).
removeDups([H|T], [H|T1]) :-
   subtract(T, [H], T2),
   removeDups(T2, T1).

It works as intended but I'm not exactly sure how to make sense of it.

What I've understood so far is:

  1. Obviously first the predicate is setup with two empty lists as parameters
  2. The Head and Tails of the lists are setup
  3. I don't understand what the subtract part is doing, it removes a tail value from the head value? And then stores it in a temporary variable T2?
  4. Then the temporary value of T2 is stored into T1?

I'm quite confused as to what exactly is going on here so any help would be really appreciated!

Upvotes: 1

Views: 79

Answers (2)

tas
tas

Reputation: 8140

The predicate subtract/3 describes a relation where the 3rd argument is the 1st argument without the elements of the 2nd argument, e.g.:

   ?- subtract([1,2,3],[1],L).
L = [2,3]
   ?- subtract([1,2,3],[1,2],L).
L = [3]

The first rule of removeDups/2 is the base case:

removeDups([],[]).

You can read it as: The empty list without duplicates is the empty list. The second rule is the general case of the relation, where the 1st list is not empty.

removeDups([H|T], [H|T1]) :-  % the head of list 1 is in the head of list 2
   subtract(T, [H], T2),      % T2 is the tail of list 1 without H
   removeDups(T2,T1).         % T1 is a duplicate free T2

So the goal with subtract/3 describes a list T2 that contains all elements but H of T. Since through the recursions the list T2 becomes shorter and shorter you inevitably end up with the base case []. And that is described by the first rule. Procedurally speaking you need the base case so your predicate can terminate. However, as pointed out by @repeat, the use of subtract/3 can be problematic if the first two arguments contain free variables. Consider the following examples:

   ?- X=1, subtract([1,2,3],[X],L).
L = [2,3],
X = 1
   ?- subtract([1,2,3],[X],L), X=1.
L = [2,3],
X = 1

But:

   ?- X=2, subtract([1,2,3],[X],L).
L = [1,3],
X = 2
   ?- subtract([1,2,3],[X],L), X=2.
no

So it's a good idea to test those arguments for sufficient instantiation as suggested by him in the comments:

removeDups([],[]).
removeDups([H|T], [H|T1]) :-
   safe_subtract(T, [H], T2),
   removeDups(T2,T1).

safe_subtract(As,Bs,Xs) :-
   ( ground(As+Bs) ->
     subtract(As,Bs,Xs) ;
     throw(error(instantiation_error,_))).

Upvotes: 2

gusbro
gusbro

Reputation: 22585

This procedure states that removeDups(L,L1):

  • clause1: should succeed if L and L1 both unify with empty lists
  • clause2: L and L1 are both lists with at least one element, the head of each list (H) unifies with the head of the other list, then subtract/3 is called with the tail of the list (T) from the first argument and a list comprising solely with the head. This procedure will unify the third argument (T2) with a list containing the elements of T without H. Then the recursive call to removeDups/3 applies the same algorithm to the resulting list (which does not have H). The recursive call has at least one element less than the original list L. Upon returning from the recursive call T1 should have no duplicates (and H won't be in it either). However as the third argument to removeDups is [H|T1] the caller will have in the third argument H as the head of the third list.

Upvotes: 1

Related Questions