Most general higher-order constraint describing a sequence of integers ordered with respect to a relation

Question

In CLP(FD), we frequently need to state: "This is a list of integers and finite domain variables in (sometimes: strictly) ascending/descending order."

Is there any CLP(FD) system that provides a general (parametrisable) built-in constraint for this task?

SWI-Prolog provides a constraint called chain/2, which is similar to what I am looking for. However, the name is slightly too specific to encompass all relations that the constraint can describe (example: #< is not a partial order but admissible in chain/2, leading to the sequence — taken as a set of integers — no longer counting as a chain as defined in mathematical order-theory). Hence, the name does not fully describe what the constraint actually implements.

Please give the most general definition with respect to the usual binary CLP(FD) constraints — or a suitable subset that contains at least #<, #>, #=< and #>= — including the proper name according to the algebraic structure the constraint defines. The condition imposed is that the constraint describe an actual mathematical structure that has a proper name in the literature.

As a start, consider with SICStus Prolog or SWI:

:- use_module(library(clpfd)).

connex(Relation_2, List) :-
    connex_relation(Relation_2),
    connex_(List, Relation_2).

connex_relation(#=).
connex_relation(#<).
connex_relation(#=<).
connex_relation(#>).
connex_relation(#>=).

connex_([], _).
connex_([L|Ls], Relation_2) :-
    foldl(adjacent(Relation_2), Ls, L, _).

adjacent(Relation_2, X, Prev, X) :- call(Relation_2, Prev, X).

Sample cases:

?- connex(#<, [A,B,C]).
A#=<B+-1,
B#=<C+-1.

?- connex(#=, [A,B,C]).
A = B, B = C,
C in inf..sup.

?- maplist(connex(#<), [[A,B],[C,D]]).
A#=<B+-1,
C#=<D+-1.

Notice that it would even be admissible to allow #\=, because the relation would still describe a connex as known in mathematical order-theory. Hence, the code above is not most general with respect to the usual binary CLP(FD) constraints.

Answer 1

Hoogle was not very useful, but Hayoo is!

foldcmpl

so this is a special form of fold for a list, but it does not apply length list times but one time less.

isSortedBy

is not entirely general in its name, but in its signature. Maybe insisting on the most general name is not that helpful. Otherwise we just have entities all over?

The definition reads:

The isSortedBy function returns True iff the predicate returns true for all adjacent pairs of elements in the list.

Maybe: all_adjacent_pairs(R_2, Xs). which sounds a bit after having a looping construct that has adjacent_pair as some modifier.

Answer 2

This is inspired by a toolbox of functional higher-order idioms I once implemented. Back then I found the corner cases agonizing, I still do today:) Also, finding good names is always an issue...

Consider meta-predicate mapadj/4:

mapadj(Relation_4,As,Bs,Cs) :-
   list_list_list_mapadj(As,Bs,Cs,Relation_4).

list_list_list_mapadj([],[],[],_).
list_list_list_mapadj([A|As],Bs,Cs,Relation_4) :-
   list_prev_list_list_mapadj(As,A,Bs,Cs,Relation_4).

list_prev_list_list_mapadj([],_,[],[],_).
list_prev_list_list_mapadj([A1|As],A0,[B|Bs],[C|Cs],Relation_4) :-
   call(Relation_4,A0,A1,B,C),
   list_prev_list_list_mapadj(As,A1,Bs,Cs,Relation_4).

Sample uses:

z_z_sum_product(X,Y,Sum,Product) :-
   Sum     #= X + Y,
   Product #= X * Y.

:- mapadj(z_z_sum_product,[],       [],     []).
:- mapadj(z_z_sum_product,[1],      [],     []).

:- mapadj(z_z_sum_product,[1,2],    [3],    [2]).
:- mapadj(z_z_sum_product,[1,2,3],  [3,5],  [2,6]).
:- mapadj(z_z_sum_product,[1,2,3,4],[3,5,7],[2,6,12]).

I'm aware of the rift in the corner cases As = []and As = [_], still I feel this is as close to "for all adjacent list items" as it gets.

Also, all of this can easily be extended:

• down to mapadj/2 (akin to chain/2, except for the type-check with singleton lists)
• sideways, with an additional state argument, to foldadjl/n, scanadjl/n

Regarding names: IMO the l / r suffix is required with fold / scan, but not with map.

---

Edit 2015-04-26

Here comes the before-mentioned foldadjl/4:

foldadjl(Relation_4,Xs) -->
   list_foldadjl(Xs,Relation_4).

list_foldadjl([],_) -->
   [].
list_foldadjl([X|Xs],Relation_4) -->
   list_prev_foldadjl(Xs,X,Relation_4).

list_prev_foldadjl([],_,_) -->
   [].
list_prev_foldadjl([X1|Xs],X0,Relation_4) -->
   call(Relation_4,X0,X1),
   list_prev_foldadjl(Xs,X1,Relation_4).

---

Edit 2015-04-27

Here comes meta-predicate splitlistIfAdj/3, based on if_/3 which was proposed in a previous answer on reification.

split_if_adj(P_3,As,Bss) :- splitlistIfAdj(P_3,As,Bss).

splitlistIfAdj(P_3,As,Bss) :- 
   list_split_(As,Bss,P_3).

list_split_([],[],_).
list_split_([X0|Xs],     [Cs|Bss],P_3) :-
   list_prev_split_(Xs,X0,Cs,Bss, P_3).

list_prev_split_([],     X, [X],[],_).
list_prev_split_([X1|Xs],X0,[X0|Cs],Bss,P_3) :-
   if_(call(P_3,X0,X1), 
       (Cs = [],  Bss = [Cs0|Bss0]),
       (Cs = Cs0, Bss = Bss0)),
   list_prev_split_(Xs,X1,Cs0,Bss0,P_3).

To show it in use let's define dif/3 exactly the same way as (=)/3 but with flipped truth-value:

dif(X, Y, R) :- X == Y,    !, R = false.
dif(X, Y, R) :- ?=(X, Y),  !, R = true. % syntactically different
dif(X, Y, R) :- X \= Y,    !, R = true. % semantically different
dif(X, Y, R) :- R == false, !, X = Y.
dif(X, X, false).
dif(X, Y, true) :-
   dif(X, Y).

Now we use them in tandem:

?- splitlistIfAdj(dif,[1,2,2,3,3,3,4,4,4,4],Pss).
Pss = [[1],[2,2],[3,3,3],[4,4,4,4]].      % succeeds deterministically

What if we generalize some list items? Do we get multiple answers with the right pending goals?

First, a small example:

?- splitlistIfAdj(dif,[1,X,2],Pss).
X = 1,             Pss = [[1,1],[2]]  ;
X = 2,             Pss = [[1],[2,2]]  ;
dif(X,1),dif(X,2), Pss = [[1],[X],[2]].

A somewhat bigger example involving the two variables X and Y.

?- splitlistIfAdj(dif,[1,2,2,X,3,3,Y,4,4,4],Pss).
X = 2,             Y = 3,             Pss = [[1],[2,2,2],[3,3,3],[4,4,4]]    ;
X = 2,             Y = 4,             Pss = [[1],[2,2,2],[3,3],[4,4,4,4]]    ;
X = 2,             dif(Y,3),dif(Y,4), Pss = [[1],[2,2,2],[3,3],[Y],[4,4,4]]  ;
X = Y,             Y = 3,             Pss = [[1],[2,2],[3,3,3,3],[4,4,4]]    ;
X = 3,             Y = 4,             Pss = [[1],[2,2],[3,3,3],[4,4,4,4]]    ;
X = 3,             dif(Y,3),dif(Y,4), Pss = [[1],[2,2],[3,3,3],[Y],[4,4,4]]  ;
dif(X,2),dif(X,3), Y = 3,             Pss = [[1],[2,2],[X],[3,3,3],[4,4,4]]  ;
dif(X,2),dif(X,3), Y = 4,             Pss = [[1],[2,2],[X],[3,3],[4,4,4,4]]  ;
dif(X,2),dif(X,3), dif(Y,3),dif(Y,4), Pss = [[1],[2,2],[X],[3,3],[Y],[4,4,4]].

---

Edit 2015-05-05

Here's tpartition/4:

tpartition(P_2,List,Ts,Fs) :- tpartition_ts_fs_(List,Ts,Fs,P_2).

tpartition_ts_fs_([],[],[],_).
tpartition_ts_fs_([X|Xs0],Ts,Fs,P_2) :-
   if_(call(P_2,X), (Ts = [X|Ts0], Fs = Fs0),
                    (Ts = Ts0,     Fs = [X|Fs0])),
   tpartition_ts_fs_(Xs0,Ts0,Fs0,P_2).

Sample use:

?- tpartition(=(0), [1,2,3,4,0,1,2,3,0,0,1], Ts, Fs).
Ts = [0, 0, 0],
Fs = [1, 2, 3, 4, 1, 2, 3, 1].

---

Edit 2015-05-15

On and on, ... here's splitlistIf/3:

split_if(P_2,As,Bss) :- splitlistIf(P_2,As,Bss).

splitlistIf(P_2,As,Bss) :-
   list_pred_split(As,P_2,Bss).

list_pred_split([],_,[]).
list_pred_split([X|Xs],P_2,Bss) :-
   if_(call(P_2,X), list_pred_split(Xs,P_2,Bss),
                    (Bss = [[X|Ys]|Bss0], list_pred_open_split(Xs,P_2,Ys,Bss0))).

list_pred_open_split([],_,[],[]).
list_pred_open_split([X|Xs],P_2,Ys,Bss) :-
   if_(call(P_2,X), (Ys = [],      list_pred_split(Xs,P_2,Bss)),
                    (Ys = [X|Ys0], list_pred_open_split(Xs,P_2,Ys0,Bss))).

Let's use it:

?- splitlistIf(=(x),[x,1,2,x,1,2,3,x,1,4,x,x,x,x,1,x,2,x,x,1],Xs).
Xs = [[1, 2], [1, 2, 3], [1, 4], [1], [2], [1]].

Answer 3

Quite in the same vein as mapadj/4 presented in an earlier answer... maybe the name is better.

forallAdj(P_2,Xs) :-
   list_forallAdj(Xs,P_2).

list_forallAdj([],_).
list_forallAdj([X|Xs],P_2) :-
   list_forallAdj_prev(Xs,P_2,X).

list_forallAdj_prev([],_,_).
list_forallAdj_prev([X1|Xs],P_2,X0) :-
   call(P_2,X0,X1),
   list_forallAdj_prev(Xs,P_2,X1).

Sample use:

:- use_module(library(clpfd)).
:- use_module(library(lambda)).

?- Ls = [0,_,_,_,_,_], forallAdj(\X0^X1^(X0 + 1 #= X1), Ls).
Ls = [0, 1, 2, 3, 4, 5].

Where could that take us?

• forallAdj => existAdj
• maybe variants with index (forallAdjI, existAdjI) like in Collections.List Module (F#)
• findfirstAdj/pickfirstAdj also like F# find/pick