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

Question

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

filter(A, B) 

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

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

... выводит список, который включает все элементы из второго аргумента, которые заставляют фильтр выводить false . (Таким образом, если фильтр (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-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

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

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

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.
   ).

Answer 5

Я получаю взрослых из страны // Я получаю взрослых из страны, Страна = Страна, Люди = Люди, Человек = один Человек

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

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

Это фильтр в прологе // Это фильтр в прологе

Answer 6

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