Ответ 1
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 достаточно инстанцированы.
Проблемы отображаются только в том случае, если термины не созданы в достаточной мере.
Недостатком определения ОП и выше, является то, что оба они излишне слишком общие, что можно наблюдать с повторяющимися элементами в 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
может выполняться несколько раз с разными значениями истинности (то есть, он может быть как true, так и false), конструктор управления делает 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) ).