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

Question

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

filter(A, B) 

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

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

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

У меня есть готовая функция "фильтра", но теперь мне нужно применить ее к списку, как показано во втором примере, за исключением всех элементов, для которых фильтр возвращает 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-Пролог имеет =.. оператор, который решает все его проблемы и делает возможной произвольную логику n-порядка.

Answer 2

SWI-Пролог предлагает 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

Существует неотъемлемая проблема с функциями фильтра, которые рассматривают успех или неудачу предиката в качестве критерия для фильтрации: получающаяся программа больше не является чисто монотонной программой. Поэтому он теряет все свои декларативные свойства - единственное значение, которое остается, - это процедурная пошаговая интерпретация. Вот чистая, усовершенствованная версия фильтрации с использованием 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, Country = Pais, People = Personas, Person = 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.
   ).