Sorting By Functions in Prolog

Our example demonstrates how to implement custom sorting in Prolog. We’ll sort strings by their length and then sort a list of structures by a specific field.

% Define our main predicate
main :-
    % Define a list of fruits
    Fruits = [peach, banana, kiwi],

    % Sort the fruits by length
    sort_by_length(Fruits, SortedFruits),
    writeln(SortedFruits),

    % Define a list of people
    People = [person(jax, 37), person(tj, 25), person(alex, 72)],

    % Sort the people by age
    sort_by_age(People, SortedPeople),
    writeln(SortedPeople).

% Predicate to sort a list by the length of its elements
sort_by_length(List, Sorted) :-
    map_list_to_pairs(atom_length, List, Pairs),
    keysort(Pairs, SortedPairs),
    pairs_values(SortedPairs, Sorted).

% Predicate to sort a list of person structures by age
sort_by_age(List, Sorted) :-
    map_list_to_pairs(person_age, List, Pairs),
    keysort(Pairs, SortedPairs),
    pairs_values(SortedPairs, Sorted).

% Helper predicate to get the age from a person structure
person_age(person(_, Age), Age).

In this Prolog example, we implement custom sorting for both strings and structures:

1. We define a sort_by_length/2 predicate that sorts a list of atoms (strings) by their length. It uses map_list_to_pairs/3 to create key-value pairs where the key is the length of each atom, then uses keysort/2 to sort these pairs, and finally extracts the sorted values with pairs_values/2.

2. For sorting structures, we define a sort_by_age/2 predicate that works similarly, but uses a helper predicate person_age/2 to extract the age from each person structure.

3. The main/0 predicate demonstrates both sorting operations.

To run this program, you would typically save it in a file (e.g., custom_sorting.pl) and then use your Prolog interpreter. For example, with SWI-Prolog:

$ swipl -s custom_sorting.pl -g main -t halt
[kiwi,peach,banana]
[person(tj,25),person(jax,37),person(alex,72)]

This example showcases Prolog’s declarative approach to sorting. Instead of writing comparison functions, we define the sorting criteria through predicates and leverage Prolog’s built-in sorting capabilities.