Prolog - A newbe wants to know what this mean..

Author

A newbe wants to know what this mean..

Snaggy

2007-08-31, 8:10 pm

bubble_sort(Xs, Ys):-
append(Ws, [A,B|Zs], Xs),
B < A,
append(Ws, [B,A|Zs], Vs), !,
bubble_sort(Vs, Ys).
bubble_sort(Xs, Xs).

this is a very simple bubblesort algorithm, the only thing I don't
understand is the use of ,!, . I can't find what that's for, but if
I delete it the program returns a bunch of wrong solutions after the
first correct one.

thanks
Luca

Chip Eastham

2007-08-31, 8:10 pm

On Aug 31, 1:47 pm, Snaggy <l.cio...@gmail.com> wrote:
> bubble_sort(Xs, Ys):-
> append(Ws, [A,B|Zs], Xs),
> B < A,
> append(Ws, [B,A|Zs], Vs), !,
> bubble_sort(Vs, Ys).
> bubble_sort(Xs, Xs).
>
> this is a very simple bubblesort algorithm, the only thing I don't
> understand is the use of ,!, . I can't find what that's for, but if
> I delete it the program returns a bunch of wrong solutions after the
> first correct one.
>
> thanks
> Luca

If you understand what the rest of the code
is doing, then a concise answer is that the
cut (!) keeps the algorithm moving toward a
sorted final result.

The first clause makes a recursive call just
after the cut, effectively transposing two
adjacent elements in the input list Xs to
the ascending order in revised input list Vs.

When (and only when, as a result of the cut)
the out-of-order pairs of elements can no
longer be found in the (current) input list,
control passes to the second clause (which
succeeds simply by binding the output list
to the input list, since now that's known to
be sorted).

Without the cut you should still get the
sorted list as the first solution, but any
backtracking will begin to produce alternate
"solutions" that (by utilizing the second
clause in place of the first at various levels
of recursion) are not sorted (because they do
contain adjacent elements out-of-order).

regards, chip

Snaggy

2007-08-31, 8:10 pm

thanks for the quick answer, I noticed that cuts are a big part of
prolog that I had somehow completely missed!

Luca

Chip Eastham

2007-08-31, 8:10 pm

On Aug 31, 2:09 pm, Chip Eastham <hardm...@gmail.com> wrote:
> On Aug 31, 1:47 pm, Snaggy <l.cio...@gmail.com> wrote:
>
>
>
>
> If you understand what the rest of the code
> is doing, then a concise answer is that the
> cut (!) keeps the algorithm moving toward a
> sorted final result.
>
> The first clause makes a recursive call just
> after the cut, effectively transposing two
> adjacent elements in the input list Xs to
> the ascending order in revised input list Vs.
>
> When (and only when, as a result of the cut)
> the out-of-order pairs of elements can no
> longer be found in the (current) input list,
> control passes to the second clause (which
> succeeds simply by binding the output list
> to the input list, since now that's known to
> be sorted).
>
> Without the cut you should still get the
> sorted list as the first solution, but any
> backtracking will begin to produce alternate
> "solutions" that (by utilizing the second
> clause in place of the first at various levels
> of recursion) are not sorted (because they do
> contain adjacent elements out-of-order).
>
> regards, chip

It might be worth noting that, as a special
case, inputting a sorted list Xs will only
result in success of the second clause. So
there would be no alternative solutions for
that input, regardless of cut placement.

regards, chip

Sponsored Links