Filtr (yuqori darajadagi funktsiya) - Filter (higher-order function)

Yilda funktsional dasturlash, filtr a yuqori darajadagi funktsiya bu ishlov beradigan a ma'lumotlar tuzilishi (odatda a ro'yxat ) qandaydir tarzda ma'lumotlar bazasi tarkibidagi aynan shu elementlarni o'z ichiga olgan yangi ma'lumotlar tuzilishini yaratish predikat qaytaradi mantiqiy qiymat to'g'ri.

Misol

Yilda Xaskell, kod misoli

 filtr hatto [1..10]

predikatni qo'llash orqali 2, 4,…, 10 ro'yxatiga baho beradi hatto 1, 2,…, 10 tamsayılar ro'yxatining har bir elementiga shu tartibda va predikat mantiqiy qiymatini qaytaradigan elementlarning yangi ro'yxatini yaratadi va shu bilan ushbu ro'yxatning faqat juft a'zolarini o'z ichiga olgan ro'yxatni beradi. Aksincha, kod misoli

 filtr (emas . hatto) [1..10]

1, 3,…, 9 ro'yxatiga predikat bo'lgan 1, 2,…, 10 tamsayılar ro'yxatining elementlarini yig'ish orqali baho beradi. hatto mantiqiy qiymatini false bilan qaytaradi (bilan . bo'lish funktsiya tarkibi operatori ).

Vizual misol

Quyida siz butun sonlar ro'yxati uchun filtrlash jarayonining har bir bosqichining ko'rinishini ko'rishingiz mumkin X = [0, 5, 8, 3, 2, 1] funktsiyasiga ko'ra:

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

Ushbu funktsiya ifoda etadi ${displaystyle x}$ hatto qaytish qiymati ham ${displaystyle True}$ , aks holda u ${displaystyle False}$ . Bu predikat.

filtr funktsiyasini qayta ishlash bosqichlarini qo'llash

Ro'yxatdagi filtr funktsiyasini qo'llashda ishlov berish bosqichlarini ko'rish

Tilni taqqoslash

Filtr ko'pchilik uchun standart funktsiya dasturlash tillari, masalan, Haskell,^[1]OCaml,^[2]Standart ML,^[3]yoki Erlang.^[4]Umumiy Lisp funktsiyalarini ta'minlaydi olib tashlash-agar va agar yo'q bo'lsa, olib tashlang.^[5]Amalga oshirish uchun sxemalar (SRFI) 1 til uchun filtrni amalga oshirishni ta'minlaydi Sxema.^[6]C ++ beradi algoritmlar olib tashlash_if (mutatsiyaga uchragan) va olib tashlash_copy_if (mutatsiyaga uchramaydigan); C ++ 11 qo'shimcha ravishda ta'minlaydi nusxa_if (mutatsiyaga uchramaydigan).^[7] Kichik munozarasi beradi tanlang: to'plamlar uchun usul. Filtrni yordamida ham amalga oshirish mumkin tushunchalar ro'yxati ularni qo'llab-quvvatlaydigan tillarda.

Haskellda, filtr quyidagicha amalga oshirilishi mumkin:

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

Bu yerda, [] bo'sh ro'yxatni bildiradi, ++ ro'yxatni birlashtirish jarayoni va [x | p x] shartli ravishda qiymatga ega bo'lgan ro'yxatni bildiradi, x, agar shart bo'lsa p x ushlaydi (uchun baholaydi To'g'ri).

Turli tillarda filtrlash
Til	Filtr	Izohlar
APL	`(oldindan qator)/qator`
C # 3.0	`ienum.Qaerda (oldindan)` yoki The `qayerda` band	Kengaytma usuli qayerda ienum IEnumerable Xuddi shunday barcha .NET tillarida
CFML	`obj.filter (funktsiya)`	Qaerda `obj` bu massiv yoki tuzilishdir. The `funktsiya` argument sifatida har bir elementning qiymatini oladi.
Klojure	`(filtr predikat ro'yxat)^[8]`	Yoki, orqali ro'yxatni tushunish: `(uchun [x ro'yxat :qachon (oldindan x)] x)`
Umumiy Lisp	`(olib tashlash-agar teskari-pred ro'yxat) (olib tashlash-agar (to'ldiruvchi) oldindan) ro'yxat) (agar yo'q bo'lsa, olib tashlang oldindan ro'yxat)`	Funktsiya `agar yo'q bo'lsa, olib tashlang` eskirgan^[5] ekvivalenti foydasiga `olib tashlash-agar` bu erda predikat to'ldiriladi.^[9] Shunday qilib filtr `(olib tashlash-agar-bo'lmasa # 'oddp' (0 1 2 3))` yozilishi kerak `(olib tashlash-if (komplement # 'oddp)' (0 1 2 3))` yoki oddiyroq: `(olib tashlash-if # 'evenp' (0 1 2 3))` qayerda `juft` ning teskari qiymatini qaytaradi `g'alati`.^[10]
C ++	`std :: remove_copy_if (boshlash, oxiri, natija, oldindan belgilash) std :: copy_if (boshlash, oxiri, natija, oldindan) (C ++ 11)`	sarlavhasida boshlash, oxiri, natija iteratorlar predikat teskari
D.	`std.algorithm.filter! (oldindan)(ro'yxat)`
Erlang	`ro'yxatlar: filter (Qiziqarli, Ro'yxat)`	Yoki, orqali ro'yxatni tushunish: `[X \|\| X <- Ro'yxat, qiziqarli (X)]`
Groovy	`ro'yxat.findAll (oldindan)`
Xaskell	`filtr oldindan ro'yxat`	Yoki, orqali ro'yxatni tushunish: `[x \| x <- ro'yxat, oldindan x]`
Xaks	`ro'yxat.filtr (oldindan)` `Lambda.filter (ro'yxat, oldindan)`	Yoki, orqali ro'yxatni tushunish: `[x \| x <- ro'yxat, oldindan x]`
J	`(#~ oldindan) ro'yxat`	Monadik kanca misoli. # nusxa, ~ argumentlarni teskari yo'naltiradi. `(f g) y = y f (g y)`
Yuliya	`filtr (oldindan, qator)`	Filtrni funktsiyasi ham qabul qiladi `imlo` ma'lumotlar turi. Yoki, orqali ro'yxatni tushunish: `[x uchun x yilda qator agar oldindan (x)]`
Java 8+	`oqim.filtr (oldindan)`
JavaScript 1.6	`qator.filtr (oldindan)`
Kotlin	`qator.filtr (oldindan)`
Matematik	`Tanlang [ro'yxat, oldindan]`
Maqsad-C (Kakao Mac-da OS X 10.4+)	`[qator filteredArrayUsingPredicate:oldindan]`	`oldindan` bu NSPredicate ekspresivlikda cheklangan bo'lishi mumkin bo'lgan ob'ekt
F #, OCaml, Standart ML	`List.filter oldindan ro'yxat`
PARI / GP	`tanlang (expr, ro'yxat)`	2.4.2-bandda argumentlarning tartibi o'zgartirilgan.
Perl	`grep blokirovka qilish ro'yxat grep expr, ro'yxat`
PHP	`qator_filtri (qator, oldindan)`
Prolog	`filtr (+ Yopish, + Ro'yxat, -Ro'yxat)`	ISO / IEC 13211-1: 1995 / Cor.2: 2012 yildan beri^[11] asosiy standart orqali yopilish dasturi mavjud `qo'ng'iroq / N`^[12]
Python	`filtr (funktsiya, ro'yxat)`	Yoki, orqali ro'yxatni tushunish: `[x in x uchun ro'yxat agar oldindan(x)]`. Python 3-da, `filtr` ga qaytarish uchun o'zgartirildi iterator ro'yxat o'rniga.^[13] Qo'shimcha funktsionallik, iteratatorni predikat yolg'on bo'lgan elementlar ustiga qaytarish, shuningdek standart kutubxonada mavjud `qalbaki` ichida `itertools` modul.
Yoqut	`enum.find_all {blokirovka qilish} enum.select {blokirovka qilish}`	`enum` bu ro'yxat
Zang	`iterator.filtr (oldindan)`	`iterator` bu `Takrorlovchi` va `filtr` usul yangi iteratorni qaytaradi; `oldindan` funktsiyadir (xususan `FnMut`) iterator elementini qabul qiladigan va qaytaradigan a `bool`
S, R	`Filtr (oldindan,qator) qator[oldindan(qator)]`	Ikkinchi holda, oldindan vektorlangan funktsiya bo'lishi kerak
Scala	`ro'yxat.filtr (oldindan)`	Yoki tushunish uchun: `uchun (x <- ro'yxat; agar oldindan) hosil x`
Sxema R⁶RS	`(filtr oldindan ro'yxat)` `(olib tashlash teskari pred ro'yxat)` `(bo'lim oldindan ro'yxat ro'yxat)`
Kichik munozarasi	`aCollection tanlang: blokirovka`
Tez	`qator.filtr (oldindan) filtr (ketma-ketlik, oldindan)`
XPath, XQuery	`ro'yxat [blok]` `filtr (ro'yxat, funktsiya)`	Yilda `blokirovka qilish` kontekst elementi `.` joriy qiymatni ushlab turadi

Variantlar

Filtr o'zining natijasini asl ro'yxatni o'zgartirmasdan yaratadi. Ko'pgina dasturlash tillari, shuningdek, tezkor ishlash uchun ro'yxat argumentini destruktiv ravishda o'zgartiradigan variantlarni taqdim etadi. Filtrning boshqa variantlari (masalan, Haskell) tomchi^[14] va bo'lim^[15]) ham keng tarqalgan. Umumiy xotirani optimallashtirish uchun sof funktsional dasturlash tillari kirish ro'yxati va filtrlangan natijani eng uzun umumiy quyruq bilan bo'lishishdir (dumini bo'lishish ).

Shuningdek qarang

Adabiyotlar

^ filtr Haskell standart muqaddimasida
^ filtr ichida OCaml standart kutubxona moduli ro'yxat
^ "Ro'yxat tarkibi". Standart ML asoslari kutubxonasi. Olingan 2007-09-25.
^ 2. filtr modulning Erlang STDLIB qo'llanmasidagi hujjatida ro'yxatlar
^ ^a ^b Funktsiya O'chirish, olib tashlash-IF, olib tashlash-IF-NOT, O'chirish, O'chirish-IF, O'chirish-IF-NOT ichida Umumiy Lisp HyperSpec
^ filtr SRFI 1 da
^ olib tashlash_if va olib tashlash_copy_if SGIda Standart shablon kutubxonasi (STL) spetsifikatsiyasi
^ ClojureDocs-dagi clojure.core / filter
^ Funktsiya TO'LDIRUVCHI ichida Umumiy Lisp HyperSpec
^ Funktsiya EVENP, ODDP ichida Umumiy Lisp HyperSpec
^ ISO / IEC 13211-1: 1995 / Kor 2: 2012
^ http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call
^ "Ichki funktsiyalar - Python 3.9.0 hujjatlari". docs.python.org. Olingan 2020-10-28.
^ Haskell filtri tomchi
^ Haskell filtri bo'lim

[HaskellStandard-1] filtr Haskell standart muqaddimasida

[OcamlManual-2] filtr ichida OCaml standart kutubxona moduli ro'yxat

[3] "Ro'yxat tarkibi". Standart ML asoslari kutubxonasi. Olingan 2007-09-25.

[4] 2. filtr modulning Erlang STDLIB qo'llanmasidagi hujjatida ro'yxatlar

[remove-if-5] Funktsiya O'chirish, olib tashlash-IF, olib tashlash-IF-NOT, O'chirish, O'chirish-IF, O'chirish-IF-NOT ichida Umumiy Lisp HyperSpec

[SRFI1-6] filtr SRFI 1 da

[SGISTLSpec-7] olib tashlash_if va olib tashlash_copy_if SGIda Standart shablon kutubxonasi (STL) spetsifikatsiyasi

[8] ClojureDocs-dagi clojure.core / filter

[9] Funktsiya TO'LDIRUVCHI ichida Umumiy Lisp HyperSpec

[10] Funktsiya EVENP, ODDP ichida Umumiy Lisp HyperSpec

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

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

[13] "Ichki funktsiyalar - Python 3.9.0 hujjatlari". docs.python.org. Olingan 2020-10-28.

[14] Haskell filtri tomchi

[15] Haskell filtri bo'lim

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]