🚀 go-pugleaf

"Shira Rotman" <shira20@matavtv.net> wrote:
    % code:
/*1*/   swap([],[]).
/*2*/   swap([X],[X]).
/*3*/   swap([X,Y|L1],[X,Y|L2]):-X=<Y,swap([Y|L1],[Y|L2]).
/*4*/	swap([X,Y|L1],[Y,X|L2]):-X>Y,swap([X|L1],[X|L2]).
    % query:
	?- swap([2,5,4,7,6],X).

The query unifies with the head of clause 3b:
    X.1 = 2, Y.1 = 5, L1.1 = [4,7,6],
    X.0 = [2,5|L2.1]
then the test X1.1 =< Y1.1 succeeds, so the new query is
    swap([5,4,7,6], [5|L2.1]

The key point is that this query does NOT unify with the head
of clause 4.  Let's lay them out together:

	swap([5,  4  |[7,6]], [5  |L2.1      ])
	swap([X.2,Y.2|L1.2 ], [Y.2|[X.2|L2.2]])

For this query to unify with the head of clause 4, we'd need
	X.2 = 5,
	Y.2 = 4,
	L1.2 = [7,6]		(no problem yet)
	Y.2 = 5		OOPS!

So the code DOES "continue to [clause] 4", but it doesn't get as far
as checking whether 5 > 4 because the head unification correctly fails.

This is extremely unusual code; what is the intended meaning of this
predicate?

If it is suppose to traverse the first list from left to right,
swapping all adjacent pairs that are out of order (including the
pairs that result _after_ each swap), then

    swap([], []).
    swap([X], [X]).
    swap([X,Y|L1], [X|L2]) :- X =< Y, swap([Y|L1], L2).
    swap([X,Y|L1], [Y|L2]) :- X > Y,  swap([X|L1], L2).

produces the result X = [2,4,5,6,7] for the query swap([2,5,4,7,6], X).
Not that I'd write it quite like that, myself.

To help, here's a Haskell version:
    swap :: Ord a => [a] -> [a]

    swap (x1:x2:xs) | x1 <= x2 = x1 : swap (x2:xs)
    swap (x1:x2:xs) | x1 > x2  = x2 : swap (x1:xs)
    swap xs                    = xs


----------------
* To UNSUBSCRIBE, please use the HTML form at

    http://www.swi.psy.uva.nl/projects/SWI-Prolog/index.html#mailinglist

or send mail to prolog-request@swi.psy.uva.nl using the Subject: "unsubscribe"
(without the quotes) and *no* message body.

** An ARCHIVE of this list is maintained at

    http://www.swi.psy.uva.nl/projects/SWI-Prolog/mailinglist/archive/