Szűrő (magasabb rendű funkció) - Filter (higher-order function)

A funkcionális programozás során a szűrő egy magasabb rendű függvény, amely valamilyen adatstruktúrát (általában listát ) dolgoz fel valamilyen célból, hogy új adatstruktúrát hozzon létre, amely pontosan azokat az elemeket tartalmazza az eredeti adatszerkezetből, amelyekre egy adott predikátum visszaadja a logikai értéket true .

Példa

A Haskell , a kód például

 filter even [1..10]

kiértékeli a 2, 4,…, 10 listát úgy, hogy az predikátumot evenaz 1, 2,…, 10 egész számok listájának minden elemére alkalmazza ebben a sorrendben, és létrehoz egy új listát azokról az elemekről, amelyekre a predikátum visszaadja a true logikai értéket , ezáltal olyan listát adva, amely csak a lista páros tagjait tartalmazza. Fordítva, a kód példa

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

kiértékeli az 1, 3,…, 9 listára az 1, 2,…, 10 egész számok listájának azon elemeinek összegyűjtésével, amelyekre a predikátum evenhamis logikai értéket ad vissza ( .a függvényösszetétel -operátorral ).

Vizuális példa

Az alábbiakban megtekintheti a szűrési folyamat egyes lépéseinek nézetét X = [0, 5, 8, 3, 2, 1]a függvény szerinti egész számok listájához :

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

Ez a függvény azt fejezi ki, hogy ha még a visszatérési érték is , akkor egyébként . Ez a predikátum. ${\ displaystyle x}$${\ displaystyle True}$${\ displaystyle False}$

A feldolgozási lépések nézete a szűrőfunkció listán történő alkalmazásakor

Nyelvi összehasonlítás

A szűrő szabványos funkció sok programozási nyelvhez , pl. Haskell, OCaml , Standard ML vagy Erlang . A Common Lisp biztosítja a funkciókat remove-ifés remove-if-not. A Scheme Requests for Implementation (SRFI) 1 megvalósítja a nyelvi séma szűrőjének megvalósítását . A C ++ biztosítja az algoritmusokat remove_if (mutáló) és remove_copy_if(nem mutáló); A C ++ 11 ezenkívül biztosítja copy_if(nem mutáló). A Smalltalk biztosítja a select:módszert a gyűjteményekhez. A szűrő az őket támogató nyelvek listájának megértésével is megvalósítható .

Haskellben a filterkövetkezőképpen valósítható meg:

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

Itt []az üres listát, ++a listafűzési műveletet [x | p x]jelöli , és feltételesen értéket tartalmazó listát jelöl x, ha a feltétel p xérvényes (értékeli a True) értéket.

Változatok

A szűrő az eredeti lista módosítása nélkül hozza létre eredményét. Sok programozási nyelv olyan változatokat is kínál, amelyek romboló módon módosítják a lista argumentumot a gyorsabb teljesítmény érdekében. A szűrő egyéb változatai (pl. Haskell dropWhileés partition) szintén gyakoriak. A közös memória optimalizálás a tisztán funkcionális programozási nyelvek az, hogy a bemeneti listában, majd szűrjük eredményeként részesedése a leghosszabb közös farok ( tail-megosztás ).

Lásd még

• Térkép (magasabb rendű funkció)
• A lista megértése
• Őr (számítástechnika)

Hivatkozások