I have this insertion sort to sort a list in descending order in Prolog and it works:
insert(X,[],[X]).
insert(X, [Y|Tail], [X,Y|Tail]):- X > Y, !.
insert(X, [Y|Tail], [Y|NTail]):- insert(X, Tail, NTail).
ins_sort([], []).
ins_sort([X|Tail], Sorted):- ins_sort(Tail, STail), insert(X, STail, Sorted).
I am running it on SWISH and trying to understand how it functions with the following trace:
Call:ins_sort([1, 2, 3, 4, 5], _12162)
Call:ins_sort([2, 3, 4, 5], _12358)
Call:ins_sort([3, 4, 5], _12358)
Call:ins_sort([4, 5], _12358)
Call:ins_sort([5], _12358)
Call:ins_sort([], _12358)
Exit:ins_sort([], [])
Call:insert(5, [], _12360)
Exit:insert(5, [], [5])
Exit:ins_sort([5], [5])
Call:insert(4, [5], _12366)
Call:4>5
Fail:4>5
Redo:insert(4, [5], _12370)
Call:insert(4, [], _12282)
Exit:insert(4, [], [4])
Exit:insert(4, [5], [5, 4])
Exit:ins_sort([4, 5], [5, 4])
Call:insert(3, [5, 4], _12378)
Call:3>5
Fail:3>5
Redo:insert(3, [5, 4], _12382)
Call:insert(3, [4], _12294)
Call:3>4
Fail:3>4
Redo:insert(3, [4], _12294)
Call:insert(3, [], _12300)
Exit:insert(3, [], [3])
Exit:insert(3, [4], [4, 3])
Exit:insert(3, [5, 4], [5, 4, 3])
Exit:ins_sort([3, 4, 5], [5, 4, 3])
Call:insert(2, [5, 4, 3], _12396)
Call:2>5
Fail:2>5
Redo:insert(2, [5, 4, 3], _12400)
Call:insert(2, [4, 3], _12312)
Call:2>4
Fail:2>4
Redo:insert(2, [4, 3], _12312)
Call:insert(2, [3], _12318)
Call:2>3
Fail:2>3
Redo:insert(2, [3], _12318)
Call:insert(2, [], _12324)
Exit:insert(2, [], [2])
Exit:insert(2, [3], [3, 2])
Exit:insert(2, [4, 3], [4, 3, 2])
Exit:insert(2, [5, 4, 3], [5, 4, 3, 2])
Exit:ins_sort([2, 3, 4, 5], [5, 4, 3, 2])
Call:insert(1, [5, 4, 3, 2], _12162)
Call:1>5
Fail:1>5
Redo:insert(1, [5, 4, 3, 2], _12162)
Call:insert(1, [4, 3, 2], _12336)
Call:1>4
Fail:1>4
Redo:insert(1, [4, 3, 2], _12336)
Call:insert(1, [3, 2], _12342)
Call:1>3
Fail:1>3
Redo:insert(1, [3, 2], _12342)
Call:insert(1, [2], _12348)
Call:1>2
Fail:1>2
Redo:insert(1, [2], _12348)
Call:insert(1, [], _12354)
Exit:insert(1, [], [1])
Exit:insert(1, [2], [2, 1])
Exit:insert(1, [3, 2], [3, 2, 1])
Exit:insert(1, [4, 3, 2], [4, 3, 2, 1])
Exit:insert(1, [5, 4, 3, 2], [5, 4, 3, 2, 1])
Exit:ins_sort([1, 2, 3, 4, 5], [5, 4, 3, 2, 1])
I get lost once I get beyond the first "Exit". I understand all of the recursive calls until we get to an empty list, which stops the recursive calls because of the other fact and begins going back, but why after the first exit on line 7 does the undefined STail become an empty list [] in the insert call?
Has the exit of ins_sort([], []) set STail to an empty set [] and does this mean that the last argument of a fact is a return value or something?
I think the problem here is you are having some difficulty understanding what happens with variables during recursion. Let's take a simplified case:
count([], 0).
count([X|Xs], N) :- count(Xs, N0), succ(N0, N).
What happens when I call count([a,b], N) is this:
count([a, b], N)
+-> count([b], N)
The first thing we have to do upon entering count([a,b], N) is a recursive call to count/2. When Prolog re-enters count, we suddenly have a new set of bindings for X and Xs. In the outer call, X=a and Xs=[b], but in the inner call, X=b and Xs=[]. There will then be a third inner call, which begins with the Xs value []. This corresponds to the first three lines of this trace:
Call: (8) count([a, b], _8636) ? creep
Call: (9) count([b], _8866) ? creep
Call: (10) count([], _8866) ? creep
What the tracer is telling you here is "I am trying to enter this predicate with these values and variables." Note that the variable actually changed for N between the first and second calls.
Now, you'll notice that the [] cannot match the second clause, only the first. The first doesn't have a body but it does establish a binding. So the next line of the trace will reflect that:
Exit: (10) count([], 0) ? creep
See the numbers on the side? That's telling you the depth of the call stack. It's convenient to use numbers for traces instead of showing the nesting visually because eventually our call stacks are going to get pretty deep!
Now that we have a value for the variable, it's going to move on to the next expression in the clause we're in:
Call: (10) succ(0, _8866) ? creep
Exit: (10) succ(0, 1) ? creep
Nesting level went up one but was immediately resolved; this is par for the course with built-ins like succ/2. Now let's look at the rest of the trace:
Exit: (9) count([b], 1) ? creep
Call: (9) succ(1, _8636) ? creep
Exit: (9) succ(1, 2) ? creep
Exit: (8) count([a, b], 2) ? creep
So now that we had a binding for the recursive call, we can enter the next step in the parent call, and so on, until the whole call is resolved and we get 2.
Let's see it again, this time with nesting instead of numbers:
[trace] ?- count([a,b],N).
Call: (8) count([a, b], _8636) ? creep
Call: (9) count([b], _8866) ? creep
Call: (10) count([], _8866) ? creep
Exit: (10) count([], 0) ? creep
Call: (10) succ(0, _8866) ? creep
Exit: (10) succ(0, 1) ? creep
Exit: (9) count([b], 1) ? creep
Call: (9) succ(1, _8636) ? creep
Exit: (9) succ(1, 2) ? creep
Exit: (8) count([a, b], 2) ? creep
N = 2.
This should make what's going on in your own trace a little easier to understand.