Prolog Practice Questions

In the follow Prolog questions, your functions only need to work correctly for the first solution that they return. It’s okay if they don’t work perfectly after the first correct solution is returned.

Of course, it would be best to have your functions work perfectly in all cases, but that may require using advanced features such as cuts, that we didn’t cover in this course.

1. Write a function called is_sorted(Lst) that succeeds if Lst is a list of numbers in ascending sorted order, and fails otherwise. For example:

   ?- is_sorted([]).
   true.
   
   ?- is_sorted([6]).
   true .
   
   ?- is_sorted([6, 9]).
   true .
   
   ?- is_sorted([4, 4, 4]).
   true .
   
   ?- is_sorted([1, 2, 3, 5, 4, 6]).
   false.
   

   Your implementation should be relatively efficient and use basic Prolog features (don’t use sorting in your answer).

   Solution:

   % Of course, other solutions are possible.
   
   % is_sorted(Lst) succeeds iff Lst is in ascending sorted order
   is_sorted([]).
   is_sorted([_]).
   is_sorted([X|Xs]) :-
      is_sorted(Xs),
      [H|_] = Xs,
      X =< H.
   

2. Write a function called qsort(Lst, Sorted) that sorts the list of numbers Lst, putting the result in Sorted. For example:

   ?- qsort([], Sorted).
   Sorted = [].
   
   ?- qsort([4], Sorted).
   Sorted = [4] .
   
   ?- qsort([4, 5], Sorted).
   Sorted = [4, 5] .
   
   ?- qsort([5, 4], Sorted).
   Sorted = [4, 5] .
   
   ?- qsort([1, 5, 4], Sorted).
   Sorted = [1, 5, 4] ..
   
   ?- qsort([5, 1, 9, 3, 2, 0, 2, 0, 0], Sorted).
   Sorted = [0, 0, 0, 1, 2, 2, 3, 5, 9] .
   

   qsort should also be able to test if a list is sorted, e.g:

   ?- qsort([5,6,7], [5,6,7]).
   true .
   
   ?- qsort([5,6,7], [5,7,6]).
   false.
   

   Note that qsort only needs to follow the basic outline of quicksort. It’s okay if it is inefficient when, say, combining the sorted sub-lists.

   Solution:

   % Of course, other solutions are possible.
   
   % part1(X, Lst, Smalls, Bigs) partitions the numbers in Lst
   % such that all numbers in Lst less than, or equal to, X are
   % put in Smalls, and all other numbers are put in Bigs.
   part1(_, [], [], []).
   part1(X, [A], [A], []) :-
      X >= A.
   part1(X, [A], [], [A]) :-
      X < A.
   part1(X, [A|As], Smalls, Bigs) :-
      X >= A,
      part1(X, As, Asmalls, Bigs),
      Smalls = [A|Asmalls].
   part1(X, [A|As], Smalls, Bigs) :-
      X < A,
      part1(X, As, Smalls, Abigs),
      Bigs = [A|Abigs].
   
   % qsort(Lst, Sorted) sorts the numbers of Lst into ascending order,
   % and puts the sorted listed into Sorted.
   %
   % While this follows the quicksort algorithm, no attempt has been
   % made to make this efficient either in terms of time or space.
   qsort([], []).
   qsort([A], [A]).
   qsort([X|Xs], Sorted) :-
      part1(X, Xs, Smalls, Bigs),
      qsort(Smalls, Smalls_sorted),
      qsort(Bigs, Bigs_sorted),
      append(Smalls_sorted, [X|Bigs_sorted], Sorted).