prologprogram-slicing

Selection sort in prolog


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?


Solution

  • 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.