Подтвердить что ты не робот

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

В CLP (FD) нам часто нужно указать: "Это список целых чисел и конечных доменных переменных в (иногда: строго) порядке возрастания/убывания".

Существует ли какая-либо CLP (FD) система, которая предоставляет общее (параметризуемое) встроенное ограничение для этой задачи?

SWI-Prolog предоставляет ограничение под названием chain/2, которое похоже на то, что я ищу. Однако имя немного слишком специфично, чтобы охватить все отношения, которые может описывать ограничение (например: #< не является частичным порядком, но допустимым в chain/2, что приводит к последовательности — взято как набор целых чисел — no более длинный подсчет как цепочка, определенная в математической теории порядка). Следовательно, имя не полностью описывает то, что на самом деле реализует ограничение.

Пожалуйста, дайте самое общее определение относительно обычных двоичных ограничений 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).

4b9b3361

ОТВЕТЫ

Ответ 1

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

foldcmpl

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

isSortedBy

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

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

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

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

Ответ 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]].

Ответ 3

В том же духе, что и 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 Module (F #)
  • findfirstAdj/pickfirstAdj также как F # find/pick