Prolog check list of numbers are in order

Question

I would like to be able to take a list of numbers and get the largest sequence of numbers that are in order. For example:

?- in_order([1,2,3,4,5],N).
N = 5.                              % expected result

?- in_order([1,2,5,6,7,8,4],N).
N = 4.                              % expected result

I have so far produced some basic code that counts up the length of a sequence of numbers but once the list is empty, it back tracks, hence the number returned N, is the same as the first element in the list. I know that I need to stop back tracking but can't seem to do it. Would someone be kind enough to point me in the correct direction.

My code so far (all be it be a bit hacky):

in_order([],_) :-
   !.
in_order([H|T],N):-
   (  var(N), 
      N is H 
   ;  true
   ),
   H = N,
   M is N+1,
   in_order(T,M).

I do understand that my current solution would not work in the 2nd example given, and pointers for that aspect would again be helpful, as I'm not too sure how to tackle that aspect. I'm using SICStus Prolog.

Many thanks in advance!

Answer 1

Let me call that relation zs_maxInOrder/2, it is based on clpfd and uses reified constraints:

:- use_module(library(clpfd)).

zs_maxInOrder([]    ,0).
zs_maxInOrder([Z|Zs],N) :-
    zs_prev_n_max0_max(Zs,Z,1,1,N).            % use "lagging" 

zs_prev_n_max0_max([]     ,_ ,_ ,M ,M).
zs_prev_n_max0_max([Z1|Zs],Z0,N0,M0,M) :-
    Z1 #= Z0 + 1 #<=> B,                       % with SWI-Prolog use `(#<==>)/2`
    N1 #= N0 * B + 1,
    M1 #= max(M0,N1),
    zs_prev_n_max0_max(Zs,Z1,N1,M1,M).

Let's see it in action using SICStus Prolog 4.3.1:

?- zs_maxInOrder([1,2,3,4,5],N).
N = 5 ? ;
no
?- zs_maxInOrder([1,2,5,6,7,8,4],N).
N = 4 ? ;
no

What about corner cases?

?- zs_maxInOrder([1],N).
N = 1 ? ;
no
?- zs_maxInOrder([],N).
N = 0 ? ;
no

Answer 2

Here is a rather brute force solution to the problem :P ( I know I'll get criticized, but I couldn't resist playing with the higher-order predicates ).

my_prefix(List,Prefix) :- 
   append(Prefix,_,List).

my_suffix(List,Suffix) :- 
   append(_,Suffix,List).

my_sublist(List,Sublist) :-
   my_suffix(List,Suffix),
   my_prefix(Suffix,Sublist).

all_sublists(List,AllSublists) :- 
   findall(Sub,my_sublist(List,Sub),AllSublists).

good_list([]) :- 
   !.
good_list([H]) :- 
   !.
good_list([H1,H2|T]) :- 
   H1 is H2-1,
   good_list([H2|T]),
   !.

in_order(List,Length) :-
   all_sublists(List,AllSublists),
   findall(L,(member(Sublist,AllSublists),
              good_list(Sublist),
              length(Sublist,L)),
             InOrderSizes),
   max_list(InOrderSizes,Length).