Please explain this example of Prolog recursion

Question

I'm learning Prolog and I'm having a hard time with recursion. The simple cases with a database I can understand, but I can't follow this exercise, where redu/2 is implemented, which will remove the duplicates of a given list and give the new list as second argument:

redu([],[]).

redu([H|T], Result):-
  member(H,T),
  redu(T,Result).

redu([H|T], [H|Result]):-
   redu(T, Result).

A trace gives me this:

[trace]  ?- redu([a,b,b,c,a], X).
   Call: (8) redu([a, b, b, c, a], _35630) ? creep
   Call: (9) lists:member(a, [b, b, c, a]) ? creep
   Exit: (9) lists:member(a, [b, b, c, a]) ? creep
   Call: (9) redu([b, b, c, a], _35630) ? creep
   Call: (10) lists:member(b, [b, c, a]) ? creep
   Exit: (10) lists:member(b, [b, c, a]) ? creep
   Call: (10) redu([b, c, a], _35630) ? creep
   Call: (11) lists:member(b, [c, a]) ? creep
   Fail: (11) lists:member(b, [c, a]) ? creep
   Redo: (10) redu([b, c, a], _35630) ? creep
   Call: (11) redu([c, a], _35900) ? creep
   Call: (12) lists:member(c, [a]) ? creep
   Fail: (12) lists:member(c, [a]) ? creep
   Redo: (11) redu([c, a], _35900) ? creep
   Call: (12) redu([a], _35906) ? creep
   Call: (13) lists:member(a, []) ? creep
   Fail: (13) lists:member(a, []) ? creep
   Redo: (12) redu([a], _35906) ? creep
   Call: (13) redu([], _35912) ? creep
   Exit: (13) redu([], []) ? creep
   Exit: (12) redu([a], [a]) ? creep
   Exit: (11) redu([c, a], [c, a]) ? creep
   Exit: (10) redu([b, c, a], [b, c, a]) ? creep
   Exit: (9) redu([b, b, c, a], [b, c, a]) ? creep
   Exit: (8) redu([a, b, b, c, a], [b, c, a]) ? creep
X = [b, c, a]

I would really appreciate it if somebody could explain to me in natural language what recursion does and how to read the clauses. Like with the second clause, is it right that it reads as "remove duplicates from list H|T and output Result if the head of that list is a member of the tail and remove the duplicates from the tail and output the result? But how can the two Results be the same? And I also don't get which rule is activated when. When does it go forward in my list of clauses? When does it go back?

Sorry for all the questions. I really want to understand everything.

your edit radically changes the question, and invalidates the answers. We are not supposed to do that on SO, so I'm going to roll it back. — Will Ness

Will Ness Will Ness · Accepted Answer · 2017-09-17T18:26:15

So you have

redu([], []).
redu([H|T],    R ):- member(H, T), redu(T, R).
redu([H|T], [H|R]):-               redu(T, R).
==
redu([], []).
redu([H|T], X ):-   member(H, T), X =    R , redu(T, R).
redu([H|T], X):-                  X = [H|R], redu(T, R).
==
redu([], []).
redu([H|T], X ):- ( member(H, T), X =    R 
                    ;             X = [H|R]), redu(T, R).
==
redu([], []).
redu([H|T], X ):- disj(H, T, X, R), redu(T, R).

disj(H, T,    R,  R):- member(H, T).
disj(H,_T, [H|R], R).

These two new redu/2 clauses are mutually exclusive, so the code can be easier to understand in this form. Whether disj/4 includes H into the list X being built (in the top-down manner) or not - and however many times it succeeds (*) - after disj/4 does its thing, the recursive call to redu/2 is simply made.

So we read redu(L,X) as "for the head element H in L=[H|T], if there are some more Hs in T, either don't include H in the 'output' list X, or do; and for a unique H - such that does not occur in T - include it in X always; and then, having dealt with this head element H of L, proceed to deal with the rest of the elements in the list in the same manner." In other words, do this for each element in the list L.

This recursive definition follows naturally the inductive definitions of lists as [H|T] or [] structures.

(*) (do take note that A. member may succeed more than once, and B. the two clauses of disj/4 are not mutually exclusive).

With your example,

redu([a,b,b,c,a], X)
==
disj( a, [b,b,c,a], X,R),             %  AND  redu([b,b,c,a], R)   i.e.
    disj( b, [b,c,a], R,R2),            %  AND  redu([b,c,a], R2)  i.e.
        disj( b, [c,a], R2,R3),           %  AND  redu([c,a], R3)  i.e.
            disj( c, [a],  R3,R4),          %  AND  redu([a], R4)  i.e.
                disj( a, [],  R4,R5),         %  AND  the final clause,
                   redu( [],     R5).

Now you can try each disj/4 invocation and see what is happening there, like

33 ?- disj(a,[b,b,c,a], X,R).
X = R ;
X = [a|R].

34 ?- disj(b,[c,a], R2,R3).
R2 = [b|R3].

Thus the whole example becomes

(X = R ; X = [a|R]),                          % [ a
    (R = R2 ; R = [b|R2]),                    %   b
         R2 = [b|R3],                         %   b
                 R3 = [c|R4],                 %   c
                         R4 = [a|R5],         %   a
                                 R5 = [].     % ]

or

ex(X):-
 (X = R ; X = [a|R]), 
     (R = R2 ; R = [b|R2]), 
          R2 = [b,c,a].

which is

42 ?- ex(X).
X = [b, c, a] ;
X = [b, b, c, a] ;
X = [a, b, c, a] ;
X = [a, b, b, c, a].

Please explain this example of Prolog recursion

2 Answers