Наиболее общее ограничение высшего порядка, описывающее последовательность целых чисел, упорядоченных относительно отношения

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

3 ответа

Hoogle был не очень полезен, но Hayoo это!

foldcmpl

так что это особая форма сгиба для списка, но она не применяется length list раз, но в один раз меньше.

isSortedBy

не совсем общий в своем названии, но в своей подписи. Возможно, настаивать на самом общем названии не так уж полезно. Иначе у нас просто есть сущности?

Определение гласит:

Функция isSortedBy возвращает True, если предикат возвращает true для всех смежных пар элементов в списке.

Может быть: all_adjacent_pairs(R_2, Xs), который звучит немного после того, как конструкция цикла, которая имеет adjacent_pair как некоторый модификатор.

Это вдохновлено инструментарием функциональных идиом высшего порядка, которые я когда-то реализовал. В то время я обнаружил, что угловые дела мучительны, я до сих пор этим занимаюсь:) Кроме того, поиск хороших имен - это всегда проблема...

Рассмотрим мета-предикат 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

Что касается имен: ИМО 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]].

Совершенно в том же духе, что и mapadj/4 представлены в более раннем ответе... может быть, имя лучше.

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

Образец использования:

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

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

Куда это может нас привести?

  • forallAdj => existAdj
  • возможно варианты с индексом (forallAdjI, existAdjI) как в модуле Collections.List (F#)
  • findfirstAdj/pickfirstAdj также как F# find/pick
Другие вопросы по тегам