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

Question

Let S = [x₁, x₂, ..., x_n] be a random sequence of distinct numbers. We can define a run of S as:

• a sequence [x₁, x₂, ..., x_i], for 1 ≤ i ≤ n, such that x₁ < x₂ < ... < x_i, and i = n or x_i > x_i+1; or
• a sequence [x_i, x_i-1, ..., x₁], for 1 ≤ i ≤ n, such that x₁ > x₂ > ... > x_i, and i = n or x_i < x_i+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".

Answer 1

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]].