Prologo: filtrare un elenco?

Question

Attualmente sto lavorando a un progetto molto breve su Prolog, e mi sono appena bloccato nel tentativo di applicare un "filtro" Ho creato un elenco. Ho quello che potresti chiamare pronto per il filtro, ma non posso applicarlo. Sarebbe meglio se illustrassi:

filter(A, B) 

... restituisce 'true' se sono soddisfatte determinate condizioni.

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

... genera un elenco che include tutti gli elementi del secondo argomento che rendono l'output del filtro falso . (Quindi se il filtro (A, X) è vero, l'output è [Y, Z]).

Ho il " filtro " pronto per la funzione, ma ora devo applicarlo a un elenco come mostrato nel secondo esempio, escludendo tutti gli elementi per i quali il filtro restituisce true quando applicato con il primo argomento.

Quindi, se il filtro è un semplice A == B, la funzione dovrebbe ricevere A [A, B, A, C, D, A] e output [B, C, D], avendo rimosso tutti i elementi per i quali si applica il filtro, ovviamente.

Ho dei problemi con la struttura di base della funzione, quindi se qualcuno potesse fornire uno schema di base per una funzione come questa sarebbe di grande aiuto. Ho semplificato il più possibile la mia situazione in modo da poter prendere tutto ciò che potresti essere in grado di fornire e modificarlo per le mie esigenze.

Grazie in anticipo!

Answer 1

Se stai cercando funzioni di ordine superiore in Prolog, dovresti assolutamente consultare Naish (1995) , un'ottima risorsa al riguardo.

La sua definizione di filter / 3 è la seguente (usa la notazione dell'elenco delle differenze, quindi evita di dover definire filter / 4 ) :

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

Ho domande su questo predicato, per favore chiedetemi nel commento. Anche leggere il documento è altamente raccomandato, sfidando anche map , foldr e compose ! Nota che molte delle limitazioni che menziona (come, ad esempio, una call / 3 mancante o un apply di ordine superiore non si applicano più. SWI-Prolog ha il = .. , che affronta tutte le sue preoccupazioni e rende possibile la logica arbitraria di n-ordine.

Answer 2

SWI-Prolog offre exclude / 3 e altri meta-predicati. Il tuo problema originale può essere codificato in questo modo:

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

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

Esempio di utilizzo:

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

Answer 3

Esiste un problema intrinseco con le funzioni di filtro che considerano il successo o il fallimento di un predicato come criterio per il filtraggio: il programma risultante non è più un puro programma monotonico. Pertanto, perde tutte le sue proprietà dichiarative & # 8212; l'unico significato che rimane è un'interpretazione procedurale passo-passo. Ecco una versione pura e reificata del filtro utilizzando 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).

Il primo argomento è quindi una chiusura / continuazione che riceverà altri due argomenti: l'elemento e il valore di verità risultante.

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

Ora i risultati rimangono precisi:

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

Esistono quattro possibilità su come filtrare un elenco di due elementi in base al criterio di essere uguale a X . Ogni elemento potrebbe essere uguale o potrebbe essere diverso.

L'aspetto negativo di questo approccio è che si devono fornire versioni reificate di tutti i criteri.

Answer 4

Beh, cosa sapevi che ho appena capito. Quindi, eccomi qui a inviare una risposta alla mia domanda, come previsto una funzione molto breve ha fatto il lavoro:

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

Ottengo gli adulti di un paese // Ottengo gli adulti da un paese, Paese = Paese, Persone = Persone, Persona = una persona

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

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

Questo è un filtro in prolog // Questo è un filtro in prolog

Answer 6

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