Пожалуйста, объясните сокращение в программе Bubblesort Prolog?

Question

В настоящее время я работаю через книгу Братко Пролога, и я смотрю программу сортировки пузырьков. Я не могу понять, почему нужен разрез (!). Скажите, что разреза нет, и Prolog откажется, как он может найти плохие ответы? Потому что, если я оставлю вырез из него, Пролог начнет, давая мне правильный ответ, но затем также дает альтернативные плохие ответы.

Как я вижу, как можно поменять когда-либо возвращенный неупорядоченный список? И как возможно, что не отсортированный список когда-либо попадает в цель bubblesort(Sorted, Sorted).

Если, конечно, не изменился и первый список ... Невозможно остричь голову.

программа Prolog BubbleSort:

gt(X,Y) :- X > Y. 

bubblesort(List, Sorted) :- 
    swap(List, List1), !,   % A useful swap in List? 
    bubblesort(List1, Sorted). 
bubblesort(Sorted, Sorted).  % Otherwise list is already sorted 

swap([X,Y|Rest], [Y,X|Rest]) :- % Swap first two elements 
    gt(X,Y). 
swap([Z|Rest], [Z|Rest1]) :-  % Swap elements in tail 
    swap(Rest, Rest1). 

Оставляя сокращение внешкольных это дает мне:

?- bubblesort([5,7,3,6,8,9,2,6], Sorted). 

Sorted = [2, 3, 5, 6, 6, 7, 8, 9] ; 

Sorted = [2, 3, 5, 6, 7, 6, 8, 9] ; 

Sorted = [2, 3, 5, 6, 7, 8, 6, 9] ; 

Sorted = [2, 3, 5, 6, 7, 8, 9, 6] ; 

Я думаю, что как-то я понимаю, но я не уверен. Может быть, в какой-то момент он возвращается к swap(List, List1), идя ко второму предикату сорта пузыря и ударяя по цели, что означает, что два списка Sorted равны?

На английском языке, означает ли это, что сортировка пузырьков должна продолжать делать свопы до тех пор, пока не будет возможно больше свопов, но тогда необходимо прекратить? Или это означает, что каждый раз удачный обмен был сделан, нет никакого смысла возвращаться к этому успеху?

Answer 1

Есть несколько возможностей, чтобы цель swap(List, List1) сбой. Либо List - это список длин 0 или 1; или он не содержит двух сразу последующих элементов, где второй меньше первого.

Разрез помещается таким образом, что он как разрезает swap/2, так и альтернативу bubblesort/2.

Это хороший пример, где «глубокий разрез» (резка глубоко в swap/2 все еще работает несколько красиво. Однако такие ситуации встречаются очень редко. В большинстве случаев срез слишком сильно сокращается. программы является очень хрупким использовать, даже более того, если второй аргумент уже дан Они часто не тверды

Ах, я чуть не пропустил его:.. даже в этой программе, мы имеем bubblesort(nonlist,L) успех, или bubblesort([1|nonlist],L) которые, вероятно, не предназначены и приводят к тонким ошибкам программирования.

Есть еще одна причина, почему программа не представляет идеальный стиль программирования логики: второе правило bubblesort/2, когда только читается: Все отсортировано по списку `. Чтобы понять это, мы должны одновременно прочитать оба правила и сузить его до Все, кроме ....

На английском языке, означает ли это, что сортировка пузырьков должна продолжать делать свопы до тех пор, пока не произойдет больше свопов, но тогда их нужно прекратить? Или это означает, что каждый раз удачный обмен был сделан, нет никакого смысла возвращаться к этому успеху?

Это первое процессуальное значение, которое здесь применяется.И, конечно же, ошибка в обращении к успеху во втором предложении bubblesort/2 будет ошибкой.

Еще одна неинтуитивная деталь, не относящаяся к разрезу, заключается в том, что в дополнение к номерам программа также преуспевает для выражений, таких как bubblesort([1,1+1],L), что снова может привести к тонким различиям.

Answer 2

Я просто хочу добавить, что если-то-иначе является гораздо более подходящей конструкцией языка, чем !/0 выразить намерение (и я знаю, что вы не выбрали !/0 самостоятельно здесь):

bubblesort(List0, List) :- 
     ( swap(List0, List1) -> 
      bubblesort(List1, List) 
     ; List0 = List 
     ). 

вы можете изменить -> к *->, чтобы увидеть альтернативные решения swap/2, а также, то есть, если вы измените это:

bubblesort(List0, List) :- 
     ( swap(List0, List1) *-> 
      bubblesort(List1, List) 
     ; List0 = List 
     ). 

Тогда йо получить у, например:

?- bubblesort([5,7,3,6,8,9,2,6], Ascending). 
Ascending = [2, 3, 5, 6, 6, 7, 8, 9] ; 
Ascending = [2, 3, 5, 6, 6, 7, 8, 9] ; 
Ascending = [2, 3, 5, 6, 6, 7, 8, 9] . 

Как вы видите, все эти списки не убывают, как вы уже ожидали.