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

В 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_([], _). 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 Solutions collect form web for “Наиболее общее ограничение высшего порядка, описывающее последовательность целых чисел, упорядоченных относительно отношения”

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

Что касается имен: 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 который был предложен в предыдущем ответе на 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). 

Чтобы показать это, давайте определим 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 и splitlistIf/3 … здесь 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 Module (F #)
  • findfirstAdj / pickfirstAdj также нравится F # find / pick
Interesting Posts

Устранение неполадок использования центрального процессора с помощью процесса «Система»

Отображение файлов (например, изображений), хранящихся на Google Диске, на веб-сайте

Создайте нового пользователя в MySQL и дайте ему полный доступ к одной базе данных

Как определяется размер кучи Java по умолчанию?

Как создать точную копию массива?

Как я могу получить доступ к теневой глобальной переменной в C?

dplyr суммировать: Эквивалент «.drop = FALSE» для сохранения групп с нулевой длиной в выходе

Порт 1 Гбит / с в полнодуплексном режиме составляет 1 Гбит / с и 1 Гбит / с?

Настройка взаимодействия с сервером с двумя мониторами поверх клиента с одним монитором

Настройка OpenFileDialog

NullPointerException: println нуждается в сообщении в android

Действительно ли обработчики GCC и Clang действительно написаны?

Как создать и сохранить группу контактов в Skype?

Команда для просмотра всех команд Windows

Как подключить устройство HDMI к входу VGA

Давайте будем гением компьютера.