Как на самом деле работает этот код на Прологе - перемешать два списка

Question

У меня есть следующий код, , работающий , который перемешивает два списка:

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

Я понимаю каждую часть в отдельности. Первое предложение получает два списка, один с X, который является head , Xs является tail . В результате мы «берем» только первый список head . То же самое со вторым пунктом & ndash; мы не берем Xs за результат, только head из Y.

Пролог рекурсивно разделяет списки, а затем объединяет их.

Что я не понимаю здесь, как это работает? После того, как он «вычеркнул» все Xs, он просто «переместился» во второе предложение, чтобы взять Ys? Что заставляет Пролог сделать это?

Спасибо.

Answer 1

Избегая всех частей X, Y и Z, что мы можем сказать о работающем коде:

1. Вы начинаете с запроса, подобного shuffle([1,2],[a,b],L)., и Пролог пытается решить его, решая три правила shuffle.
2. Одно правило тасования может быть решено само по себе, но только для пустых списков, остальные два зависят от решения другого случая правила shuffle.
3. Какое бы решение ни было найдено должно перейти shuffle -> shuffle -> [shuffle....] -> empty lists. Это должно. Если он вообще не может соответствовать ни одному шаффлу, он ответит «ложь», и ваш код не будет работать. Если он перебрасывается между шаффами вечно, он будет бесконечным циклом и не даст ответов, и ваш код не будет работать. Он работает, поэтому он должен с самого начала объединяться в цепочку с пустыми списками.

Пролог постарается решить из верхней части правила:

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 []

Это законченная цепочка от источника через четыре шаффла до пустых списков. Во время этой цепочки Zs был построен как [1|?], затем [1|[2|?]], затем [1|[2|[a|?]]], затем [1|[2|[a|[b|?]]]], затем [1|[2|[a|[b|[]]]]], что завершено, ничего не пропуская. Это связано с вашим L вводом для первого результата.

Он прошел через перемешивание B B C C.

---

Но пространство поиска не исчерпано, возможно, будет больше ответов. Если вы попросите их, он развернется обратно по цепочке к месту, где он мог бы пойти другим путем. Вместо решения shuffle([X|Xs].. он может пропустить его и нырнуть вниз shuffle(Xs.

Два предиката shuffle с большим количеством значений работают вместе, образуя шаблон отказов, который заканчивается тремя пустыми списками:

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

Одна цепочка логических соединений - B B C C A. Другая цепочка - B C B C A, что приводит к следующему ответу L=[1,a,2,b].

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

Как только он вернется назад, при каждом выборе поменяйте местами перетасовку для другого и проследуйте вниз по цепочке до пустых списков, он найдет 6 путей, 6 способов отскочить через перетасовки.

Чем длиннее списки, тем длиннее цепочки. Когда он начинает возвращаться по цепочке, расстегивая шаги, ища другие пути, их становится больше. Больше точек выбора, поэтому он найдет больше решений - пропорционально длине входов.

Answer 2

Когда вы пытаетесь доказать цель в Прологе, например: shuffle([a],[c],L)., что Пролог делает, чтобы искать в базе данных, чтобы найти правила, которые много с предикатом перемешать.

В этом случае встречаются как второе, так и третье правило, поэтому у вас есть две точки выбора опций, как они называются в Прологе:

Точка первого выбора : мы проверяем второе правило: shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs). и, применяя его в нашей цели, получаем [X|Xs] = [a] (т. Е. X = a, Xs = []), Ys = [c], L имеет форму [a|Zs] и, наконец, вызывается рекурсивно shuffle([],[c],Zs). Эта цель теперь соответствует только третьему правилу, и мы получаем Zs = [c|Zs'], и снова рекурсивно вызывается shuffle([],[],Zs'), где теперь только первое правило соответствует, и мы получаем Zs' = []. Таким образом, из первого рассматриваемого случая мы получаем Zs = [a,c]. Теперь мы оставили еще один случай:

Точка второго выбора : мы исследуем третье правило: shuffle(Xs,[Y|Ys],[Y|Zs]):- shuffle(Xs,Ys,Zs). и, применяя его в нашей цели, получаем Xs = [a], [Y|Ys] = [c] (т. Е. Y = c, Ys = []) и L имеет форму [c|Zs] и, наконец, рекурсивно shuffle([a],[],Zs) вызывается. Эта цель теперь соответствует только второму правилу, и мы получаем Zs = [a|Zs'], и снова рекурсивно вызывается shuffle([],[],Zs'), где теперь только первое правило соответствует, и мы получаем Zs' = []. Таким образом, из второго рассматриваемого случая мы получаем Zs = [c,a].

Итак, наконец мы получили два решения. Как вы можете видеть, Пролог анализирует точки выбора в глубину, потому что он находит первую точку выбора и исследует ее, а затем переходит к третьей и так далее. Очевидная проблема здесь заключается в том, что вы можете представить количество точек выбора для двухэлементных списков, например, shuffle([a,b],[c,d],L) ?? Было бы четыре точки выбора, и для общего случая Xs,Ys точка выбора слишком велика.