Filtr (funkce vyššího řádu) - Filter (higher-order function)

v Funkcionální programování, filtr je funkce vyššího řádu který zpracovává a datová struktura (obvykle a seznam ) v určitém pořadí k vytvoření nové datové struktury obsahující přesně ty prvky původní datové struktury, pro které daný predikát vrátí logická hodnota skutečný.

Příklad

v Haskell, příklad kódu

 filtr dokonce [1..10]

vyhodnotí do seznamu 2, 4,…, 10 použitím predikátu dokonce ke každému prvku v seznamu celých čísel 1, 2,…, 10 v uvedeném pořadí a vytvoření nového seznamu těch prvků, pro které predikát vrátí logickou hodnotu true, čímž získá seznam obsahující pouze sudé členy tohoto seznamu. Naopak příklad kódu

 filtr (ne . dokonce) [1..10]

vyhodnotí do seznamu 1, 3,…, 9 shromážděním prvků seznamu celých čísel 1, 2,…, 10, u nichž predikát dokonce vrací booleovskou hodnotu false (s . být operátor složení funkce ).

Vizuální příklad

Níže vidíte pohled na každý krok procesu filtrování pro seznam celých čísel X = [0, 5, 8, 3, 2, 1] podle funkce:

{displaystyle f (x) = {egin {cases} True & {ext {if}} xequiv 0 {pmod {2}} False & {ext {if}} xequiv 1 {pmod {2}}. end {cases}}}

Tato funkce vyjadřuje, že pokud ${displaystyle x}$ is even the return value is ${displaystyle True}$ , jinak je ${displaystyle False}$ . Toto je predikát.

Pohled na kroky zpracování při použití funkce filtru na seznam

Porovnání jazyků

Filtr je pro mnohé standardní funkcí programovací jazyky např. Haskell,^[1]OCaml,^[2]Standardní ML,^[3]nebo Erlang.^[4]Společný Lisp poskytuje funkce odstranit-pokud a odstranit, pokud ne.^[5]Systémové žádosti o implementaci (SRFI) 1 poskytuje implementaci filtru pro jazyk Systém.^[6]C ++ poskytuje algoritmy remove_if (mutující) a remove_copy_if (nemutující); C ++ 11 navíc poskytuje copy_if (nemutující).^[7] Pokec poskytuje vybrat: metoda pro sbírky. Filtr lze také realizovat pomocí seznam porozumění v jazycích, které je podporují.

V Haskellu, filtr lze implementovat takto:

 filtr :: (A -> Boole) -> [A] -> [A] filtr _ []     = [] filtr str (X:xs) = [X | str X] ++ filtr str xs

Tady, [] označuje prázdný seznam, ++ - operaci zřetězení seznamu a - [x | p x] označuje seznam podmíněně obsahující hodnotu, X, pokud je podmínka p x drží (hodnotí do Skutečný).

Filtrujte v různých jazycích
Jazyk	Filtr	Poznámky
APL	`(před pole)/pole`
C# 3.0	`ienum.Kde(před)` nebo The `kde` doložka	Kde je metoda rozšíření ienum je IEnumerable Podobně ve všech jazycích .NET
CFML	`obj. filtr (funkce)`	Kde `obj` je pole nebo struktura. The `func` obdrží jako argument hodnotu každého prvku.
Clojure	`(filtr predikát seznam)^[8]`	Nebo prostřednictvím seznam s porozuměním: `(pro [x seznam :když (před x)] x)`
Společný Lisp	`(odstranit-li obráceně-před seznam) (remove-if (doplněk před) seznam) (odstranit, pokud ne před seznam)`	Funkce `odstranit, pokud ne` byla ukončena podpora^[5] ve prospěch ekvivalentu `odstranit-pokud` kde je predikát doplněn.^[9] Tedy filtr `(remove-if-not # 'oddp' (0 1 2 3))` by mělo být napsáno `(remove-if (doplněk # 'oddp)' (0 1 2 3))` nebo jednodušeji: `(remove-if # 'evenp' (0 1 2 3))` kde `evenp` vrací obrácenou hodnotu `oddp`.^[10]
C ++	`std :: remove_copy_if (začít, konec, výsledek, prednot) std :: copy_if (začít, konec, výsledek, před) (C ++ 11)`	v záhlaví začít, konec, výsledek jsou iterátory predikát je obrácen
D	`std.algorithm.filter! (před)(seznam)`
Erlang	`seznamy: filtr (Zábava, Seznam)`	Nebo prostřednictvím seznam s porozuměním: `[X \|\| X <- seznam, zábava (X)]`
Báječný	`seznam.findAll (před)`
Haskell	`filtr před seznam`	Nebo prostřednictvím seznam s porozuměním: `[x \| x <- seznam, před X]`
Haxe	`seznam.filtr(před)` `Lambda.filter (seznam, před)`	Nebo prostřednictvím seznam s porozuměním: `[x \| x <- seznam, před X]`
J	`(#~ před) seznam`	Příklad monadického háku. # is copy, ~ obrátí argumenty. `(f g) y = y f (g y)`
Julie	`filtr(před, pole)`	Funkce filtru také přijímá `diktát` datový typ. Nebo prostřednictvím seznam s porozuměním: `[X pro X v pole -li před (x)]`
Jáva 8+	`proud.filtr(před)`
JavaScript 1.6	`pole.filtr(před)`
Kotlin	`pole.filtr(před)`
Mathematica	`Vybrat[seznam, před]`
Cíl-C (Kakao v systému Mac OS X 10.4+)	`[pole filterArrayUsingPredicate:před]`	`před` je NSPredicate objekt, který může být omezen v expresivitě
F#, OCaml, Standardní ML	`Seznam. Filtr před seznam`
PARI / GP	`vybrat(expr, seznam)`	Pořadí argumentů je obráceno ve v. 2.4.2.
Perl	`grep blok seznam grep expr, seznam`
PHP	`array_filter (pole, před)`
Prolog	`filtr (+ Uzavření, + Seznam, -List)`	Od ISO / IEC 13211-1: 1995 / Cor.2: 2012^[11] základní standard obsahuje uzavírací aplikaci přes `volání / č`^[12]
Krajta	`filtr(func, seznam)`	Nebo prostřednictvím seznam s porozuměním: `[x pro x in seznam -li před(X)]`. V Pythonu 3, `filtr` byl změněn na vrácení iterátor spíše než seznam.^[13] Doplňková funkce, která vrací iterátor nad prvky, pro které je predikát nepravdivý, je také k dispozici ve standardní knihovně jako `filtrfalse` v `itertools` modul.
Rubín	`výčet.find_all {blok} výčet.vyberte {blok}`	`výčet` je výčet
Rez	`iterátor.filtr(před)`	`iterátor` je `Iterátor` a `filtr` metoda vrací nový iterátor; `před` je funkce (konkrétně `FnMut`), který obdrží položku iterátoru a vrátí a `bool`
S, R	`Filtr(před,pole) pole[před(pole)]`	V druhém případě před musí být vektorizovaná funkce
Scala	`seznam.filtr(před)`	Nebo prostřednictvím porozumění: `pro (x <- seznam; -li před) výtěžek x`
Systém R⁶RS	`(filtr před seznam)` `(odstranit obrácená pred seznam)` `(rozdělit před seznam seznam)`
Pokec	`sbírka vybrat: překážka`
Rychlý	`pole.filtr(před) filtr(sekvence, před)`
XPath, XQuery	`seznam [blok]` `filtr (seznam, funkce)`	v `blok` kontextová položka `.` drží aktuální hodnotu

Varianty

Filtr vytvoří svůj výsledek bez úpravy původního seznamu. Mnoho programovacích jazyků také poskytuje varianty, které místo toho destruktivně upravují argument seznamu pro rychlejší výkon. Další varianty filtru (např. Haskell pokles^[14] a rozdělit^[15]) jsou také běžné. Běžný optimalizace paměti pro čistě funkční programovací jazyky je mít vstupní seznam a filtrovaný výsledek sdílení nejdelšího společného ocasu (sdílení ocasu ).

Viz také

Reference

^ filtr v Haskell Standard Prelude
^ filtr v OCaml standardní knihovní modul seznam
^ "Struktura seznamu". Standardní knihovna ML ML. Citováno 2007-09-25.
^ filtr / 2 v dokumentaci modulu Erlang STDLIB Reference Manual seznamy
^ ^A ^b Funkce REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT v Společný Lisp HyperSpec
^ filtr v SRFI 1
^ remove_if a remove_copy_if v SGI Standardní knihovna šablon (STL) spec
^ clojure.core / filtr na ClojureDocs
^ Funkce DOPLNĚK v Společný Lisp HyperSpec
^ Funkce EVENP, ODDP v Společný Lisp HyperSpec
^ ISO / IEC 13211-1: 1995 / Cor 2: 2012
^ http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call
^ "Built-in Functions - Python 3.9.0 documentation". docs.python.org. Citováno 2020-10-28.
^ Haskellův filtr pokles
^ Haskellův filtr rozdělit

[HaskellStandard-1] filtr v Haskell Standard Prelude

[OcamlManual-2] filtr v OCaml standardní knihovní modul seznam

[3] "Struktura seznamu". Standardní knihovna ML ML. Citováno 2007-09-25.

[4] filtr / 2 v dokumentaci modulu Erlang STDLIB Reference Manual seznamy

[remove-if-5] A ^b Funkce REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT v Společný Lisp HyperSpec

[SRFI1-6] filtr v SRFI 1

[SGISTLSpec-7] remove_if a remove_copy_if v SGI Standardní knihovna šablon (STL) spec

[8] ure.core / filtr na ClojureDocs

[9] Funkce DOPLNĚK v Společný Lisp HyperSpec

[10] Funkce EVENP, ODDP v Společný Lisp HyperSpec

[Cor.2-11] ISO / IEC 13211-1: 1995 / Cor 2: 2012

[12] ttp://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call

[13] "Built-in Functions - Python 3.9.0 documentation". docs.python.org. Citováno 2020-10-28.

[14] Haskellův filtr pokles

[15] Haskellův filtr rozdělit

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]