Filter (hogere-ordefunctie)

In programmeertalen is filter een hogere-ordefunctie waarmee een datastructuur (vaak een lijst) in een bepaalde volgorde wordt doorlopen om een nieuwe datastructuur te produceren die alleen de elementen bevat uit de oorspronkelijke datastructuur waarvoor een predicaat waar is.

De functie komt onder andere voor in Haskell[1], Objective Caml[2], Standard ML[3], Python[4], Erlang, Perl (onder de naam grep) en JavaScript. Common Lisp bevat de functies remove-if en remove-if-not. SRFI 1 bevat een implementatie van filter voor Scheme[5]. C++ bevat de functies remove_if en remove_copy_if[6]. Smalltalk heeft select: voor collecties.

Definitie

De filter-functie kan als volgt gedefinieerd worden (in Haskell): 

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

Filter kan ook geschreven worden met lijstcomprehensie in talen die deze taalconstructie ondersteunen: 

 filter :: (a -> Bool) -> [a] -> [a]
 filter p lijst = [ x | x <- lijst, p x ]

Voorbeelden

In Haskell:

filter even [1..10]

De notatie [1..10] geeft de lijst met getallen van 1 tot en met 10. De filter-functie geeft een lijst terug met getallen waarvoor het meegegeven predicaat (even) waar is. In dit geval geeft het bovenstaande stuk code een lijst met alleen de even getallen: [2, 4, 6, 8, 10]. Op vergelijkbare wijze zal het volgende stuk code de lijst met oneven getallen produceren:

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

waarbij . functie-compositie weergeeft. Het predicaat (not . even) is alleen waar voor oneven getallen en dit zorgt ervoor dat filter de lijst met oneven getallen produceert: [1, 3, 5, 7, 9].