How does recursion in Prolog works from inside. One example

Question

I've got here a small script, that converts list of elements into a set. For example list [1,1,2,3] -> set [1,2,3]. Can somebody explain to me, step by step, whats happening inside those procedures? Can you please use my [1,1,2,3] -> [1,2,3] example?

list_to_set([],[]).

list_to_set([A|X],[A|Y]):-
   list_to_set(X,Y),
    \+member(A,Y).

list_to_set([A|X],Y):-
   list_to_set(X,Y),
   member(A,Y).

Answer 1

If you look at a concrete example, you will soon be buried in lots of irrelevant detail. So much, that you will lose sight for the important properties of your program. Let's have a look at the following program fragment instead which is called a failure slice. You get a failure slice by adding goals false into your program. Failure slices share many interesting properties with the original program. For example, a goal Goal, false executed with the failure slice will never use more inferences than the original program. Or conversely, the original program will use more (or at best the same number of) inferences. So, let me point out one such slice:

list_to_set([],[]) :- false.
list_to_set([A|X],[A|Y]):-
   list_to_set(X,Y), false,
    \+member(A,Y).
list_to_set([A|X],Y):-
   list_to_set(X,Y), false,
   member(A,Y).

And since this fragment is no longer interested in concrete elements (the A is no longer used, nor member/2), we can use length/2 for the most general lists. In this manner we can observe the minimal number of inferences needed for every length like so:

?- length(L, N), call_inferences((list_to_set(L,_),false;true),Inf).
   N = 0, Inf = 3
;  N = 1, Inf = 6
;  N = 2, Inf = 12
;  N = 3, Inf = 24
;  N = 4, Inf = 48
;  N = 5, Inf = 96
;  N = 6, Inf = 192
;  N = 7, Inf = 384
;  N = 8, Inf = 768
;  N = 9, Inf = 1536
;  N = 10, Inf = 3072
;  ... .

Using

:- meta_predicate(user:call_inferences(0,-)).
call_inferences( Goal, Inferences) :-
   statistics(inferences, Inferences0),
   Goal,
   statistics(inferences, Inferences1),
   Inferences is Inferences1 - Inferences0.

The number of inferences doubles with each further element. That is they grow exponentially. Your implementation thus costs at least exponentially many inferences... No need to look at a concrete example.

There are more problems in your program:

?- L=[A,B],list_to_set(L,S), L = [a,b].
   false.

fails, whereas

?-  L=[A,B], L = [a,b], list_to_set(L,S).
    L = [a,b], A = a, B = b, S = [a,b].

succeeds. That is, your program is no longer a pure relation. Use maplist(dif(A),Y) in place of \+ member(A,Y).