sortingprologmergesorttail-recursion

# How to collect maximal non-overlapping ascending/descending prefixes of a random sequence of numbers

Let S = [x1, x2, ..., xn] be a random sequence of distinct numbers. We can define a run of S as:

• a sequence [x1, x2, ..., xi], for 1 ≤ i ≤ n, such that x1 < x2 < ... < xi, and i = n or xi > xi+1; or
• a sequence [xi, xi-1, ..., x1], for 1 ≤ i ≤ n, such that x1 > x2 > ... > xi, and i = n or xi < xi+1.

The predicate `runs/2` collects all runs of a given sequence of distinct numbers (for successive non-overlapping ascending or descending prefixes).

``````% runs(+Sequence, -Runs)

runs([], []).
runs([X|Xs], [Run|Runs]) :-
run(Xs, X, Run, Rest),
runs(Rest, Runs).

run([], X, [X], []).
run([X1|Xs], X0, Run, Rest) :-
compare(Order, X0, X1),
run_case(Order, X0, X1, Xs, Run, Rest).

run_case(<, X0, X1, Xs, [X0|Run], Rest) :-
ascending(Xs, X1, Run, Rest).

run_case(>, X0, X1, Xs, Run, Rest) :-
descending(Xs, X1, [X0], Run, Rest).

% for an ascending prefix, the run is built up as a QUEUE

ascending([], X0, [X0], []).
ascending([X1|Xs], X0, [X0|Run0], Rest) :-
(   X0 @> X1
->  Run0 = [],
Rest = [X1|Xs]
;   ascending(Xs, X1, Run0, Rest) ).

% for a descending prefix, the run is built up as a STACK

descending([], X0, Run, [X0|Run], []).
descending([X1|Xs], X0, Run0, Run, Rest) :-
(   X0 @< X1
->  Run = [X0|Run0],
Rest = [X1|Xs]
;   descending(Xs, X1, [X0|Run0], Run, Rest) ).
``````

Example:

``````?- runs([1, 2, 9, 8, 5, 3, 7, 6, 4, 0], R).
R = [[1, 2, 9], [3, 5, 8], [0, 4, 6, 7]].
``````

PROBLEM: How to extend this code to deal with sequences containing repeating numbers:

• modifying only the predicates `run/3` and `run_case/6` (in the latter, the arity can be changed);
• without explicitly using the predicate `reverse/2`;
• without processing the same item more than once;
• using only tail-recursive predicates; and
• the predicate `runs/2` must take time O(n).

After the modifications, the predicate `run/2` should work as follows:

``````?- runs([5, 5, 3, 2, 2, 4, 4, 7, 6, 6, 1, 7, 8, 8, 9], Runs).
Runs = [[2, 2, 3, 5, 5], [4, 4, 7], [1, 6, 6], [7, 8, 8, 9]].
``````

MOTIVATION: The predicate `runs/2` helps to implement a (bottom-up) version of natural merge sort that takes time O(n) to sort sequences that are already sorted (ascending or descending), as well as greatly reducing the execution time to sort sequences that are already "almost ordered".

Solution

• I came up with this (ascending and descending remain the same):

``````runs([], []).
runs([X|Xs], [Run|Runs]) :-
run(Xs, X, [X|Tail]-Tail, Run, Rest),
runs(Rest, Runs).

run([], _, Run-[], Run, []).
run([X1|Xs], X0, LInit-Tail, Run, Rest):-
compare(Order, X0, X1),
run_case(Order, X1, LInit-Tail, Xs, Run, Rest).

run_case(=, X1, LInit-[X1|Tail], Xs, Run, Rest) :-
run(Xs, X1, LInit-Tail, Run, Rest).

run_case(<, X1, LInit-Run, Xs, LInit, Rest) :-
ascending(Xs, X1, Run, Rest).

run_case(>, X1, LInit-[], Xs, Run, Rest) :-
descending(Xs, X1, LInit, Run, Rest).

% for an ascending prefix, the run is built up as a QUEUE

ascending([], X0, [X0], []).
ascending([X1|Xs], X0, [X0|Run0], Rest) :-
(   X0 @> X1
->  Run0 = [],
Rest = [X1|Xs]
;   ascending(Xs, X1, Run0, Rest) ).

% for a descending prefix, the run is built up as a STACK

descending([], X0, Run, [X0|Run], []).
descending([X1|Xs], X0, Run0, Run, Rest) :-
(   X0 @< X1
->  Run = [X0|Run0],
Rest = [X1|Xs]
;   descending(Xs, X1, [X0|Run0], Run, Rest) ).

``````

Sample runs:

``````?- runs([1, 2, 9, 8, 5, 3, 7, 6, 4, 0], R).
R = [[1, 2, 9], [3, 5, 8], [0, 4, 6, 7]].

?- runs([5, 5, 3, 2, 2, 4, 4, 7, 6, 6, 1, 7, 8, 8, 9], Runs).
Runs = [[2, 2, 3, 5, 5], [4, 4, 7], [1, 6, 6], [7, 8, 8, 9]].
``````