3

I'm new in Prolog and I'm trying to make the selection sort. Here is what I have:

ssort([],[]).
ssort([M|S],L):-min(M,L),remove(M,L,N),ssort(S,N).

min(M,[M]).
min(M,[H,T]):-min(N,T),min2(M,H,N).

min2(A,A,B):-less(A,B).
min2(B,A,B):-not(less(A,B)).

less(A,B):-(A<B).

append([],B,B).
append([H|A],B,[H|AB]):-append(A,B,AB).

remove(X,L,N):-append(A,[X|B],L),append(A,B,N).

But when I try this for example:

ssort(S,[5,3,1]),write(S).

I get false, no matter what I try. Can you tell me how can I actually sort the list and get the result written in S?

Petar D.
  • 149
  • 1
  • 5
  • 15
  • 1
    Have you traced it? Are you sorting the first or the second argument? Have you tried to test each of the predicates in isolation? For example, are you sure that your `min/2` does what you expect it do do? I am asking because you might be able to solve your problem on your own without too much effort, and because if I would try to do a selection sort in Prolog it would be a bit too different from what you have right now, and it is an unpleasant job to hunt down other people's errors ("bugs"). –  Mar 19 '17 at 13:21
  • Unfortunately, I don't know how to trace it. I'm sorting the second argument, and writing the result in the first. `min2` is supposed to find the minimum between 2nd and 3rd argument and write it in the first. I'm not sure if I'm doing it right, though :D – Petar D. Mar 19 '17 at 13:29
  • Here is a suggestion: test your `min/2` and your `min2/3`. If they work as expected, you have a problem elsewhere (and there isn't that much code). If they don't work as expected, you can make a smaller, more specific question that is easier to answer. At the moment you just have a bunch of code and "please correct it" which is not a good approach to asking. –  Mar 19 '17 at 13:46
  • 1
    "no matter what I try" have you tried `ssort(S,[5]),write(S).`? it works. – Will Ness Mar 19 '17 at 15:29

2 Answers2

5

Here is a general way how you can at least localize the error in your program. If your query fails, simply remove goals from your program. If the remaining fragment still fails, there must be an error in that fragment.

:- op(950,fy,*).
*_.

ssort(_/*[]*/,[]).
ssort(_/*[M|S]*/,L):-
   min(_/*M*/,L),
   * remove(M,L,N),
   * ssort(S,N).

min(M,[M]).
min(M,[H,T]):-
   * min(N,T),
   * min2(M,H,N).

?- ssort(S,[5,3,1]).

Because this fragment fails, your original program will fail as well. You need to generalize something in the remaining part.

false
  • 10,264
  • 13
  • 101
  • 209
4

As well pointed out by @Boris the main mistake was in min/2 predicate because it needs a 3rd parameter in order to return the min element in that parameter. With a few small changes the code looks like:

ssort([],[]).
ssort([M1|S],[H|T]):-min(H,T,M1),remove(M1,[H|T],N),ssort(S,N).

min(M,[],M).
min(M,[H|T],M1):-min2(M,H,N),min(N,T,M1).

min2(A,B,A):-less(A,B).
min2(A,B,B):-not(less(A,B)).

less(A,B):-(A<B).

append([],B,B).
append([H|A],B,[H|AB]):-append(A,B,AB).

remove(X,L,N):-append(A,[X|B],L),append(A,B,N).

Example:

?- ssort(S,[5,3,1]).
S = [1, 3, 5] ;
false.

?- ssort(S,[5,3,1,7]).
S = [1, 3, 5, 7] ;
false.

EDIT:

As @Will Ness correctly pointed out the only mistake was the comma in min(M,[H,T]) so changing to min(M,[H|T]) it works fine!!!. I thought that min/2 predicate wasn't working very well so I changed it in the answer above but finally this was not necessary.

coder
  • 12,832
  • 5
  • 39
  • 53
  • What happens if you try `ssort(Sorted, [1,2,1])`? –  Mar 19 '17 at 13:52
  • @Boris, I've (already) noticed that when there are duplicate elements there are duplicate answers, for example ssort(Sorted, [1,2,1,1]) returns 6 same correct answers because there are the ways to put the three 1-elements in the beginning of the sorted list (3 ways for 1st position,2 for second and 1 for third so overall 3*2*1=6 ways)... I think this is due to min2/2 predicate but anyway it doe not give wrong answers... duplicates could be removed with cut operator... – coder Mar 19 '17 at 14:00
  • Thank you for the answers. One last thing, why do you refer to `min` predicate as `min/2`? – Petar D. Mar 19 '17 at 14:25
  • Glad to help!!!, Sorry I was thinking the first min predicate which had two parameters, now it is min/3 ,(/3 means that this predicate has three parameters). – coder Mar 19 '17 at 14:28
  • 1
    no need to change all of that. all it was, was a typo - just *one* wrong character in the code. can be hard to notice, visually, too. – Will Ness Mar 19 '17 at 15:13
  • @Will Ness, What was the just one wrong character in the code?? Am I missing something?? – coder Mar 19 '17 at 15:17
  • 1
    a comma. i missed it too, at first. could swear I saw the correct character there. expectation driven perception, huh. – Will Ness Mar 19 '17 at 15:21
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/138465/discussion-between-will-ness-and-coder). – Will Ness Mar 19 '17 at 15:34