Prolog mystery(c,[a,b,c,d],Z).

Question

I think the answer is 3 but I am not sure, can anyone provide some help?

Suppose the following two statements are entered into Prolog:

mystery(X,[X|L],L).
mystery(X,[Y|L],[Y|M])  :-  mystery(X,L,M).

What would Prolog return if one then gives it the following goal?

?- mystery(c,[a,b,c,d],Z).

Answer 1

So, mystery/3 is defined as:

mystery(X, [X|L], L).
mystery(X, [Y|L], [Y|M]) :- mystery(X, L, M).

There are (at least) three ways to look at mystery:

1. It takes an element X (first parameter), looks for its existence in a given list (second parameter) and returns that same list, minus one occurrence of X (third parameter). Thus:

   ?- mystery(c, [a, b, c, d], Z).
   Z = [a, b, d] ;
   fail.
   
   
   ?- mystery(c, [a, b, c, d, c], Z).
   Z = [a, b, d, c] ;
   Z = [a, b, c, d] ;
   fail.
   

2. Another way to look at mystery is that it checks whether the lists constituting its second and third argument only differ with respect to one element, i.e. that the second list equals the third list, except that it has one additional element in one place. Thus:

   ?- mystery(X, [a, b, c, d], [a, b]).
   fail.
   
   
   ?- mystery(X, [a, b, c, d], [a, b, c]).
   X = d ;
   fail.
   

   Note that order is important:

   ?- mystery(X, [a, b, c, d], [a, c, b]).
   fail.
   

3. Lastly, mystery can also generate all ways in which the first argument can be interspersed in the list of the third argument. Thus:

   ?- mystery(d, Y, [a, b, c]).
   Y = [d, a, b, c] ;
   Y = [a, d, b, c] ;
   Y = [a, b, d, c] ;
   Y = [a, b, c, d] ;
   fail.