В SWI-Prolog я хочу составить список L из двух списков L1 и L2 с наименьшим количеством элементов при условии, что 1 ∈ L1
и 1 ∈ L2
.
Если 1 ∉ L1
и 1 ∈ L2
, то L = L1
. Если 1 ∈ L1
и 1 ∉ L2
, то L = L2
. Если 1 ∉ L1
и 1 ∉ L2
, то предикат возвращает false.
Я мог бы оценить это на Прологе со следующими условиями:
minset_one(D1, D2, T) :- ((member(1, D1), not(member(1, D2))) -> T=D1).
minset_one(D1, D2, T) :- ((not(member(1, D1)), member(1, D2)) -> T=D2).
minset_one(D1, D2, T) :- (member(1, D1), member(1, D2), length(D1,L1), length(D2,L2), L1 >= L2) -> T=D2.
minset_one(D1, D2, T) :- (member(1, D1), member(1, D2), length(D1,L1), length(D2,L2), L2 > L1) -> T=D1.
Моя проблема с этой функцией заключается в том, что функция-член вызывается очень часто. Это способ уменьшить сложность этого предиката таким образом, что функции
member(1, D1)
member(1, D2)
length(D1, L1)
length(D2, L2)
вызываются только один раз?
Я думаю, вы могли бы сделать это с помощью предиката оболочки/помощника, который выполняет эти проверки один раз, а затем выполняет поиск некоторых фиксированных ответов:
% minset_one(1 in D1, 1 in D2, D1, D2, D1Len, D2Len, T).
minset_one_(true, false, D1, _, _, _, D1).
minset_one_(false, true, _, D2, _, _, D2).
minset_one_(true, true, _, D2, D1Len, D2Len, D2) :- D1Len >= D2Len.
minset_one_(true, true, D1, _, D1Len, D2Len, D1) :- D1Len < D2Len.
minset_one(D1, D2, T) :-
(member(1, D1) -> D1check = true ; D1check = false),
(member(1, D2) -> D2check = true ; D2check = false),
length(D1, D1Len),
length(D2, D2Len),
minset_one_(D1check, D2check, D1, D2, D1Len, D2Len, T).
И ваш код, и код в ответ @TessellatingHacker теряют логическая чистота, когда аргументы minset_one/3
недостаточно конкретизированы:
?- D1 = [X,Y,Z], D2 = [U,V], minset_one(D1,D2,T). D1 = [1,Y,Z], D2 = [1,V], T = D2 ; false. % no more solutions!
Это явно неполно. Есть находятся другие решения. Мы потеряли логическая чистота.
Итак, что мы можем с этим сделать? По сути, у нас есть два варианта:
D1
, D2
и T
заранее и выбросьте instantiation_error
, когда экземпляра недостаточно.В этом ответе я хочу показать, как реализовать вариант номер два.
Код основан на if_/3
, который является ядром library(reif)
.
Короче говоря, мы материализуем значения истинности отношений и используем для этих значений индексацию Пролога.
Использование SWI-Prolog 8.4.2:
?- use_module(library(reif)).
Во-первых, shorter_than_t(Xs,Ys,T)
преобразует "список Xs
короче, чем Ys
" в T
:
shorter_than_t([],Ys,T) :- aux_nil_shorter_than(Ys,T). shorter_than_t([_|Xs],Ys,T) :- aux_cons_shorter_than_t(Ys,Xs,T). aux_nil_shorter_than_t([],false). aux_nil_shorter_than_t([_|_],true). aux_cons_shorter_than_t([],_,false). aux_cons_shorter_than_t([_|Ys],Xs,T) :- shorter_than_t(Xs,Ys,T).
На основе shorter_than_t/3
определяем minset_one/3
:
minset_one(D1,D2,T) :- if_(shorter_than_t(D1,D2), if_(memberd_t(1,D1), D1=T, (memberd_t(1,D2,true),D2=T)), if_(memberd_t(1,D2), D2=T, (memberd_t(1,D1,true),D1=T))).
Теперь давайте снова запустим вышеуказанный запрос:
?- D1 = [X,Y,Z], D2 = [U,V], minset_one(D1,D2,T). D1 = [X,Y,Z], D2 = [1,V], T = D2 ; D1 = [X,Y,Z], D2 = [U,1], T = D2, dif (U,1) ; D1 = [1,Y,Z], D2 = [U,V], T = D1, dif (U,1), dif (V,1) ; D1 = [X,1,Z], D2 = [U,V], T = D1, dif (U,1), dif (V,1), dif (X,1) ; D1 = [X,Y,1], D2 = [U,V], T = D1, dif (U,1), dif (V,1), dif (X,1), dif (Y,1) ; false.
Наконец-то minset_one/3
стал полным!
@TessellatingHeckler. member/2
сам по себе чистый. Но использование его в (->)/2
может сделать его нечистым, потому что (->)/2
исключает альтернативные решения, как и пролог-вырез.
@TessellatingHeckler. Если вас интересуют минимальные изменения в вашем коде, позволяющие сохранить логическая чистота, я предлагаю опубликовать новый вопрос об этом. Буду рад ответить на него :)
Ааа, я искал «reification», думая, что это может быть уместно здесь, но нашел только ссылки на clpfd, использующие его. Почему теряет ли мой код логическую чистоту, когда
member(1, [A,B,C])
выполняет возврат через A=1, B=1, C=1?