title: Please explain the cut in the Bubblesort Prolog program?
body: <p>I'm currently working trough the Bratko Prolog book and I am looking at the bubble-sort Program. I can't seem to figure out why the cut(<code>!</code>) is necessary. Say the cut isn't there, and Prolog would backtrack, how could it possibly find bad answers? Because if I leave the cut out of it, Prolog begins by giving me the correct answer but then also gives alternative bad answers.</p>
  
  <p>As I see it, how can swap ever return a non sorted list? And how is it possible that a non sorted list ever hits the goal <code>bubblesort(Sorted, Sorted)</code>.</p>
  
  <p>Unless of course the first List is also being changed... Can't get my head around it.</p>
  
  <p>Prolog BubbleSort program:</p>
  
  <pre><code>gt(X,Y) :- X &gt; 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).
  </code></pre>
  
  <p>Leaving the cut of out it gives me:</p>
  
  <pre><code>?- 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] ;
  </code></pre>
  
  <p>I think that somehow I get it, but I am not sure. Could it be that at a certain moment, it backtracks over <code>swap(List, List1)</code> going to the second bubble-sort predicate and hitting the goal, meaning the two lists Sorted are equal?</p>
  
  <p>In English, does this mean that bubble-sort needs to continue doing swaps until no more swaps are possible, but then needs to terminate? Or does it mean that every-time a successful swap has been done, there's no use backtracking over that success?</p>