Prolog Recursion on List

Question

I am trying to understand how this prolog program works, and, as a beginner, I'm having some difficulty. The program is as follows:

initialCan([w, b, w, w, w]).
scholten([X], X).
scholten([X, X | Z], Answer) :- scholten([b | Z], Answer).
scholten([X, Y | Z], Answer) :- scholten([w | Z], Answer).
run(Answer) :- initialCan(L), scholten(L, Answer).

Here is the trace from running it through the first solution.

{trace}
| ?- run(A).
      1    1  Call: run(_17) ? 
      2    2  Call: initialCan(_84) ? 
      2    2  Exit: initialCan([w,b,w,w,w]) ? 
      3    2  Call: scholten([w,b,w,w,w],_17) ? 
      4    3  Call: scholten([w,w,w,w],_17) ? 
      5    4  Call: scholten([b,w,w],_17) ? 
      6    5  Call: scholten([w,w],_17) ? 
      7    6  Call: scholten([b],_17) ? 
      7    6  Exit: scholten([b],b) ? 
      6    5  Exit: scholten([w,w],b) ? 
      5    4  Exit: scholten([b,w,w],b) ? 
      4    3  Exit: scholten([w,w,w,w],b) ? 
      3    2  Exit: scholten([w,b,w,w,w],b) ? 
      1    1  Exit: run(b) ? 

A = b ?

The thing I'm having trouble understanding is how the recursive calls work. What exactly happens with

scholten([X, X | Z], Answer) :- scholten([b | Z], Answer).

What is most confusing is the difference between [X, X | Z] and [b | Z]. Any help would be appreciated.

Sergey Kalinichenko Sergey Kalinichenko · Accepted Answer · 2013-03-15T01:48:01

The rule in question says that if scholten sees a list that starts with two identical elements, these two elements need to be replaced with a single b. The list [b | Z] is shorter by one element than the [X, X | Z].

Note that the rule below

scholten([X, Y | Z], Answer) :- scholten([w | Z], Answer).

has a singleton (i.e. unused anywhere else) variable Y. You should change the rule to

scholten([X, Y | Z], Answer) :- X \= Y, scholten([w | Z], Answer).

to ensure that X does not equal Y, preventing this rule from matching the same arguments as the [X, X | Z] one.

Prolog Recursion on List

1 Answers