Простые задачи добавления в Прологе

Question

Я изучал Prolog несколько недель назад, и что-то тривиальное, на чем я застреваю, - это поиск решений с использованием append.

Например, если у меня есть правило сопоставления с образцом, которое выглядит примерно так:

pattern( foo(X,Y), L1, L ) :-
    % some code to go through a list (where the foo-pattern is)
    % and add the pattern to the list L if it matches`

Я знаю, что добавление / 3 - это путь сюда, но ... L начинает неизвестно, то есть не заземляется, и когда мы начинаем рекурсию, список начинает заполняться соответствующими шаблонами. Тем не менее, я всегда путаюсь с тем, что первоначально происходит, то есть когда L не заземлен.

Например, вот фрагмент кода, в котором мы хотим получить список всех совпавших шаблонов, когда первый параметр - это список возможных шаблонов:

pat([foo(X,Y)|L1], R, L) :-  
    append(foo(X,Y),R,L),
    pat(L1, R, [D|L]).
pat([_|L1], R, L2) :-
    pat(L1, R, L2).

Большое спасибо.

Answer 1

Мне не нужно выглядеть отцом в вашем примере кода, чем ... append (foo (... Стандартный предикат append / 3 работает с lists . Append (foo (Anything) ,.)... не будет совпадать ни с одним из его предложений. Таким образом, ваше первое примерное предложение должно всегда терпеть неудачу, а второе должно либо терпеть неудачу, либо снимать создание бесконечного списка несвязанных переменных, в конечном итоге разрушаясь при исчерпании памяти.чтобы сделать это здесь, мне не сразу понятно, но звучит так, будто вы не хотите столько сопоставлять с образцом, сколько находите элементы в списке, которые объединяются с заданным термином. Почему вы думаете, что добавление / 3 - это путьидти?

Answer 2

Возможно, вам не поможет решение, которое не использует append/3. Например, рассмотрим следующий предикат filter/3:

filter(_Pattern, [], []).
filter(Pattern, [E|Es], Matches) :-
    Pattern \= E, !,
    filter(Pattern, Es, Matches).
filter(Pattern, [E|Es], [E|Matches]) :-
    filter(Pattern, Es, Matches).

Первое предложение filter/3 является базовым случаем, где, если во втором списке аргументов нет ничего, что можно сопоставить, мы получаем пустой список. Поскольку мы не учитывали Pattern, он игнорируется (отсюда и предыдущий _ против переменной).

Во втором предложении filter/3 проверяется, может ли Pattern, который может быть связан с термином (например, foo(X,Y)), объединять с первым элементом списка для сопоставления E. Оператор \= будет успешным, когда его аргументы не могут быть объединены , поэтому, если это удастся, когда мы не сопоставим E с шаблоном, он может выбросить его и продолжить (обратите внимание на сокращение ! после теста для фиксации в этой ветке).

Последнее (третье) предложение filter/3 зависит от второго предложения, поскольку оно просто передает E в список последних аргументов Matches, предполагая, что равно совпадению с Pattern, поскольку в предыдущем пункте не удалось определить, что не совпадение. Обратите внимание, что мы добавляем E к списку, привязывая структуру списка к выводу, оставляя подсписок Matches свободным; полный список Matches будет полностью связан только тогда, когда он достигнет базового случая, связывая его с пустым списком [], когда у нас закончатся термины для сопоставления во втором аргументе, создавая что-то вроде [E1,E2,...,En|[]], где каждый E1 до En соответствует шаблону; этот термин эквивалентен списку [E1,E2,...,En].

Проверка этого предиката следующим образом дает:

?- filter(foo(X,Y), [a,b,foo(x,y),c(f),foo(v(3),Z),5], L).
L = [foo(x, y), foo(v(3), Z)] ;
false.

Обратите внимание, что здесь все, что можно отнести к шаблону foo(X,Y), было отфильтровано в L при необходимости.

Последнее замечание: в вашем коде вызов append(foo(X,Y),R,L) всегда будет неудачным, поскольку append/3 работает только со списками; вы, вероятно, хотели бы вместо этого позвонить append([foo(X,Y)],R,L), но в этом случае вы просто используете вместо него L = [foo(X,Y)|R].

РЕДАКТИРОВАТЬ: Чтобы соответствовать вашему конкретному случаю, когда у вас есть список возможных шаблонов для сопоставления и фильтрации, вот еще один предикат, filter_list/3:

filter_list(_Patterns, [], []).
filter_list(Patterns, [E|Es], Matches) :-
    filter(E, Patterns, []), !,
    filter_list(Patterns, Es, Matches).
filter_list(Patterns, [E|Es], [E|Matches]) :-
    filter_list(Patterns, Es, Matches).

Обратите внимание, что filter_list/3 зависит от моего предыдущего определения filter/3 и реализовано с использованием точно такой же стратегии: если E не соответствует ни одному из Patterns (т. Е. Это тот случай, когда filter(E, Patterns, []) успешно), затем мы забываем E и продолжаем, иначе (последнее предложение) мы сохраняем его. Тестирование дает нам:

?- filter_list([foo(X,Y),bar(X),b], [a,b,foo(X,Y),c], L).
L = [b, foo(X, Y)] ;
false.