Sorting in Prolog

Our example demonstrates sorting in Prolog. We’ll look at sorting for lists of different types.

% Main predicate to demonstrate sorting
main :-
    % Sorting strings
    Strs = ["c", "a", "b"],
    msort(Strs, SortedStrs),
    write('Strings: '), write(SortedStrs), nl,

    % Sorting integers
    Ints = [7, 2, 4],
    msort(Ints, SortedInts),
    write('Ints:    '), write(SortedInts), nl,

    % Checking if a list is sorted
    is_sorted(SortedInts, IsSorted),
    write('Sorted:  '), write(IsSorted), nl.

% Predicate to check if a list is sorted
is_sorted([], true).
is_sorted([_], true).
is_sorted([X,Y|Rest], Result) :-
    (   X @=< Y
    ->  is_sorted([Y|Rest], Result)
    ;   Result = false
    ).

In Prolog, we use the built-in msort/2 predicate to sort lists. This predicate works for both lists of atoms (strings) and numbers.

We define a main predicate that demonstrates sorting for both strings and integers. The msort/2 predicate is used to sort the lists.

To check if a list is sorted, we define a custom is_sorted/2 predicate. This predicate recursively checks if each element is less than or equal to the next one.

To run this program, you would typically save it in a file (e.g., sorting.pl) and then consult it in a Prolog interpreter:

?- [sorting].
?- main.
Strings: [a,b,c]
Ints:    [2,4,7]
Sorted:  true

Note that Prolog doesn’t have mutable variables or side effects like imperative languages. Instead, we use logical variables and unification to achieve our results. The write/1 and nl/0 predicates are used for output.

Prolog’s approach to sorting is declarative, focusing on the what (the sorted result) rather than the how (the sorting algorithm). The built-in msort/2 predicate handles the implementation details of the sorting algorithm.