Predykat przecięcia Prologu używając

Question

Próbuję zbudować prosty predykat, który jako dane wejściowe otrzyma dwie listy, a wyniki będą trzecią, składającą się z przecięcia pierwszych dwóch. Postanowiłem zrobić za pomocą instrukcji logicznej. Jestem prawie pewien, że moja logika jest poprawna, ale mój predykat nie działa. Jakieś pomysły ?:

element(X,[H|T]) :- 
     X=H 
    ; 
     element(X,T). 

intersection(L1,L2,R) :- 
    not((
     element(A,L1), 
     not(element(A,L2)) 
    )), 
    not((
     element(A,L1), 
     not(element(A,R)) 
    )). 

Proszę nie publikować alternatywnych metod Zastanawiam się, dlaczego ten zwraca FALSE za każdym razem.

Answer 1

Problem polega na tym, że not/1 neguje jedynie wynik twojego element/2. Nie powoduje to cofnięcia się w celu znalezienia innych instancji, dla których obudowa not/1 będzie prawdą.

Rozważmy następujący program.

a(1). 
a(2). 

b(1). 
b(2). 
b(3). 

i następujące pytania:

1. b(X), not(a(X)).
2. not(a(X)), b(X).

Pierwsza z nich daje X = 3, podczas gdy druga daje false. Dzieje się tak dlatego, że pierwsza kwerenda najpierw tworzy instancję X z 1, następnie z 2, a następnie z 3, aż w końcu powiedzie się not(a(X)).
Druga kwerenda najpierw tworzy instancję X z wynikiem 1, a(1), więc niepowodzenie not(a(1)). Nie ma cofania się!

Answer 2

Twoja definicja to prawidłowa zbyt ogólna. Przyznaje np. to [] jest przecięciem każdej z dwóch list, która jest zbyt ogólna. To znaczy. niepoprawnie się to uda dla intersection([],[a],[a]). Brakuje trzeciego "idiomu" stwierdzającego, że wszystkie elementy znajdujące się na obu listach znajdą się na liście wynikowej.

Ale poza tym twoja definicja jest w porządku. Dla przypadku ziemi. Nieco niezwykłe jest to, że przecięcie jest pierwszym, a nie ostatnim argumentem. Całkiem irytujące są dla mnie nazwy zmiennych. Uważam, że R oznacza "wynik", a więc przecięcie. I L1 i L2 to dwa zestawy do budowy skrzyżowania. .

Jest to nieco zbyt ogólne, choć - podobnie jak wiele predykatów Prologu (pomyśl append([], non_list, non_list) Oprócz list, twoja definicja przyznaje również warunki, które nie są ani listy, ani częściowe listy:

?- intersection(non_list1,[1,2|non_list2],[3,4|non_list3]). 

aby to bardzo przydatne bezpieczne, użyć go tak:

?- when(ground(intersection(I, A, B)), intersection(I, A, B)). 

lub tak:

?- ( ground(intersection(I, A, B)) 
    -> intersection(I, A, B) 
    ; throw(error(instantiation_error, intersection(I, A, B))) 
    ). 

---

Jako drobna uwaga, napisz raczej (\+)/1 zamiast not/1.

Answer 3

Brak cofnięcia z powodu negacji wskazany przez @SQB nie jest w rzeczywistości jedynym problemem z kodem. Jeśli grasz trochę za pomocą zapytań o ziemię, okazuje się, że nie-listy i pusta lista wskazana przez @false również nie są jedynym problemem. Rozważ następujące zapytania:

?- intersection([2,3],[1,2,3],[2,3,4]). 
yes 
    ?- intersection([2],[1,2,3],[2,3,4]). 
yes 
    ?- intersection([3],[1,2,3],[2,3,4]). 
yes 
    ?- intersection([],[1,2,3],[2,3,4]). 
yes 

Pierwszy to, co zwykle jest rozumiane jako przecięcie. Pozostałe trzy to wszystkie podlisty skrzyżowania, w tym banalna podlista []. Dzieje się tak ze względu na sposób, w jaki predykat opisuje to, czym jest skrzyżowanie: na przecięciu nie ma miejsca, że ​​element znajduje się na pierwszej, ale nie na drugiej liście, a ten element znajduje się na pierwszej, ale nie na trzeciej liście. Opis ten wyraźnie pasuje do powyższych trzech zapytań, więc im się to udaje. Wygłupiać trochę więcej z tego opisu w umyśle istnieje kilka innych godnych uwagi zapytań wątpliwości, że uda:

?- intersection([2,2,3],[1,2,3],[2,3,4]). 
yes 

pytanie, czy obecność duplikatów w roztworze jest dopuszczalne, czy nie jest w rzeczywistości całkiem przedmiotem dyskusji. Listy [2,2,3] i [2,3], chociaż różne, reprezentują ten sam zbiór {2,3}. Istnieje this recent answer na pytanie dotyczące unii Prolog, która zawiera omówienie takich aspektów odpowiedzi. I oczywiście na listach podrzędnych skrzyżowania wymienione powyżej mogą również zawierać duplikatów lub wielokrotności:

?- intersection([2,2,2],[1,2,3],[2,3,4]). 
yes 

Ale dlaczego tak jest? Dla pustej listy jest to dość łatwe do zauważenia. Zapytanie

?- element(A,[]). 
no 

nie stąd spójnik element(A,L1), not(element(A,L2)) zawiedzie również dla L1=[]. Dlatego negacja wokół niego się udaje. To samo odnosi się do drugiej negacji, w związku z czym [] można wyprowadzić jako przecięcie. Aby zrozumieć, dlaczego [2] i [3] sukces jako skrzyżowanie warto napisać predykat jako wzoru logiki uniwersalne kwantyfikatory spisane wyraźnie:

∀ L1 ∀ L2 ∀ R ∀ A(intersection(L1,L2,R) ← ¬ (element(A,L1) ∧ ¬ element(A,L2)) ∧ ¬ (element(A,L1) ∧ ¬ element(A,R)))

Jeśli zajrzysz do podręcznika logiki lub programowania logicznego, który również pokazuje kod Prologu jako formuły logiczne, przekonasz się, że uniwersalne kwantyfikatory zmiennych, które nie występują w nagłówku reguły, mogą zostać przeniesione do ciała jako egzystencjalne kwantyfikatory.W tym przypadku dla A:

∀ L1 ∀ L2 ∀ R(intersection(L1,L2,R) ← ∃ A ( ¬ (element(A,L1) ∧ ¬ element(A,L2)) ∧ ¬ (element(A,L1) ∧ ¬ element(A,R))))

Więc dla wszystkich argumentów L1,L2,R istnieje częśćA, która spełnia cele. Co wyjaśnia wyprowadzanie podlisty przecięcia i wielokrotność występowania elementów.

jest jednak znacznie bardziej irytujące, że zapytanie

?- intersection(L1,[1,2,3],[2,3,4]). 

pętle zamiast rozwiązań produkcyjnych. Jeśli wziąć pod uwagę, że L1 nie jest tworzony i spojrzeć na wyniki w następnym zapytaniu

?- element(A,L1). 
L1 = [A|_A] ? ; 
L1 = [_A,A|_B] ? ; 
L1 = [_A,_B,A|_C] ? ; 
... 

staje się jasne, że zapytanie

?- element(A,L1),not(element(A,[1,2,3])). 

musi pętla ze względu na nieskończenie wiele list L1, które zawierają A, opisany pierwszym celem. Dlatego też odpowiednia koniunkcja w twoim predykacie również musi się zapętlić. Poza uzyskaniem wyników byłoby również miłe, gdyby takie orzeczenie odzwierciedlało relacyjną naturę Prologu i działało odwrotnie (zmienna druga lub trzecia argumentacja). Porównajmy twój kod z takim rozwiązaniem. (Dla porównania następujące orzeczenie opisuje listy zagnieżdżone na skrzyżowaniu tak kodzie nie, dla innej definicji patrz poniżej).

aby odzwierciedlić jego deklaratywny charakter pozwala nazwać list_list_intersection/3:

list_list_intersection(_,_,[]). 
list_list_intersection(L1,L2,[A|As]) :- 
    list_element_removed(L1,A,L1noA), 
    list_element_removed(L2,A,L2noA), 
    list_list_intersection(L1noA,L2noA,As). 

list_element_removed([X|Xs],X,Xs). 
list_element_removed([X|Xs],Y,[X|Ys]) :- 
    dif(X,Y), 
    list_element_removed(Xs,Y,Ys). 

Podobnie jak twój predykat, ta wersja używa również elementów przecięcia do opisania relacji. Stąd produkujących te same listy zagnieżdżone (w tym []):

?- list_list_intersection([1,2,3],[2,3,4],I). 
I = [] ? ; 
I = [2] ? ; 
I = [2,3] ? ; 
I = [3] ? ; 
I = [3,2] ? ; 
no 

ale bez pętli. Jednak wiele wystąpień nie jest już tworzonych, ponieważ już dopasowane elementy są usuwane przez argument list_element_przełączony/3. Ale wiele wystąpień w obu pierwszych listach są dopasowane prawidłowo:

?- list_list_intersection([1,2,2,3],[2,2,3,4],[2,2,3]). 
yes 

To orzeczenie działa również w innych kierunkach:

?- list_list_intersection([1,2,3],L,[2,3]). 
L = [2,3|_A] ? ; 
L = [2,_A,3|_B], 
dif(_A,3) ? ; 
L = [2,_A,_B,3|_C], 
dif(_A,3), 
dif(_B,3) ? ; 
... 

    ?- list_list_intersection(L,[2,3,4],[2,3]). 
L = [2,3|_A] ? ; 
L = [2,_A,3|_B], 
dif(_A,3) ? ; 
L = [2,_A,_B,3|_C], 
dif(_A,3), 
dif(_B,3) ? ; 
... 

więc ta wersja odpowiada kodzie bez duplikatów. Zwróć uwagę, że element A skrzyżowania jawnie pojawia się w nagłówku reguły, w której wszystkie elementy przecięcia są przechodzące rekursywnie. Uważam, że to jest to, co próbowaliście osiągnąć, wykorzystując implicite uniwersalne kwantyfikatory przed regułami Prologu.

Aby powrócić do punktu na początku mojej odpowiedzi, nie jest to powszechnie rozumiane jako skrzyżowanie.Spośród wszystkich wyników list_list_intersection/3 opisuje dla skrzyżowań tylko argumenty o [1,2,3] i [2,3,4]. Tutaj pojawia się kolejny problem z kodem: jeśli używasz elementów przecięcia do opisania relacji, w jaki sposób upewniasz się, że pokrywasz wszystkie przecinające się elementy? W końcu wszystkie elementy [2] występują w [1,2,3] i [2,3,4]. Oczywistym pomysłem byłoby przejrzenie elementów jednej z pozostałych list i opisanie tych, które występują w obu miejscach, a także na skrzyżowaniu. Oto wariant użyciu if_/3 i memberd_t/3:

list_list_intersection([],_L2,[]). 
list_list_intersection([X|Xs],L2,I) :- 
    if_(memberd_t(X,L2), 
     (I=[X|Is],list_element_removed(L2,X,L2noX)), 
     (I=Is,L2noX=L2)), 
    list_list_intersection(Xs,L2noX,Is). 

Należy pamiętać, że jest to również możliwe, aby przejść przez argumentów drugiej listy zamiast pierwszego. Predykat memberd_t/3 jest reifikowanym wariantem twojego predykatu element/2, a list_element_removed/3 jest ponownie używany w opisie, aby uniknąć duplikatów w rozwiązaniu. Teraz rozwiązanie jest unikalne

?- list_list_intersection([1,2,3],[2,3,4],L). 
L = [2,3] ? ; 
no 

i „pytania problemowe” z góry nie jak oczekiwano:

?- list_list_intersection([1,2,3],[2,3,4],[]). 
no 
    ?- list_list_intersection([1,2,3],[2,3,4],[2]). 
no 
    ?- list_list_intersection([1,2,3],[2,3,4],[3]). 
no 
    ?- list_list_intersection([1,2,3],[2,3,4],[2,2,3]). 
no 
    ?- list_list_intersection([1,2,3],[2,3,4],[2,2,2]). 
no 

I oczywiście można również użyć predykatu w innych kierunkach:

?- list_list_intersection([1,2,3],L,[2,3]). 
L = [2,3] ? ; 
L = [3,2] ? ; 
L = [2,3,_A], 
dif(_A,1) ? ; 
... 

    ?- list_list_intersection(L,[2,3,4],[2,3]). 
L = [2,3] ? ; 
L = [2,3,_A], 
dif(4,_A) ? ; 
...