Filter (funksjon av høyere orden) - Filter (higher-order function)

I funksjonell programmering er filter en funksjon av høyere orden som behandler en datastruktur (vanligvis en liste ) i en eller annen rekkefølge for å produsere en ny datastruktur som inneholder nøyaktig de elementene i den opprinnelige datastrukturen som et gitt predikat returnerer den boolske verdien for true .

Eksempel

I Haskell , kodeeksemplet

 filter even [1..10]

evaluerer til listen 2, 4, ..., 10 ved å bruke predikatet evenpå hvert element i listen over heltall 1, 2, ..., 10 i den rekkefølgen og lage en ny liste over de elementene som predikatet returnerer den boolske verdien true for , og gir derved en liste som bare inneholder de jevne medlemmene på listen. Omvendt, kodeeksemplet

 filter (not . even) [1..10]

evalueres til listen 1, 3, ..., 9 ved å samle de elementer i listen over hele tall 1, 2, ..., 10 for hvilke de underliggende evenreturnerer den boolske verdi falske (med .å være den funksjon sammensetningen operatør ).

Visuelt eksempel

Nedenfor kan du se en oversikt over hvert trinn i filterprosessen for en liste med heltall i X = [0, 5, 8, 3, 2, 1]henhold til funksjonen:

$${\ displaystyle f (x) = {\ begin {cases} True & {\ text {if}} x \ equiv 0 {\ pmod {2}} \\ False & {\ text {if}} x \ equiv 1 {\ pmod {2}}. \ End {cases}}}$$

Denne funksjonen uttrykker at selv om returverdien er , ellers er det . Dette er predikatet. ${\ displaystyle x}$${\ displaystyle True}$${\ displaystyle False}$

Visning av behandlingstrinn ved bruk av filterfunksjon på en liste

Språksammenligning

Filter er en standardfunksjon for mange programmeringsspråk , f.eks. Haskell, OCaml , Standard ML eller Erlang . Common Lisp gir funksjonene remove-ifog remove-if-not. Skjema forespørsler for implementering (Srfl) 1 gir en implementering av filter for språket ordningen . C ++ gir algoritmene remove_if (muterende) og remove_copy_if(ikke-muterende); C ++ 11 gir i tillegg copy_if(ikke-muterende). Smalltalk gir select:metoden for samlinger. Filter kan også realiseres ved hjelp av listeforståelser på språk som støtter dem.

I Haskell, filterkan implementeres slik:

 filter :: (a -> Bool) -> [a] -> [a]
 filter _ []     = []
 filter p (x:xs) = [x | p x] ++ filter p xs

Her []angir den tomme listen, ++listen sammenkoblingsoperasjon, og [x | p x]angir en liste som betinget holder en verdi x, hvis betingelsen p xholder (evalueres til True).

Varianter

Filter skaper resultatet uten å endre den opprinnelige listen. Mange programmeringsspråk gir også varianter som ødeleggende endrer listeargumentet i stedet for raskere ytelse. Andre varianter av filter (f.eks. Haskell dropWhileog partition) er også vanlige. En vanlig minneoptimalisering for rent funksjonelle programmeringsspråk er å ha inngangslisten og det filtrerte resultatet til å dele den lengste felles halen ( haledeling ).

Se også

• Kart (funksjon av høyere orden)
• Listeforståelse
• Guard (databehandling)

Referanser