Равенство двух списков переменных

Как определить мета-логический предикат, который проверяет (то есть успешно или только неуспешно), если два списка уникальных переменных содержат точно такие же переменные, используя встроенные модули из текущего стандарта ISO (ISO / IEC 13211-1: 1995, включая Cor.2).

Другими словами, предикат должен быть успешным, если один список уникальных переменных является перестановкой другого. По аналогии с library(ordsets), назовем этот мета-логический предикат varset_seteq(As, Bs).

Обратите внимание, что, в отличие от ord_seteq/2, этот предикат не может быть просто As == Bs.


prolog iso-prolog
person false    schedule 13.01.2015    source источник
comment
Должен ли предикат завершиться ошибкой, если какой-либо из двух его аргументов не является списком уникальных переменных?   -  person Tudor Berariu    schedule 13.01.2015
comment
Просто жду, может есть еще и разные ответы.   -  person false    schedule 13.01.2015
comment
Я пробовал что-то другое, но мне нужно было проверить, действительно ли As и Bs являются наборами свободных переменных. В моем ответе это гарантируется тем фактом, что они должны объединяться со вторым аргументом term_variables/2.   -  person Tudor Berariu    schedule 13.01.2015
comment
Нет, это не гарантируется, вы тоже должны это предполагать. varset_seteq([A+B,a],[]) успешно работает во многих системах (по умолчанию). ... и объединяет аргументы.   -  person false    schedule 13.01.2015
comment
Я понимаю почему. Спасибо. Я добавил это наблюдение к своему ответу.   -  person Tudor Berariu    schedule 13.01.2015

Ответы (4)


arrow_upward
14
arrow_downward

Предлагаемое мной решение использует term_variables/2, чтобы проверить, не имеет ли Bs дополнительных переменных по сравнению с As и что As не имеет переменной, которая не отображается в Bs.

varset_seteq(As, Bs):-
    term_variables(As-Bs, As),
    term_variables(Bs-As, Bs).

Вышеупомянутое решение можно обмануть, используя аргументы, которые не являются наборами свободных переменных:

 | ?- varset_seteq([A], [a]).

 A = a

 yes

Чтобы этого не произошло, унификацию можно заменить тестом на эквивалентность:

varset_seteq(As, Bs):-
    term_variables(As-Bs, A0),
    A0 == As,
    term_variables(Bs-As, B0),
    B0 == Bs.
person Tudor Berariu    schedule 13.01.2015
comment
Ваш контрпример действительно лучший! Жалко, потому что в противном случае term_variables/2 мог бы использовать тот факт, что ему все равно нужно проверять правильность своего второго аргумента, поэтому подсчет его длины является бесплатным, что затем может быть использовано для отказа раньше. - person false; 13.01.2015
comment
Мне нравится такой подход! Но разве вам не нужно также проверять, являются ли списки просто барами? Я сейчас не на своем компьютере, но varset_seteq([A,B,a], [A,B]) это не получится? - person Shon; 25.02.2015
comment
Нет, не получится. Что такое бар? - person Tudor Berariu; 25.02.2015
comment
О, да. Виноват. У меня мозг закоротил. Я вижу: потому что вы проверяете каждый список переменных на соответствующие списки. Думаю, очень хорошее решение. bar - это опечатка для var. простите :) - person Shon; 25.02.2015

arrow_upward
7
arrow_downward

Если мы можем предположить, что два списка содержат уникальные переменные, тогда работает следующее использование двойного отрицания:

varset_seteq(As, Bs) :-
    \+ \+ (numbered_from(As, 1),
           sort(Bs, SBs),
           As == SBs).

numbered_from([], _).
numbered_from([X|Xs], X) :-
    X1 is X + 1,
    numbered_from(Xs, X1).

Это похоже на решение Пауло, но позволяет избежать проблемы, заключающейся в том, что порядок переменных требуется только в соответствии с требованиями ISO / IEC 13211-1 для обеспечения согласованности в рамках одного выполнения sort/2.

person Michael Ben Yosef    schedule 27.02.2015

arrow_upward
4
arrow_downward

Другое решение, менее эффективное, чем умное решение Tudor, и поэтому не рекомендуется, но все же заслуживающее упоминания здесь, поскольку я вижу, что оно используется неоднократно:

varset_seteq(As, Bs) :-
    sort(As, Sa), sort(Bs, Sb), Sa == Sb.
person Paulo Moura    schedule 25.02.2015
comment
Мой первоначальный ответ был именно об этом :), хотя я также добавил предикат varlist/1, чтобы проверить, состоят ли оба списка из переменных. Но потом я понял, и Тудор Берариу указал, что такой подход будет успешным, например, на As = [A,A,B,C], Bs = [B,C,B,C,A]. Я, наверное, тоже должен был оставить свою первоначальную попытку .. - person Shon; 25.02.2015
comment
Хотя это решение будет работать в конкретных реализациях Prolog, оно зависит от свойств реализации Prolog, зависящих от реализации. В цели Sa == Sb больше не гарантируется, что Sa и Sb по-прежнему отсортированы. Подумайте о том, что сборщик мусора происходит в реализации, которая не сохраняет порядок переменных - который может все еще соответствовать, если он не вызывает сборщик мусора во время sort/2. - person false; 25.02.2015
comment
@aBathologist В самом деле :-) Детализация подводных камней очевидных альтернативных решений всегда стоит того. Тем не менее, исходный вопрос действительно утверждает, что входные данные - это два списка уникальных переменных (выделено мной). - person Paulo Moura; 25.02.2015
comment
@PauloMoura О да. Ты прав! Мое чтение постоянно колебалось между тем, означает ли Falsel, что сам предикат должен завершиться ошибкой, если списки не являются наборами переменных, или если он может ожидать, что его аргументы будут наборами переменных. Теперь, с вашим акцентом, кажется очевидным, что он может ожидать наборы переменных (точно так же, как ord_seteq/1 ожидает, но не проверяет упорядоченные наборы). - person Shon; 25.02.2015

arrow_upward
3
arrow_downward

Другой подход. Если мы обеспечим себя этими предикатами более высокого порядка (каждый из которых полезен сам по себе),

select_with(_, _, [], []).
select_with(P, X, [Y|Ys], Ys)     :- call(P, X, Y), !.
select_with(P, X, [Y|Ys], [Y|Ks]) :-
    select_with(P, X, Ys, Ks).

foldl(_,[],Vn,Vn).
foldl(P,[X|Xs],V0,Vn) :- 
    call(P,X,V0,V1),
    foldl_(P,Xs,V1,Vn).

тогда мы можем легко определить предикат, который будет истинным, если каждый член одного списка имеет одинаковый элемент в другом (используя ==/2):

members_equal(A, B :-
    foldl(select_with(==), A, B, []).

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

is_varset([]).
is_varset([V|Vs]) :-
    var(V),
    maplist(\==(V), Vs),
    is_varset(Vs).

(По крайней мере, в SWI Prolog использование sort/2 требует меньшего количества выводов, чем приведенное выше. Предположительно, это связано с тем, что сортировка выполняется на C. Кроме того, этот ответ все еще не приближается к элегантности подхода term_vars/2 - такова сила " смысловое восхождение »:)

person Shon    schedule 25.02.2015