Сопряженное отношение по списку

Следующий предикат более высокого порядка преуспевает, если все пары элементов списка верны для данного отношения. Есть ли общее или лучшее, большее намерение, раскрывающее имя для этого отношения?

Моя оригинальная мотивация для этого имени заключалась в том, что в clpfd, часто существует ограничение all_different/1, которое описывается как истинное, если элементы попарно отличаются друг от друга. На самом деле, скорее, предпочитают говорить, что все элементы разные, но меня часто исправляли (другими программистами Пролога), чтобы использовать их по-разному. Фактически это ограничение теперь наиболее естественно выражается как pairwise(#\=, Zs).

pairwise(Rel_2, Xs) :-
   i_pairwise(Xs, Rel_2).

i_pairwise([], _).
i_pairwise([X|Xs], Rel_2) :-
   maplist(call(Rel_2,X),Xs),
   i_pairwise(Xs, Rel_2).

Как заметил @aBathologist, попарно не является правильным словом, потому что это может иметь смысл и для нерефлексивного Rel.

Кроме того, отношение Rel не является полным отношением, потому что call(Rel, X, X) может завершиться неудачей, но pairwise(Rel, Xs) может все еще сработать.

Я даже зацепился за (a->a->Bool)->[a]->Bool. Но Hayoo нашел его: name pairwise в отличие от потокового.

Посмотрел на МО и математику:

Ответы

Ответ 1

Мне очень нравится ваш вопрос. Я пошел копаться через википедию, чтобы попытаться найти подходящий термин. Я думаю о списке как о наборе, в том смысле, что каждый член является четким и дифференцируемым элементом, так что даже если бы были два экземпляра одного и того же атома, это были бы разные элементы, qua их позиция или что-то еще. Я думаю, что предикат, который вы описали, будет тогда бинарным отношением [connex] (https://en.wikipedia.org/wiki/Total_relation):

Бинарное отношение R над X называется коннексом, если для всех a и b из X такое, что a ≠ b, a связано с b или b, связано с (или обоими)

С другой стороны, если это отношение также должно быть рефлексивным, тогда оно будет описывать полное двоичное отношение (на той же странице, что и коннекс).

Однако, я думаю, что ваш предикат pairwise/2 на самом деле не соответствует описанию, которое вы даете, или (более вероятно) я не совсем понимаю.

Вы говорите, что предикат должен преуспеть "если все пары элементов списка верны для данного отношения". Но pairwise(>, [1,2,3]) является ложным, тогда как pairwise(<, [1,2,3]) истинно, а pairwise(>, [3,2,1]) - true, но pairwise(<, [3,2,1]) - false. Но из каждой пары элементов из этих списков одна больше другой.

Изменения:

Ниже приводится результат моего недоразумения и оказалось, что это не относится к вопросу.

Я предложил следующее определение, считая, что это может быть более точное определение того, что @false описывало, но он указал, что он не определяет отношения, которые, как я думал, он сделал. Я сохранил это ради того, чтобы сделать наш последующий обмен в комментариях понятным.

Добавление другого предложения, которое проверяет список в обратном порядке, решит эту проблему, но могут ли быть другие отношения, которые невозможно поймать путем обращения вспять? Кроме того, существует ли более эффективный способ реализации подлинной проверки connex?

connex_over(Rel, Xs) :-
   i_connex_over(Xs, Rel), !.
connex_over(Rel, Xs) :-
   reverse(Xs, Sx),
   i_connex_over(Sx, Rel).

i_connex_over([], _).
i_connex_over([X|Xs], Rel) :-
   maplist(call(Rel,X),Xs),
   i_connex_over(Xs, Rel).

После того, как @false указал мою ошибку в предыдущем, я написал следующее определение. Я считаю, что он описывает коннекцию над элементами S:

actual_connex_over(Rel, S) :-
   foreach( ( select(X, S, T), member(Y, T) ),
            ( call(Rel, X, Y) ; call(Rel, Y, X) )
          ).

Ответ 2

Такой предикат более высокого порядка, несомненно, будет очень полезен (пример: breaks/1).

Как и для семейства предикатов foldl/n, мнемоническое имя для этого должно, на мой взгляд, меньше ориентироваться на возникающую алгебраическую структуру, а на шаблон, который мы находим здесь. Например, этот шаблон несколько напоминает аккордеон, но это явно еще не хорошее имя. Кажется, существует обобщение foldl/4 или scanl/4 (или некоторая смесь), в пределах досягаемости которого этот шаблон является частным случаем.