Пролог: фильтрация списка?

Question

В настоящее время я работаю над очень коротким проектом на Прологе, и я застрял, пытаясь применить созданный мной «фильтр» к списку. У меня есть то, что вы могли бы назвать фильтром готовым, но я не могу его применить. Было бы лучше, если бы я проиллюстрировал:

filter(A, B) 

... выводит true, если выполняются определенные условия.

filterList(A, [X, Y, Z])

... выводит список, который включает все элементы из второго аргумента, которые делают вывод фильтра false . (Таким образом, если фильтр (A, X) равен true, вывод будет [Y, Z]).

У меня есть готовая функция «filter», но теперь мне нужно применить ее к списку, как показано во втором примере, за исключением всех элементов, для которых фильтр возвращает true при применении с первым аргументом.

Итак, если фильтр является простым A == B, функция должна получить A [A, B, A, C, D, A] и вывести [B, C, D], удалив все элементы, для которых применяется фильтр, очевидно.

У меня проблемы с базовой структурой функции, поэтому, если кто-нибудь сможет предоставить базовую схему для такой функции, это будет очень полезно. Я максимально упростил свою ситуацию, чтобы я мог взять все, что вы сможете предоставить, и изменить его для своих нужд.

Заранее спасибо!

Answer 1

Если вы ищете функции более высокого порядка в Прологе, вам обязательно следует обратиться к Naish (1995) , очень хорошему ресурсу по этому вопросу.

Его определение filter/3 следующее (он использует нотацию списка различий, поэтому избегает необходимости определять filter/4):

filter(_,[],[]).
filter(P, A0-As0, As) :-
    (
        call(P, A0) -> As = A0-As1
    ;
        As = As1
    )
    , filter(P, As0, As1).

Если у вас есть вопросы по этому предикату, пожалуйста, спросите меня в комментарии. Чтение бумаги также настоятельно рекомендуется, это также бросает вызов map, foldr и compose! Обратите внимание, что многие из упомянутых им ограничений (например, отсутствующий call/3 или более высокий порядок apply больше не применяются. SWI-Prolog имеет оператор =.., который решает все его проблемы и делает произвольным Возможна логика n-порядка.

Answer 2

SWI-Prolog предлагает exclude/3 и другие подобные мета-предикаты. Ваша исходная проблема может быть закодирована так:

are_identical(X, Y) :-
    X == Y.

filterList(A, In, Out) :-
    exclude(are_identical(A), In, Out).

Пример использования:

?- filterList(A, [A, B, A, C, D, A], Out).
Out = [B, C, D].

Answer 3

Существует неотъемлемая проблема с функциями фильтра, которые принимают успех или неудачу предиката в качестве критерия для фильтрации: Полученная программа больше не является чисто монотонной программой. Поэтому он теряет все свои декларативные свойства & mdash; единственное значение, которое остается, - это процедурная пошаговая интерпретация. Вот чистая, усовершенствованная версия фильтрации с использованием if_/3:

tfilter(_CT_2,    [], []).
tfilter(CT_2, [E|Es], Fs0) :-
   if_(call(CT_2,E), Fs0 = [E|Fs], Fs0 = Fs ),
   tfilter(CT_2, Es, Fs).

Таким образом, первый аргумент является замыканием / продолжением, которое получит еще два аргумента: элемент и полученное значение истинности.

=(X,X,true).
=(X,Y,false) :- dif(X,Y).

Теперь результаты остаются точными:

| ?- tfilter(=(X),[A,B],Xs).
B = A,
X = A,
Xs = [A,A] ? ;
X = A,
Xs = [A],
dif(A,B) ? ;
X = B,
Xs = [B],
dif(B,A) ? ;
Xs = [],
dif(X,A),
dif(X,B) ? ;
no

Существует четыре возможности фильтрации списка из двух элементов по критерию, равному X. Каждый элемент может быть одинаковым или различным.

Недостаток этого подхода заключается в том, что необходимо предоставить уточненные версии всех критериев.

Answer 4

filter(_,[],[]).
filter(Predicate,[First|Rest],[First|Tail]) :-
   filter(Predicate,Rest,Tail).
filter(Predicate,[_|Rest],Result) :-
   filter(Predicate,Rest,Result).

Answer 5

У меня взрослые в стране // Obtengo los Propertos de un pais, Страна = Pais, Люди = Personas, Персона = una sola Persona

habitants(USA, [juan, pedro, david])

adults(Adults, Country) :-
     findall(Person, (habitants(Country,People), member(People, Person), adult(Person)), Adults)

Это фильтр в прологе // Asi es un filter en prolog

Answer 6

Ну, что ты знал, я только что понял это. Итак, вот я и представляю ответ на свой вопрос, как и ожидалось, очень короткая функция сработала:

filterList(_,[],R,R).           % Returns answer when the list is exhausted.
filterList(L,[A|List],Temp,Res) :-
   filterList(L,List,New,Res),  % Recursive call, New is either the same list
   (  filter(L,A),              % in case the filter outputs true, or the list
      New = Temp
   ;  New = [A|Temp]            % plus the current element otherwise.
   ).