CODEWITHSUNDEEP
recursionprolog
Nick J
Nick J

Reputation: 43

Prolog Recursion Doesn't Stop as Expected

Hi everyone this is my first post so if you have any suggestions on how to ask questions I'm all ears. so on to my question I'm trying to sort a list of numbers using recursion, I have a my_max/2 predicate that returns the max of a list so after that returns I select that value from the list and then add it to my sorted list. then I recurse with the new list.

My problem is that the predicate seems to work and find the correct list but when the predicate exits it puts all the lists back to their original state basically undoing all of the work the predicate did. I think it has something to do with how Prolog backtracks?

%finds the max of a list, if the list is empty return int_min

my_max([],-2147483647).
my_max(L,M):-select(M,L,Rest), \+ (member(E,Rest),E>M).

%calls the my_max predicate store it in X, combines x and sorted and appends 
%it to sorted2,then it takes X out of unsorted and creates Unsorted2 then  
%recurse with unsorted2 and sorted2 should stop and output when unsorted is 
%empty or []

my_sort([],S).
%my_sort([],S):-write(S). for test    
my_sort(Unsorted,Sorted):-
   my_max(Unsorted,X),
   append(Sorted,[X],Sorted2),
   select(X,Unsorted,Unsorted2),
   my_sort(Unsorted2,Sorted2).

I added the the write just to show that it sorted the list. the output should be S=[3,2,1,1].

Output from the trace

Upvotes: 3

Views: 945

Answers (1)

game0ver
game0ver

Reputation: 1290

Firstly when loading your file I get:

Warning: Singleton variables: [S]

due to the base case:

my_sort([],S).

The problem is that base case states that empty list matches with a singleton variable S, so try:

?- my_sort([],[1,2]).
true ;
false.

?- my_sort([],hello).
true ;
false.

In neither cases should my_sort/2 succeed. So your base case should be the empty list: 

my_sort([],S).

and instead of building the complete sorted list in the base case you could build it through the recursion and leave an empty list in base case:

my_sort([],[]).
my_sort(Unsorted,Sorted):-
   my_max(Unsorted,X),
   select(X,Unsorted,Unsorted2),
   my_sort(Unsorted2,Sorted2),  %  <- continue to find the sorted sublist
   append(Sorted2,[X],Sorted).  %  <-place max at the end of sorted

In the above the Sorted2 is the sublist of Sorted so you find the list Sorted2 of the subproblem recursively and then add max. This is done recursively in each step and in base case you will have empty list.

So to understand it better here is an example-explanation:
Say you want to sort [2,1,3] list.

  • Find max = 3 find sorted for [2,1] (3 will be added after all recursive calls later)
  • Find max = 2 find sorted for [1]
  • Find max = 1 find sorted for [] which is []
  • Add max = 1 -> Sorted = [1]
  • Add max = 2 -> Sorted = [2]

  • Finally last add max = 3 -> Sorted = [1,2,3] Example:

    ?- my_sort([4,1,3,2],L). L = [1, 2, 3, 4] ; false.

Some Optimizations

In each step you find max in O(n) steps by traversing unsorted list, where n the length of unsorted list. Append again O(n). Select again O(n). So overall in each step you do 3 times O(n) computations.

To avoid that you could build the list in descending order so you wouldn't need to use append in O(n).

Also your max predicate could return the Rest list so you could avoid the select/3 in the sort predicate to reduce another N steps:

my_sort([],[]).

my_sort(Unsorted,[X|Sorted]):-
   my_max(Unsorted,X,Unsorted2),
   my_sort(Unsorted2,Sorted).

Example:

?- my_sort([4,1,3,2],L).
L = [4, 3, 2, 1] ;
false.

Now to get the ascending order use reverse/2:

?- my_sort([4,1,3,2],L),reverse(L,L1).
L = [4, 3, 2, 1],
L1 = [1, 2, 3, 4] ;
false.

This does O(N) steps to reverse the list but only one time not in each recursive call!!

Upvotes: 3

Related Questions