Найти наименьший список при условиях

В 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)

вызываются только один раз?

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
0
60
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Я думаю, вы могли бы сделать это с помощью предиката оболочки/помощника, который выполняет эти проверки один раз, а затем выполняет поиск некоторых фиксированных ответов:

% 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!

Это явно неполно. Есть находятся другие решения. Мы потеряли .

Итак, что мы можем с этим сделать? По сути, у нас есть два варианта:

  1. проверьте D1, D2 и T заранее и выбросьте instantiation_error, когда экземпляра недостаточно.
  2. используйте стандартные блоки, которые лучше подходят для кода, сохраняющего .

В этом ответе я хочу показать, как реализовать вариант номер два.

Код основан на 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 стал полным!

Ааа, я искал «reification», думая, что это может быть уместно здесь, но нашел только ссылки на clpfd, использующие его. Почему теряет ли мой код логическую чистоту, когда member(1, [A,B,C]) выполняет возврат через A=1, B=1, C=1?

TessellatingHeckler 02.04.2022 20:39

@TessellatingHeckler. member/2 сам по себе чистый. Но использование его в (->)/2 может сделать его нечистым, потому что (->)/2 исключает альтернативные решения, как и пролог-вырез.

repeat 02.04.2022 21:02

@TessellatingHeckler. Если вас интересуют минимальные изменения в вашем коде, позволяющие сохранить логическая чистота, я предлагаю опубликовать новый вопрос об этом. Буду рад ответить на него :)

repeat 02.04.2022 21:37

Другие вопросы по теме