最常见的高阶约束描述了关于关系排序的整数序列

Question

在CLP(FD)中,我们经常需要声明:"这是整数和有限域变量的列表(有时:严格地)升序/降序."

是否有任何CLP(FD)系统为此任务提供通用(参数化)内置约束？

SWI-Prolog提供了一个名为的约束chain/2,类似于我正在寻找的约束.但是,名称稍微过于具体,不能包含约束可以描述的所有关系(例如:#<不是部分顺序,但是可以接受chain/2,导致序列 - 作为一组整数 - 不再计算为链中定义的链数学顺序理论).因此,该名称并未完全描述约束实际实现的内容.

请给所述最一般相对于通常的二进制CLP(FD)约束定义-或包含至少一个合适的子集#<,#>,#=<和#>=- 包括根据代数结构的约束定义适当的名称.强加的条件是约束描述了在文献中具有正确名称的实际数学结构.

首先,请考虑使用SICStus Prolog或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).

示例案例:

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

请注意,它甚至可以被允许#\=,因为这种关系仍然可以描述数学顺序理论中已知的连接.因此,就通常的二进制CLP(FD)约束而言,上述代码不是最一般的.

Answer 1

Hoogle不是很有用,但Hayoo是!

foldcmpl

所以这是列表的折叠的一种特殊形式,但它不适用length list时间,但少一次.

isSortedBy

它的名字并不完全是通用的,而是它的签名.也许坚持最通用的名称并没有那么有用.否则我们只有实体？

定义如下:

如果谓词对列表中所有相邻元素对返回true,则isSortedBy函数返回True.

也许:all_adjacent_pairs(R_2, Xs).在具有adjacent_pair作为一些修饰符的循环构造之后听起来有点.

Answer 2

这是我曾经实现的功能性高阶习语工具箱的启发.那时我发现角落的情况很痛苦,我今天仍然这样做:)另外,找到好名字总是一个问题......

考虑元谓词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).

样品用途:

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

我知道在角落案件的裂痕As = []和As = [_],我仍然觉得这是接近"的所有相邻列表项",因为它得到.

此外,所有这些都可以轻松扩展:

• 下来mapadj/2(类似于chain/2,使用单例列表进行类型检查除外)
• 侧面,还有一个额外的国家论点,到foldadjl/n,scanadjl/n

关于名称:IMO l//r后缀是fold/ scan,但不是map.

编辑2015-04-26

这是前面提到的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).

编辑2015-04-27

这是元谓词splitlistIfAdj/3,基于 if_/3此在先前的 具体化答案中提出.

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

为了显示它的使用,我们定义dif/3的方式(=)/3与翻转的真值完全相同:

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

现在我们一起使用它们:

?- 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

如果我们推广一些列表项怎么办？我们是否通过正确的未决目标得到多个答案？

首先,一个小例子:

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

一个涉及两个变量X和一个更大的例子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]].

编辑2015-05-05

这是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).

样品用途:

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

编辑2015-05-15

等等,......这里是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))).

我们来使用它:

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