Beginners problem sorting a list

[Jan Tack]

I have just started with Prolog, by reading Brue Tates book "Seven Languages in Seven Weeks".

Two of the exerices in the Prolog chapter are:  

* Find the smallest element in a list

* sort the elments in a list 

My Idee was to solve the second problem by using the solution of the first one.   (Of course just could use the sort/2 of SWI Prolog, but this not what an exercise is about.)

min([H|T],X) :- T=[], X=H.

min([H|T],H):- T\=[], min(T,Min_Tail), Min_Tail>H.

min([H|T],X):- T\=[], min(T,X), X=<H.

The Minimum should be the first element in the sorted List. Now I want to delete the minimum from the given list and proceed with this shorted list. There for, I created remove/3, which should be used to delete the first occurrence of a given item in the list.   

remove(Item, [H|T], Result) :- Item=H, Result=T.

remove(Item, [H|T], Result) :- Item\=H, remove(Item, T, Y), Result=[H|Y].

  

sor(X, [H|T]) :- T=[], X=[H].    

sor(X, [H|T]) :- T\=[], min(X,H), remove(H, X, Y), sor(Y,T).

sor can find out, weather a list is sorted correctly:

?- sor([3,2,1],[1,2,3]).

true .

?- sor([1,4,55,3,2,1],[1,1,2,3,4,55]).

true .

?- sor([3,2,4],[2,4,3]).

false.

but sort does not find a solution by it self:

?- sor([2,1], X).

false.

   

Why?

 

[Jan Tack]

[Feliks Kluzniak]

After unifying  sor([2, 1], Y) with the head of the first clause, you get X instantiated to [2, 1],  so the unification X = [H] will fail.

But the second clause cannot succeed, either, because when you test whether T \= [], T is an uninstantiated variable, which can of course unify with [], and therefore the test fails.

Hope this helps.

— Feliks

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.
Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

[Jan Tack]

Thank You!

Now I see why it did'nt work. I have changed it to 

...

sor(X, S) :- X=[], S=[].    

sor(X, [H|T]) :- X\=[], min(X,H), remove(H, X, Y), sor(Y,T).

and now it's working.

[Markus Triska]

Hi Jan,

in addition, you can also get your original code working if you simply use the constraint dif/2 instead of (\=)/2: dif/2 is easy to understand, because it works correctly in all directions. (\=)/2, on the other hand, is much harder to understand, because it lacks the properties you expect from logical relations. For example:

?- X \= Y.

false.

Read declaratively, this answer tells us: "There are no 2 terms X and Y for which X \= Y holds.". But that's not the case!

?- a \= b.

true.

When you are using such predicates, it makes your code very hard to reason about. Therefore, I recommend you look into the dif/2 predicate that actually behaves in exactly the way you expect from relations, and use it instead.

For example, here is your original code, with only very small changes: I have put unifications into the clause heads, I have replaced (\=)/2 by dif/2, and I am using CLP(FD) constraints to make clear that this program is reasoning about integers (you need to place ":- use_module(library(clpfd))." in your ~/.swiplrc to use CLP(FD) constraints in all your programs):

min([H],H).

min([H|T],H):- dif(T, []), min(T,Min_Tail), Min_Tail #> H.

min([H|T],X):- dif(T, []), min(T,X), X #=< H.

remove(H, [H|T], T).

remove(Item, [H|T], [H|Y]) :- dif(Item, H), remove(Item, T, Y).

sor([H], [H]).

sor(X, [H|T]) :- dif(T, []), min(X, H), remove(H, X, Y), sor(Y, T).

Now the query that previously failed also yields an answer:

?- sor([2,1], X).

X = [1, 2] ;

false.

Best of all, you can now also apply your change on top of this. So, this was really only obtained by exchanging impure predicates for pure ones: Use dif/2 to express term disequality, use CLP(FD) constraints for integer arithmetic. All other changes can follow from there. It simply gives you a solid foundation for more complex changes, such as reordering goals. The available Prolog books do not take advantage of such predicates, mostly because they were not (as widely) available when the books were written.

All the best,

Markus

[Jan Tack]

Thank you very much Markus, for your comprehensive explanation! Your first example explains, why Prolog - and in particular "/=" - don't  work like I expect it. This is very helpful for me. I all ready despaired of that problem, also in other exercises.  

[Markus Triska]

Hi Jan,

On Sunday, August 14, 2016 at 3:57:10 PM UTC+2, Jan Tack wrote:

Your first example explains, why Prolog - and in particular "/=" - don't  work like I expect it.

For such reasons (impurity of (\=)/2), I recommend you simply use dif/2 to express disequality of terms.

The tragic in this concrete case, and countless others like it, is that your way of approaching this task ("the second clause holds only if T is not the empty list") is in principle perfectly valid, but anticlimactically counteracted by impure legacy predicates that can only be understood procedurally and non-monotonically depend on concrete instantiation patterns.

dif/2 gives you the necessary freedom to reorder your goals and observe the procedural effects of placing the goal at different positions within your clause. (\=)/2 does not give you this freedom in the first place. Everything that would have worked correctly with (\=)/2 also works with dif/2, so dif/2 is a true generalization that completely subsumes the more low-level predicate it is meant to replace in user code.

Historically, dif/2 was even available in the very first Prolog implementation, then largely ignored by implementors for a number of yours, and is now becoming available again in a growing number of Prolog implementations. SWI-Prolog has been shipping with dif/2 and many other important constraints for a number of years now, thanks to the implementation work of Tom Schrijvers, Bart Demoen and several other contributors. Adoption of these constraints in user programs and books is ... work in progress ;-)

I have uploaded a short text about logical purity and hope you find it useful:

https://www.metalevel.at/prolog/purity.html

All the best,

Markus