CODEWITHSUNDEEP
prolog
John_00
John_00

Reputation: 45

I cant understand how the function subset(X,Y) works

Can somebody to explain me this code? I try for hours to understand but i can't understand this...

subset([],[]).
subset([X|L],[X|S]) :- subset(L,S).
subset(L, [_|S]) :- subset(L,S).

Upvotes: 1

Views: 39

Answers (2)

Will Ness
Will Ness

Reputation: 71070

We can re-write it (nearly) equivalently to push the unifications out of the rules' headers, to make the code's structure more visually apparent:

subset(A,B) :- B=[], A=[].

subset(A,B) :- B=[X |    S], 
               A=[X | L], 
               subset(L, S).

subset(A,B) :- B=[_ |    S], 
               A=     L, 
               subset(L, S).

So A is a subset of B, if

  • B=[] and A=[], or
  • A contains the first element of B, etc. or
  • A does not contain the first element of B, etc.

That is all.

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476503

Imagine that you have a list [1,4], then there are four possible solutions: [1,4], [1], [4], and [], so if you call subset(L, [1,4]), we get:

?- subset(L, [1,4]).
L = [1, 4] ;
L = [1] ;
L = [4] ;
L = [].

The Prolog predicate returns for an empty list an empty list, which is indeed the only sublist we can generate:

sublist([], []).

for a sublist with at least one element X there are each time two possibilities: include X in the result, or do not include X in the result. In both cases we recurse on the tail of the list. The tail thus contains the remaining elements, and for each of these elements, there is again a decision point whether to include these elements or not.

In pseudo-code, an evaluation tree could thus look like:

subset(L, [1,4]) :-
    subset([1|L], [1|S]) :-
        subset([4|L], [1|S]) :-
            subset([], []).  % outer L=[1,4]
        subset(L, [1|S]) :-
            subset([], []).  % outer L=[1]
    subset(L, [1|S]) :-
        subset([4|L], [1|S]) :-
            subset([], []).  % outer L=[4]
        subset(L, [1|S]) :-
            subset([], []).  % outer L=[]

Upvotes: 2

Related Questions