Prolog: Filtrer une liste?

Question

Je travaille actuellement sur un très court projet sur Prolog et je suis resté bloqué en essayant d'appliquer un "filtre". J'ai créé une liste. J'ai ce que vous pourriez appeler le filtre prêt, mais je ne peux pas l'appliquer. Ce serait mieux si j'illustrais:

filter(A, B) 

... indique 'true' si certaines conditions sont remplies.

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

... génère une liste qui inclut tous les éléments du deuxième argument qui rendent la sortie du filtre false . (Ainsi, si le filtre (A, X) est vrai, la sortie est [Y, Z]).

J'ai le " filtre " function ready, mais je dois maintenant l'appliquer à une liste comme indiqué dans le deuxième exemple, à l'exclusion de tous les éléments pour lesquels le filtre renvoie la valeur true lorsqu'il est appliqué avec le premier argument.

Donc, si le filtre est un simple A == B, la fonction est supposée recevoir A [A, B, A, C, D, A] et la sortie [B, C, D], après avoir supprimé tous les éléments pour lesquels le filtre s'applique, évidemment.

J'ai des problèmes avec la structure de base de la fonction. Par conséquent, si quelqu'un pouvait fournir un aperçu de base d'une fonction telle que celle-ci, il serait d'une grande aide. J'ai simplifié ma situation autant que possible afin de pouvoir prendre tout ce que vous pourriez être en mesure de fournir et de la modifier selon mes besoins.

Merci d'avance!

Answer 1

Si vous recherchez des fonctions d'ordre supérieur dans Prolog, vous devez absolument consulter Naish (1995) , une très bonne ressource à ce sujet.

Sa définition de filtre / 3 est la suivante (il utilise la notation de liste de différences, donc évite de devoir définir filtre / 4 ) :

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

Je vous avez des questions sur ce prédicat, s'il vous plaît me demander dans le commentaire. La lecture du document est également vivement recommandée. Elle contient également les définitions map , foldr et composer ! Notez que la plupart des limitations qu’il mentionne (comme, par exemple, un call / 3 manquant ou un apply supérieur ne s’appliquent plus. SWI-Prolog a le code < > = .. , qui répond à toutes ses préoccupations et permet une logique arbitraire à l'ordre n.

Answer 2

SWI-Prolog propose exclude / 3 et d'autres méta-prédicats de ce type. Votre problème initial peut être codé comme ceci:

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

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

Exemple d'utilisation:

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

Answer 3

Il existe un problème inhérent aux fonctions de filtrage qui considèrent le succès ou l'échec d'un prédicat comme critère de filtrage: le programme résultant n'est plus un programme purement monotone. Il perd donc toutes ses propriétés déclaratives - le seul sens qui reste est une interprétation procédurale étape par étape. Voici une version pure et réifiée du filtrage utilisant 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).

Le premier argument est donc une fermeture / continuation qui recevra deux arguments supplémentaires: L'élément et la valeur de vérité résultante.

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

Les résultats restent précis:

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

Il existe quatre possibilités pour filtrer une liste de deux éléments selon le critère de l’égalité X . Chaque élément peut être égal ou différent.

L’inconvénient de cette approche est qu’il faut fournir des versions réifiées de tous les critères.

Answer 4

Eh bien, comment saviez-vous que je venais de le comprendre? Alors, voici que je soumets une réponse à ma propre question, comme prévu, une fonction très courte a fait le travail:

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

Je reçois les adultes d'un pays // je reçois des adultes d'un pays, Pays = Pays, Personnes = Personnes, Personne = une personne

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

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

Ceci est un filtre dans prolog // Ceci est un filtre dans prolog

Answer 6

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