Как Prolog распечатывает 2 списка в виде одного списка без добавления кода? - PullRequest
Новая
       26

Как Prolog распечатывает 2 списка в виде одного списка без добавления кода?

2 голосов
/ 05 декабря 2011

У меня есть следующий код, который, по-видимому, является стандартным способом показать объединение между 2 списками: 

union([Head|Tail],List2,Result) :- 
    member(Head,List2),  union(Tail,List2,Result).
union([Head|Tail],List2,[Head|Result]) :- 
    \+ member(Head,List2), union(Tail,List2,Result).
union([],List2,List2).

и на следующем входе: 

union([a,b,c,d,2,3], [b,c,3,99], Result).

даст мнеследующий вывод: 

Result = [a,d,2,b,c,3,99] ? 

yes

Мой вопрос: как пролог делает это?List2 никогда не изменяется через рекурсивные вызовы, но в конце он печатает все элементы, которые образуют объединение между двумя исходными списками.

Пожалуйста, помогите мне понять этот код.

Спасибо.

Ответы [ 3 ]

1 голос
/ 05 декабря 2011

Алгоритм работы здесь следующий:

1) инициализировать результат в List2.Эта часть реализована благодаря: 

union([], List2, List2).

2) пройти List1 и выполнить следующее для каждого элемента:
2a) добавить его к Result, если элемент не находится в List2.Эта часть реализована благодаря этому пункту: 

union([Head|Tail], List2, [Head|Result]) :- 
    \+ member(Head, List2),
    union(Tail, List2, Result).

2b) ничего не делать, если элемент находится в List2.Эта часть реализована благодаря этому пункту: 

union([Head|Tail], List2, Result) :-
    member(Head, List2),
    union(Tail, List2, Result).

Для пошагового понимания выполнения пролога, пожалуйста, обратитесь к ответу @thanosQR.

Кстати, обратите внимание, что этот предикат нуждаетсяустанавливает возврат хорошего объединения, иначе дубликат в List1 останется дубликатом в Result (то же самое будет и в List2).

1 голос
/ 06 декабря 2011

Этот код на самом деле довольно неэффективен, поэтому мы не можем считать его «стандартным способом» для вычисления объединения.На первый взгляд, есть две простые оптимизации: избегайте повторения теста членства и используйте memberchk / 2 вместо member / 2.Таким образом, мы можем переписать его следующим образом: 

union([Head|Tail], List2, ResultT) :-
    (  memberchk(Head, List2)
    -> ResultT = Result
    ;  ResultT = [Head|Result] ),
    union(Tail, List2, Result).
union([],List2,List2).

Разница в производительности огромна.С относительно небольшими списками: 

...
numlist(1, 10000, A),
numlist(5000, 10000, B),
union(A, B, C),
...

мы переходим от 62,532,499 логических выводов к 20,002 логических выводов, и тест не заставляет оценивать все альтернативы (точки возврата)от участника): добавив это, нам нужно 25,015,004 больше выводов, хотя решения больше нет.Здесь код из библиотеки SWI-Prolog : 

%%  union(+Set1, +Set2, -Set3) is det.
%
%   True if Set3 unifies with the union of Set1 and Set2.
%   The complexity of this predicate is |Set1|*|Set2|
%
%   @see ord_union/3.

union([], L, L) :- !.
union([H|T], L, R) :-
    memberchk(H, L), !,
    union(T, L, R).
union([H|T], L, [H|R]) :-
    union(T, L, R).

Он похож на вашу версию, обратите внимание на cut (!)

1 голос
/ 05 декабря 2011

давайте предположим, что вы спрашиваете union ([1,2], [2], R).

в соответствии с первым правилом union ([1 | [2]], [2], R) будет истинным, если member (1, [2]) -> false, тогда пролог проверит, что второе объединение правил ([1 | [2]], [2], [1 | R]) будет истинным, если + member(1, [2]) -> true и union ([2], [2], R)

сейчас, union ([2 | []], [2], R) будет истинным(1-е правило), если member (2, [2]) -> true и union ([], [2], R)

union ([], [2], R) будет истинным (3-е правило), если R = [2]

, поэтому R = [2] и, следовательно, первый вызов union возвращает [1 | [2]] = [1,2]

полезнуюинструмент для выяснения того, «как это делает пролог», - это trace / 0: 

    2 ?- trace.
true.

[trace] 2 ?- union([1,2],[2],R).
   Call: (6) union([1, 2], [2], _G543) ? creep
   Call: (7) lists:member(1, [2]) ? creep
   Fail: (7) lists:member(1, [2]) ? creep
   Redo: (6) union([1, 2], [2], _G543) ? creep
   Call: (7) lists:member(1, [2]) ? creep
   Fail: (7) lists:member(1, [2]) ? creep
   Call: (7) union([2], [2], _G619) ? creep
   Call: (8) lists:member(2, [2]) ? creep
   Exit: (8) lists:member(2, [2]) ? creep
   Call: (8) union([], [2], _G619) ? creep
   Exit: (8) union([], [2], [2]) ? creep
   Exit: (7) union([2], [2], [2]) ? creep
   Exit: (6) union([1, 2], [2], [1, 2]) ? creep
R = [1, 2] .

в целом: List2 не изменяется, но предикат также не возвращает List2;возвращает список, созданный List2, и уникальные элементы List1

...