Попарное отношение по списку

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

Моя первоначальная мотивация для этого имени заключалась в том, что в 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 нашел: имя pairwise в отличие от точечного.

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


terminology prolog meta-predicate clpfd
person false    schedule 08.04.2014    source источник
comment
Почему вы определяете i_pairwise вместо определения метода в pairwise_level?   -  person Willem Van Onsem    schedule 09.04.2014
comment
@CommuSoft: это только для использования индексации 1-го аргумента в нескольких системах Prolog - некоторым этот обход не нужен, но это не повредит.   -  person false    schedule 09.04.2014
comment
@false Из любопытства, почему вы указываете, что вторым аргументом должен быть список списков в подписи Haskell?   -  person Shon    schedule 09.04.2014
comment
@aBathologist: исправлено! Это не имело значения, хотя   -  person false    schedule 09.04.2014
comment
Как насчет pairwise//2? Возможное использование?   -  person repeat    schedule 10.10.2015

Ответы (2)


arrow_upward
6
arrow_downward

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

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

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

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

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

Редактирует:

Следующее является результатом моего непонимания и оказалось не относящимся к вопросу.

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

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

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) )
          ).
person Shon    schedule 09.04.2014
comment
Я считаю, что полезно разрешить некоммутативные отношения, такие как >. Но я согласен, что попарно это не то слово. - person false; 09.04.2014
comment
@false Как вы думаете, этот коннекс подходит для отношения? Я может упускаю суть... - person Shon; 09.04.2014
comment
@false не хотел спешить... ;) - person Shon; 09.04.2014
comment
Вы верите, что реализовали коннекс? Я думаю (на данный момент просто предположил), что ваше определение слишком специализировано: может быть связь с другой перестановкой, отличной от обратной, и может быть связь, требующая другой формулировки. Ведь коннекс — это: ∀ a, b ∈ X, (a R b) ∨ (b R a) ∨ (a=b). Таким образом, дизъюнкция очень локальна. - person false; 09.04.2014
comment
Подумайте: connex_over(>,[1,3,2]) Очевидно, это связь, но ваш предикат не работает. - person false; 09.04.2014
comment
@false В моем бессонном состоянии, когда я публиковал комментарий, я думал, что мое определение может сработать. Я знал, что достаточно решить один контрпример, который я изложил в своем ответе, но я подозревал, что это слишком упрощенно (отсюда мои вопросы и неуверенность) --- в свете большего количества сна и ваших замечаний очевидно, что мой предикат не определяет связь. Я думаю, что смог определить это в новом предикате, который я добавил к своему ответу, но я сомневаюсь, что это самое эффективное решение. - person Shon; 10.04.2014
comment
@false Что еще более важно, я понял из ваших ответов и изменений в вашем ответе, что порядок элементов должен иметь значение, чтобы ваш предикат был более точным, чем ваше прозаическое описание? (Если я не ошибаюсь в прозе. Я отмечу здесь свой статус простого любителя / энтузиаста, чтобы мои замечания не были переоценены). - person Shon; 10.04.2014
comment
Название произошло от pairwise(#\=,Zs), что означает all_different(Zs). Сначала я не думал об этом больше, чем об этом. Но да, я да, я думаю, что порядок должен иметь значение. Тем не менее, что-то вроде connex тоже подойдет - скорее в пряморекурсивной манере, поскольку это позволит использовать в контексте ограничений. - person false; 10.04.2014
comment
Мета-примечание: если у вас есть другой ответ, вы также можете написать его здесь в отдельном ответе! - person false; 10.04.2014
comment
В любом случае +1 за нахождение коннекса вообще! - person mat; 08.02.2015

arrow_upward
4
arrow_downward

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

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

person mat    schedule 24.11.2014