Sorting Lists

Is there a simply way to sort lists build up by (collect …) (into $List)
I didn’t find any clue yet …

I am sorry to say that to my knowledge the only list-related predicates are the built-ins and the soft-coded predicates listed in the manual. None of them is a list sorter per se.

1 Like

I don’t believe there is a built in sort function. But it’s not terribly difficult to write one, at least for numbers. I don’t at all guarantee the efficiency of this, but if you are sorting shortish lists it may suffice. (No originality claimed: it’s just a standard Prolog insert sort; I hope I have it right.)

(insert_sort $List $Sorted)
    (i_sort $List [] $Sorted)

(i_sort [] $Acc $Acc)

(i_sort [$H|$T] $Acc $Sorted)
    (insert $H $Acc $NAcc)
    (i_sort $T $NAcc $Sorted)
   
(insert $X [$Y|$T] [$Y|$NT])
    ($X > $Y)
    (insert $X $T $NT)

(insert $X $T $XY)
    (append [$X] $T $XY) 

Then one can query, say

(insert_sort [1 3 1 11 4] $List)
Query succeeded: (insert_sort [1 3 1 11 4] [1 1 3 4 11])

This does, however, depend on having some way of ordering things. So it works for numbers, which we can order with the predicate ($A < $B). If you wanted to sort something else, you would also need to define a predicate equivalent to less than. You don’t need a predicate for equality or greater than, because all cases except less than are dealt with by the second definition of insert. But Dialog does not, as far as I know, have any built in way of comparing strings or objects, so that would be an additional hurdle.

3 Likes

I also tried my hand at writing a sorting function (independently, before I saw Paul’s solution), but I’m not well-versed in Dialog.

While in some respects our versions are very similar, since I also did a variant of Insertion Sort, Paul’s version is clearly more elegant and more idiomatic Prolog/Dialog-style. :+1:

Because I already put in the work and I have some comments & test cases, I thought I’d share my version, too.

Basically, it consists of a function which inserts an element into an already sorted list, and another function which uses the first function on our list elements one by one to build up the result.

%% parameters:
%% $list - the list into which we want to insert the element;
%%         we assume it is already sorted
%% $elem - the element we want to insert
%% $result - where the result will be stored
(insertIntoSorted $list $elem $result)
    (if) (empty $list) (then)
        ($result = [$elem])
    (else)
        ([$first | $rest] = $list)
        (if) {($elem < $first) (or) ($elem = $first)} (then)
            %% we can put the element in front of the whole list
            ($result = [$elem | $list])
        (elseif) (last $list $last) {($elem > $last) (or) ($elem = $last)} (then) 
            %% it is not strictly necessary to treat this as a 
            %% special case, but it avoids going into the recursion
            %% when we can just tack the element onto the end
            %% (note that this only kicks in, if it does, directly at
            %% the start of the process; since we otherwise go through
            %% the list from left to right dividing it into first and rest,
            %% only the first element will change in the recursion,
            %% not the last element)
            (append $list [$elem] $result)
        (else)
            %% we go into recursion to find the proper place
            %% for $elem in the $rest of our list
            (insertIntoSorted $rest $elem $newRest)
            ($result = [$first | $newRest])
        (endif)
    (endif)

%% parameters:
%% $accu(mulator) - pass empty list on first call
%% $list - the list to be sorted
%% $totalResult - where the result will be stored
(sort $accu $list $totalResult)
    (if) (empty $list) (then)
        ($totalResult = $accu)
    (else)
        ([$first | $rest] = $list)
        %% Inserting $first into $accu.
        (insertIntoSorted $accu $first $newAccu)
        %% Accumulated sorted list is $newAccu, remaining is $rest.
        (sort $newAccu $rest $totalResult)
    (endif)

(program entry point)
    (display memory statistics)
    (par)
    First we test only insertIntoSorted:(line)
    (insertIntoSorted [2 3 4 5] 1 $sortedList1)
    Result 1 is $sortedList1.(line)
    (insertIntoSorted [1 2 4 5] 3 $sortedList2)
    Result 2 is $sortedList2.(line)
    (insertIntoSorted [1 2 3 4] 5 $sortedList3)
    Result 3 is $sortedList3.(line)
    (insertIntoSorted [1 2 3 4] 2 $sortedList4)
    Result 4 is $sortedList4.(line)
    (par)
    (display memory statistics)
    (par)
    Testing sort:(line)
    (sort [] [1 2 3 4 5 6 7 8 9 10 11 12] $sortResult1)
    Result 1 is $sortResult1.
    (par)
    (display memory statistics)
    (par)
    (sort [] [12 11 10 9 8 7 6 5 4 3 2 1] $sortResult2)
    Result 2 is $sortResult2.
    (par)
    (display memory statistics)
    (par)
    (sort [] [8 12 3 9 5 11 2 7 10 1 6 4] $sortResult3)
    Result 3 is $sortResult3.
    (par)
    (display memory statistics)
    (par)
    (sort [] [12 14 42 8 41 26 37 2 32 43 3 6 24 19 45 48 11 23 38 20 27 39 34 9 29 17 30 13 46 7 10 22 28 33 4 40 1 25 5 49 31 16 18 15 21 44 36 50 47 35] $sortResult4)
    Result 4 is $sortResult4.
    (par)
    (display memory statistics)

There are two drawbacks to keep in mind:

  1. It’s not a super-efficient sorting algorithm in general. I’ll leave the implementation of QuickSort and MergeSort as an exercise for the reader. :slight_smile:
    (But I think for small lists, runtime considerations won’t matter.)

  2. The bigger drawback is that it is quite memory-hungry due to the recursion. If you want to get serious about sorting lists with that approach, you might at some point get the error message: “Technical trouble: Heap space exhausted.”

In that case, it can help to compile with the -H option to reserve more memory.
Taking a look at the memory statistics, the above example already comes quite close to the default limit of 1000 heap words after several consecutive sortings of 12 items each. And it will throw the error on the last list with 50 entries. If we bump up the setting by compiling with -H 8192 (which I think is the maximum value, at least for z8?), it works.

2 Likes

Nice! And very well explained. There are always lots of ways to do the same thing, when it comes to sorting.

I make no claims for efficiency in my case, and I haven’t even checked memory use. Since the algorithms are the same, I can’t see why mine would be any better in practice, but I don’t have a good grasp of how dialog handles these things.

1 Like

Thanks for the exceptionally good advices!

1 Like