How does this Prolog code really work - Shuffle two Lists

Question

I have the following code, working, that shuffles two lists:

shuffle([], [], []).
shuffle([X|Xs], Ys, [X|Zs]):-
          shuffle(Xs, Ys, Zs).
shuffle(Xs, [Y|Ys], [Y|Zs]):-
          shuffle(Xs, Ys, Zs).

I understand each part separately. The first clause receives two lists, one with X that is the head, Xs is the tail. In the result we "take" only the first list's head. The same with the second clause – we don't take Xs for the result, only the head of Y.

Prolog recursively separates the lists and then unifies them.

What I don't understand here is how it works? After it ended "taking out" all the Xs, it just "moves" to the second clause, to take the Ys? What triggers Prolog to do that?

Thank you.

Answer 1

When you try to prove a goal in Prolog for example: shuffle([a],[c],L). what Prolog does is to search in the database to find rules that much with the predicate shuffle.

In this case both second and third rule occur, so you have two options-choice points as called in Prolog:

1st-choice point: We examine second rule: shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs). and applying that in our goal we get [X|Xs] = [a] (so X = a, Xs = []), Ys = [c], and L is of the form [a|Zs], and finally recursively shuffle([],[c],Zs) is called. This goal now only matches third rule and we get Zs = [c|Zs'] and again recursively shuffle([],[],Zs') is called where now only first rule matches and we get Zs' = []. So from the first case examined we get Zs = [a,c]. Now we have left another case:

2nd-choice point: We examine third rule: shuffle(Xs,[Y|Ys],[Y|Zs]):- shuffle(Xs,Ys,Zs). and applying that in our goal we get Xs = [a], [Y|Ys] = [c] (so Y = c, Ys = []), and L is of the form [c|Zs], and finally recursively shuffle([a],[],Zs) is called. This goal now only matches second rule and we get Zs = [a|Zs'] and again recursively shuffle([],[],Zs') is called where now only first rule matches and we get Zs' = []. So from the second case examined we get Zs = [c,a].

So finally we get the two solutions. As you can see Prolog does a depth-first analysis on the choice points because it finds the first choice point and examines it and the goes on to the third and so on. The obvious problem here is that can you imagine the number of choice points for two-element lists e.g shuffle([a,b],[c,d],L) ?? It would be four choice points and for the general case of Xs,Ys the choice point are way too much.

Answer 2

Avoiding all the X and Y and Z parts, what can we say about the working code:

1. You start with a query like shuffle([1,2],[a,b],L). and Prolog tries to solve it by solving the three shuffle rules.
2. One shuffle rule can be solved on its own, but only for empty lists, the other two rely on solving another case of the shuffle rule.
3. Whatever solution is found must go shuffle -> shuffle -> [shuffle....] -> empty lists. It must. If it could not match any shuffles at all, it would answer "false" and your code wouldn't work. If it bounced between shuffles forever it would infinite loop and give no answers and your code wouldn't work. It does work, so it must chain from the start, through a combination of shuffles, to the empty lists.

Prolog will try to solve from the top of the rules:

From the top:

A) shuffle([1,2],[a,b],L).  -no->  shuffle([],[],[]).
B) shuffle([1,2],[a,b],L).  -??->  shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs).
B) shuffle([1,2],[a,b],L).  -??->  shuffle([X=1|Xs=[2]],Ys=[a,b],[X=1|Zs=??]) :- shuffle(Xs=[2],Ys=[a,b],Zs).

% A) fails as [1,2] does not match with []
% B) partially binds but is missing Zs. Solving to try and find the Zs is now:

shuffle(Xs=[2],Ys=[a,b],Zs).



From the top:

A) shuffle([2],[a,b],Zs).  -no->  shuffle([],[],[]).
B) shuffle([2],[a,b],Zs).  -??->  shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs).
B) shuffle([2],[a,b],Zs).  -??->  shuffle([X=2|Xs=[]],Ys=[a,b],[X=2|Zs=??]):- shuffle(Xs,Ys,Zs).

% A) fails as [2] does not match with []
% B) partially binds but is missing Zs. Solving to try and find the Zs is now:

shuffle(Xs=[],Ys=[a,b],Zs).



From the top:

A) shuffle([],[a,b],Zs).  -no->  shuffle([],[],[]).
B) shuffle([],[a,b],Zs).  -no->  shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs).
C) shuffle([],[a,b],Zs).  -??->  shuffle(Xs,[Y|Ys],[Y|Zs]):- shuffle(Xs,Ys,Zs).
C) shuffle([],[a,b],Zs).  -??->  shuffle(Xs=[],[Y=a|Ys=[b]],[Y=a|Zs=??]):- shuffle(Xs,Ys,Zs).

% A) fails as [a,b] does not match with the second []
% B) fails as [] does not match with [X|Xs]
% C) partially binds but is missing Zs. Solving to try and find the Zs is now:

shuffle([],[b],Zs).



From the top:

A) shuffle([],[b],Zs).  -no->  shuffle([],[],[]).
B) shuffle([],[b],Zs).  -no->  shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs).
C) shuffle([],[b],Zs).  -??->  shuffle(Xs,[Y|Ys],[Y|Zs]):- shuffle(Xs,Ys,Zs).
C) shuffle([],[b],Zs).  -??->  shuffle(Xs=[],[Y=b|Ys=[]],[Y=b|Zs=??]):- shuffle(Xs,Ys,Zs).

% A) fails as [b] does not match with the second []
% B) fails as [] does not match with [X|Xs]
% C) partially binds but is missing Zs. Solving to try and find the Zs is now:

shuffle([],[],Zs).



From the top:

A) shuffle([],[],Zs).  -no->  shuffle([],[],[]).

% A) succeeds. Zs can be []

This is a finished chain from the origin, through four shuffles, to the empty lists. During this chain, Zs has been constructed as [1|?] then [1|[2|?]] then [1|[2|[a|?]]] then [1|[2|[a|[b|?]]]] then [1|[2|[a|[b|[]]]]] which is complete, no missing anything. That binds to your L input for the first result.

It's gone through the shuffles B B C C.

---

But the search space is not exhausted, there might be more answers. If you ask for them it unwinds back up the chain to a place where it could have taken a different path. Instead of solving shuffle([X|Xs].. it can skip that one and dive down shuffle(Xs instead.

The two shuffle predicates with lots of values work together make a bounce pattern, which terminates with the three empty list cases:

[1,2],[a,b],Unknown
        \
         \
          \ ? shuffle shuffle shuffle
          /
         /
         \
      [],[],[]

One chain of logical connections is B B C C A. Another chain is B C B C A which results in the next answer L=[1,a,2,b].

[1,2],[a,b],Unknown
       /   \       
      /     \
      \      \ B C B A
B B C C\     /
       |    /
       |    \
      [],[],[]

Once it's backtracked all the way back, at each choice swapped the shuffle for the other one and followed down the chain to the empty lists, it will have found 6 paths, 6 ways to bounce through the shuffles.

As you make the lists longer, the chains get longer. When it starts backtracking up the chain undoing its steps looking for other ways to go, there are more of them. More choice points, so it will find more solutions - proportional to the length of the inputs.