Пролог союз для АУБУК

Я недавно начал изучать Пролог и не могу решить, как объединить три списка.

Мне удалось составить объединение из 2 списков:

%element
element(X,[X|_]).
element(X,[_|Y]):-
               element(X,Y).

%union

union([],M,M).
union([X|Y],L,S) :- element(X,L),union(Y,L,S).
union([X|Y],L,[X|S]) :- (not(element(X,L))),union(Y,L,S).

Кто-нибудь может мне помочь, пожалуйста?

Источник

3 ответа 

union(A, B, C, U) :-
   union(A, B, V),
   union(C, V, U).

Ваше определение union/3 можно улучшить, заменив

... not(element(X,L)), ...

от

... maplist(dif(X),L), ...

или же

... non_member(X, L), ....

non_member(_X, []).
non_member(X, [E|Es]) :-
   dif(X, E),
   non_member(X, Es).

Вот случай, когда разница показывает:

?- union([A],[B],[C,D]).
A = C,
B = D,
dif(C, D).

Как должен [A] а также [B] выглядеть так, что их объединение содержит 2 элемента?

Ответ: они должны быть разными.

Исходная версия не выполняется для этого запроса, но она успешно выполняется для специализированного экземпляра, такого как:

?- A = 1, B = 2, union([A],[B],[C,D]).

Так что это удается для этого, но не для его обобщения. Поэтому это не чисто логическое отношение.

Так что все хорошо и прекрасно с dif/2? К сожалению нет. У @TudorBerariu есть веские основания для сокращения, поскольку оно отражает некоторые намерения, которые у нас есть относительно отношений. Сокращение эффективно отражает два ключевых намерения

  • что альтернатива не быть членом теперь исключена, что справедливо для определенных режимов, например, Arg1 и Arg2 являются достаточно инстанцированными терминами. Безопасным приближением были бы основные термины.

  • что нет необходимости искать другие элементы в списке Arg2, что опять-таки верно только в том случае, если Arg1 и Arg2 созданы в достаточной степени.

Проблемы проявляются только тогда, когда термины недостаточно проработаны.

Недостаток определения OP и приведенного выше, состоит в том, что оба излишне носят слишком общий характер, что можно наблюдать с повторяющимися элементами в Arg2:

?- union([a,a],[a,a],Zs).
Zs = [a, a] ;
Zs = [a, a] ;
Zs = [a, a] ;
Zs = [a, a] ;
false.

На самом деле, мы получаем | Arg2 | | Arg1 | -1 лишние ответы. Таким образом, у среза была хорошая причина быть там.

Еще одна причина, почему union/3 поскольку это стоит не очень эффективно, то, что для (намеченного) случая основания это оставляет открытыми ненужные точки выбора. Опять же, решение @ TudorBerariu не имеет этой проблемы:

?- union([a],[a],Zs).
Zs = [a] ;    %    <--- Prolog does not know that there is nothing left.
false.

Устранение избыточности

Фактическим виновником такого количества избыточных ответов является первое правило. element(a,[a,a]) (обычно называется member/2) удастся дважды.

union([X|Y],L,S) :- element(X,L), union(Y,L,S).
                    ^^^^^^^^^^^^

Вот улучшенное определение:

memberd(X, [X|_Ys]).
memberd(X, [Y|Ys]) :-
   dif(X,Y),          % new!
   memberd(X, Ys).

Рекурсивное правило, читая его справа налево, гласит следующее:

Предполагать memberd(X, Ys) верно уже для некоторых X а также Ys, Учитывая это, и учитывая, что у нас есть примерка Y который отличается от X, затем

мы можем заключить, что также memberd(X, [Y|Ys]) правда.

Так что это устранило избыточные решения. Но наше определение все еще не очень эффективно: ему все равно приходится посещать Arg2 дважды для каждого элемента, а затем он не может сделать вывод, что альтернативы не осталось. В любом случае: воздержитесь от размещения надреза, чтобы удалить это.

Введение детерминизма через реификацию.

Сравните определения memberd/2 а также non_member/2, Хотя они описывают "противоположность" друг друга, они выглядят очень похоже:

non_member(_X, []).
non_member(X, [Y|Ys]) :-
   dif(X,Y),
   non_member(X, Ys).

memberd(X, [X|_Ys]).
memberd(X, [Y|Ys]) :-
   dif(X,Y),         
   memberd(X, Ys).

Рекурсивное правило то же самое! Только факт другой. Давайте объединим их в одно определение - с дополнительным аргументом о том, имеем ли мы в виду memberd (true) или же non_member (false):

memberd_t(_X, [], false).
memberd_t(X, [X|_Ys], true).
memberd_t(X, [Y|Ys], Truth) :-
   dif(X, Y),
   memberd_t(X, Ys, Truth).

Теперь наше определение становится немного более компактным:

unionp([], Ys, Ys).
unionp([X|Xs], Ys, Zs0) :-
  if_( memberd_t(X, Ys), Zs0 = Zs, Zs0 = [X|Zs] ),
  unionp(Xs, Ys, Zs).

memberd_t(_X, [], false).          % see below
memberd_t(X, [Y|Ys], Truth) :-
   if_( X = Y, Truth=true, memberd_t(X, Ys, Truth) ).

Обратите внимание на разницу между if_(If_1, Then_0, Else_0) и управляющая конструкция if-then-else ( If_0 -> Then_0 ; Else_0 ), В то время как If_1 может иметь успех несколько раз с различными значениями истинности (то есть, это может быть и истиной и ложью), конструкция управления делает If_0 только один раз, чтобы быть правдой.

if_(If_1, Then_0, Else_0) :-
   call(If_1, T),
   (  T == true -> call(Then_0)
   ;  T == false -> call(Else_0)
   ;  nonvar(T) -> throw(error(type_error(boolean,T),_))
   ;  /* var(T) */ throw(error(instantiation_error,_))
   ).

=(X, Y, T) :-
   (  X == Y -> T = true
   ;  X \= Y -> T = false
   ;  T = true, X = Y
   ;  T = false,
      dif(X, Y)                             % ISO extension
      % throw(error(instantiation_error,_)) % ISO strict
   ).

equal_t(X, Y, T) :-
   =(X, Y, T).

Чтобы убедиться, что memberd_t/3 всегда будет извлекать выгоду из индексации первого аргумента, лучше использовать следующее определение (благодаря @WillNess):

memberd_t(E, Xs, T) :-
   i_memberd_t(Xs, E, T).

i_memberd_t([], _E, false).
i_memberd_t([X|Xs], E, T) :-
   if_( X = E, T = true, i_memberd_t(Xs, E, T) ).
Источник

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

union(L1, L2, L3, U):-union(L1, L2, U12), union(U12, L3, U).

Вы можете улучшить union/3 с оператором резки:

union([],M,M).
union([X|Y],L,S) :- element(X,L), !, union(Y,L,S).
union([X|Y],L,[X|S]) :- union(Y,L,S).
Источник

Использование только предикатов с дополнительным аргументом, таким как memberd_t/3, приводит только к слабой реализации. Для сильного овеществления нам также необходимо создать ограничения. Сильная реификация - это еще один подход к устранению недетерминизма.

Но сильное овеществление трудно, возможный способ архивации это использовать CLP(*) экземпляр, который также утвердил логические операторы. Вот пример использования CLP(FD) для проблемы союза. К сожалению это касается только домена Z:

Сильный код Reification:

member(_, [], 0).
member(X, [Y|Z], B) :-
   (X #= Y) #\/ C #<==> B,
   member(X, Z, C).

union([], X, X).
union([X|Y], Z, T) :-
   freeze(B, (B==1 -> T=R; T=[X|R])),
   member(X, Z, B),
   union(Y, Z, R).

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

Запуск наземного примера:

?- union([1,2],[2,3],X).
X = [1, 2, 3].

Также приведенный выше пример даже не создает точек выбора, если мы где-то используем переменные. Но мы можем увидеть много ограничений:

Запуск не наземного примера:

?- union([1,X],[X,3],Y).
X#=3#<==>_G316,
1#=X#<==>_G322,
_G316 in 0..1,
freeze(_G322,  (_G322==1->Y=[X, 3];Y=[1, X, 3])),
_G322 in 0..1.

?- union([1,X],[X,3],Y), X=2.
X = 2,
Y = [1, 2, 3].

Поскольку мы не сформулировали некоторые входные инварианты, интерпретатор не может увидеть, что создание ограничений в приведенном выше случае не имеет никакого смысла. Мы можем использовать all_different/1 ограничение, чтобы помочь переводчику немного:

Предоставление инвариантов:

?- all_different([1,X]), all_different([X,3]), union([1,X],[X,3],Y).
Y = [1, X, 3],
X in inf..0\/2\/4..sup,
all_different([X, 3]),
all_different([1, X]).

Но мы не должны ожидать слишком многого от этого единственного примера. Так как CLP(FD) и freeze/2 является лишь неполной процедурой принятия решений для предложений и Z-уравнений, этот подход может работать не так гладко, как здесь, в любой ситуации.

до свидания

Источник
Другие вопросы по тегам