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

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

filter(A, B)

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

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

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

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

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

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

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


list filter prolog meta-predicate
person Sergio Morales    schedule 18.11.2008    source источник

Ответы (6)


arrow_upward
11
arrow_downward

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

His definition of filter/3 is the following (he uses difference-list notation, therefore escapes having to define 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-го порядка.

person Aleksandar Dimitrov    schedule 18.11.2008
comment
Питти Нейш предлагает применить / 3 в своих выводах, но я полагаю, что в настоящее время можно использовать call / n. apply / 3 - это просто вызов / 3. - person Mostowski Collapse; 09.12.2011
comment
См. Обсуждение того, почему оспаривается ссылка на Naish: Complang.tuwien. ac.at/ulrich/Prolog-inedit/naish.html - person Mostowski Collapse; 10.12.2011

arrow_upward
11
arrow_downward

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].
person Kaarel    schedule 03.12.2008
comment
включают (‹(5), [3,4,5,6,7], As). работает так же, как filter (‹(5), [3,4,5,6,7], As). exclude является обратным, поскольку дает те же результаты, что и filter (›= (5), [3,4,5,6,7], As). - person joeblog; 19.10.2016
comment
можно сделать без правила are_identical. замените тело filterList на ---- exclude (= (A), In, Out) - person DaveEdelstein; 26.02.2019

arrow_upward
4
arrow_downward

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

Обратной стороной этого подхода является то, что необходимо предоставить овеществленные версии всех критериев.

person false    schedule 26.02.2014

arrow_upward
0
arrow_downward

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

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.
   ).
person Sergio Morales    schedule 18.11.2008
comment
Эта версия всегда подходит для любого списка. Предназначена? - person false; 27.02.2014

arrow_upward
0
arrow_downward

Я получаю взрослых от страны // Obtengo los vultos 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

person Jesus Ledesma    schedule 28.09.2017

arrow_upward

arrow_downward

person    schedule
comment
Как насчет того, чтобы включить несколько примеров запросов, демонстрирующих предлагаемое вами решение в действии? - person repeat; 01.02.2019