Prólogo: ¿Filtrar una lista?

Question

Actualmente estoy trabajando en un proyecto muy corto en Prolog, y me quedé atascado tratando de aplicar un " filtro " He creado a una lista. Tengo lo que podría llamar el filtro listo, pero no puedo aplicarlo. Sería mejor si ilustrara:

filter(A, B) 

... genera 'verdadero' si se cumplen ciertas condiciones.

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

... genera una lista que incluye todos los elementos del segundo argumento que hacen que la salida del filtro sea falsa . (Entonces, si el filtro (A, X) es verdadero, la salida es [Y, Z]).

Tengo el " filtro " función lista, pero ahora necesito aplicarlo a una lista como se muestra en el segundo ejemplo, excluyendo todos los elementos para los cuales el filtro devuelve verdadero cuando se aplica con el primer argumento.

Entonces, si el filtro es un simple A == B, se supone que la función recibe A [A, B, A, C, D, A] y la salida [B, C, D], habiendo eliminado todos los elementos para los que se aplica el filtro, obviamente.

Tengo problemas con la estructura básica de la función, por lo que si alguien pudiera proporcionar un esquema básico para una función como esta, sería de gran ayuda. He simplificado mi situación lo más posible para poder tomar lo que sea que puedas proporcionar y modificarlo para mis necesidades.

¡Gracias de antemano!

Answer 1

Si está buscando funciones de orden superior en Prolog, debería consultar Naish (1995) , un muy buen recurso sobre esto.

Su definición de filter / 3 es la siguiente (usa la notación de lista de diferencias, por lo tanto se escapa al tener que definir filter / 4 ) :

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

Si tiene preguntas sobre este predicado, pregúnteme en el comentario. También es muy recomendable leer el documento, ¡también desafía map , foldr y compose ! Tenga en cuenta que muchas de las limitaciones que menciona (como, por ejemplo, una call / 3 o un apply de orden superior ya no se aplican. SWI-Prolog tiene el = .. operador, que aborda todas sus preocupaciones y hace posible una lógica arbitraria de orden n.

Answer 2

SWI-Prolog ofrece exclude / 3 y otros meta-predicados similares. Su problema original puede codificarse así:

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

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

Ejemplo de uso:

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

Answer 3

Existe un problema inherente con las funciones de filtro que toman el éxito o el fracaso de un predicado como criterio para el filtrado: el programa resultante ya no es un programa monótono puro. Por lo tanto, pierde todas sus propiedades declarativas: el único significado que queda es una interpretación de procedimiento paso a paso. Aquí hay una versión pura y reificada de filtrado usando 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).

El primer argumento es, por lo tanto, un cierre / continuación que recibirá dos argumentos adicionales: el elemento y el valor de verdad resultante.

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

Ahora, los resultados siguen siendo precisos:

| ?- 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

Hay cuatro posibilidades de cómo se puede filtrar una lista de dos elementos por el criterio de ser igual a X . Cada elemento puede ser igual o diferente.

La desventaja de este enfoque es que uno debe proporcionar versiones reificadas de todos los criterios.

Answer 4

Bueno, ¿qué sabes? Acabo de descubrirlo. Entonces, aquí estoy yo enviando una respuesta a mi propia pregunta, como se esperaba, una función realmente corta hizo el trabajo:

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

I get the adults of a country // Obtengo los adultos 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)

This is a filter in prolog // Asi es un filter en prolog

Answer 6

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