Как найти последний элемент в третьем списке, который собран из первого и второго списка?

Question

intersection([],L1,L2,L3).
intersection([H|T],L2,L3,[H|L4]):-member(H,L2),intersection(T,L3,L3,L4).
member(H,[H|T]).
member(X,[H|T]):-member(X,T).

Этот код создает третий список из первого и второго списка.

last([U],U).
last([_|L3],U) :- last(L3,U).

Этот фрагмент кода ищет последний элемент в списке.
Моя проблема в том, что я могу не могу понять, как сделать эти два куска кода в одном. То есть программа должна найти дубликаты элементов в первом и втором списке и отобразить их в третьем, а в третьем списке отобразить последний элемент, умноженный на 3.

Answer 1

Основная проблема intersection/4. Я предполагаю, что вы хотели написать детерминированный c предикат intersection/3, первые два аргумента которого полностью создаются во время вызова, а последний аргумент является выходным аргументом. Под определением c я подразумеваю, что intersection/3 должен быть успешным ровно один раз без оставшихся точек выбора. Документация SWI-Prolog содержит полезный обзор объявлений детерминизма и режима (хотя он не обеспечивает их соблюдение).

Полезно начать с написания декларативной спецификации предиката, следующей за индуктивное определение списков:

1. Пересечение [] и Ys равно [].
2. Пересечение [A|Xs] и Ys равно A с добавлением до пересечения Xs и Ys, если A является членом Ys.
3. Пересечение [A|Xs] и Ys является пересечением Xs и Ys если A не является членом Ys.

Самый простой перевод этой спецификации в стандартный пролог:

intersection([],_,[]).
intersection([A|Xs],Ys,[A|Zs]) :-
    member(A,Ys),
    intersection(Xs,Ys,Zs).
intersection([A|Xs],Ys,Zs) :-
    \+ member(A,Ys),
    intersection(Xs,Zs).

Если первый вызов member/2 Успешно второй должен потерпеть неудачу. Чтобы избежать возврата, объединяя текущую цель с заголовком второго предложения и выполняя избыточный вызов на member/2, мы помещаем сокращение после вхождения member/2 во втором предложении.

intersection([],_,[]).
intersection([A|Xs],Ys,[A|Zs]) :-
    member(A,Ys),
    !,
    intersection(Xs,Ys,Zs).
intersection([_|Xs],Ys,Zs) :-
    intersection(Xs,Ys).

Если текущая цель объединяется с заголовками первого предложения, она не объединяется с заголовками последующих предложений. Чтобы предотвратить ложный возврат, мы помещаем вырез в (пустое) тело первого предложения. Необходимость этого сокращения зависит от вашего выбора реализации Prolog.

intersection([],_,[]) :-
    !.
intersection([A|Xs],Ys,[A|Zs]) :-
    member(A,Ys),
    !,
    intersection(Xs,Ys,Zs).
intersection([_|Xs],Ys,Zs) :-
    intersection(Xs,Ys).

Нас интересует только проверка членства во втором списке. Таким образом, мы можем заменить вхождение member/2 полудетерминистским предикатом c memberchk/2. Здесь semideterministi c означает, что memberchk/2 успешно или неудачно завершается один раз без оставшихся точек выбора.

intersection([],_,[]).
    !.
intersection([A|Xs],Ys,[A|Zs]) :-
    memberchk(A,Ys),
    !,
    intersection(Xs,Ys,Zs).
intersection([_|Xs],Ys,Zs) :-
    intersection(Xs,Ys).

Эта реализация intersection/3 почти идентична реализации, найденной в библиотеке SWI-Prolog lists.pl. Вы можете объединить этот предикат с реализацией last/2 для завершения вашей программы. Например:

last_duplicate_tripled(Xs,Ys,N) :-
    intersection(Xs,Ys,Zs),
    last(Zs,M),
    N is M * 3.

Здесь я рекомендую сделать следующее:

1. Реализация intersection/3 с использованием металогических предикатов подобно findall/3 .
2. Читать @ ответ на ложь на этот вопрос .
3. Читать @ повторить ответ на этот вопрос .

Они делают что-то гораздо более интересное и сложное, чем я пытался в этом ответе.