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.