Filter (高階函數)

在函數式程式設計中，過濾器（filter）是一個高階函數，它按某種次序處理一個數據結構（通常是列表），來產一個新的數據結構，它精確的包含最初數據結構中給定謂詞（英語：Predicate (mathematical logic)）對其返回布林值true的那些元素。

定義

Python

在Python中，filter在說明文件中的語法是filter(function,iterable)

可以用如下辦法用列表推導式實現

output = [x for x in iterable if function]

在Python2中filter返回一個list，而在Python3中filter返回一個迭代器對象。

Haskell

在Haskell中，filter可以如下這樣實現：

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

這裏的[]指示空串列，++是列表串接算子，而[x | p x]指示有條件持有一個值x的列表，如果條件p x成立（求值為True）。

例子

在Haskell中代碼例子

filter even [1..10]

求值得到列表2, 4, …, 10，這是通過應用謂詞even到整數列表1, 2, …, 10的按原次序的所有元素，並建立謂詞對其返回布林值true的那些元素的一個新的列表，因而給出的是只包含原列表的偶數成員的一個列表。反過來，代碼例子：

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

求值得出列表1, 3, …, 9，這是通過搜集整數列表1, 2, …, 10中，謂詞對其返回布林值false的那些元素（這裏的.是函數複合算子（英語：Function composition (computer science)））。

在Python3中代碼例子

>>>print(list(filter(lambda x:x % 2 == 0,[1,2,3,4,5,6,7,8])))  #输出偶数
[2, 4, 6, 8]

可視的例子

下面是一個過濾器過程的每個步驟的可視演示，對於整數列表X = [0, 5, 8, 3, 2, 1]依據函數：

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

這個函數表達了如果 $x$ 是偶數，則返回值是 $True$ ，否則是 $False$ ，這是謂詞。

在應用過濾器在列表上的時候的處理步驟的演示

語言比較

過濾器是很多程式語言的標準函數，比如Haskell^[1]、OCaml^[2]、Standard ML^[3]或Erlang^[4]。Common Lisp提供了函數remove-if和remove-if-not^[5]。Scheme實現要求（英語：Scheme Requests for Implementation）（SRFI）1提供了Scheme語言過濾器的一個實現^[6]。C++提供了演算法（英語：Algorithm (C++)）remove_if（可變）和remove_copy_if（不可變）；C++11補充提供了copy_if（不可變）^[7]。Smalltalk為搜集提供了select:方法。過濾器還可以在支援列表推導式的語言中使用它來實現。

在各種語言中的Filter
語言	Filter	註釋
APL	`(pred array)/array`
C# 3.0	`ienum.Where(pred)` 或 `where`子句^[8]	這裏是一個擴充方法 ienum是一個IEnumerable 在所有.NET語言中都是類似的
CFML（英語：ColdFusion Markup Language）	`obj.filter(func)`	這裏`obj`是一個陣列或結構。`func`接受作為參數的是每個元素的值。
Clojure	`(filter predicate list)^[9]`	或通過列表推導式: `(for [x list :when (pred x)] x)`
Common Lisp	`(remove-if inverted-pred list) (remove-if (complement pred) list) (remove-if-not pred list)`	函數`remove-if-not`已經廢棄^[5]，支援等價的謂詞取補的`remove-if`^[10]。因此過濾器`(remove-if-not #'oddp '(0 1 2 3))`應當寫為`(remove-if (complement #'oddp) '(0 1 2 3))`或更簡單的`(remove-if #'evenp '(0 1 2 3))`，這裏的`evenp`返回的`oddp`的反轉值^[11]。
C++	`std::remove_copy_if(begin, end, result, prednot) std::copy_if(begin, end, result, pred) (C++11)`	在標頭檔<algorithm>中 begin, end, result是迭代器謂詞是反轉的
D	`std.algorithm.filter!(pred)(list)`
Erlang	`lists:filter(Fun, List)`	或通過列表推導式: `[ X \|\| X <- List, Fun(X) ]`
Groovy	`list.findAll(pred)`
Haskell	`filter pred list`	或通過列表推導式: `[x \| x <- list, pred x]`
Haxe	`list.filter(pred)` `Lambda.filter(list, pred)`	或通過列表推導式: `[x \| x <- list, pred x]`
J	`(#~ pred) list`	一元hook的一個例子。#複製，~逆轉實際參數。`(f g) y = y f (g y)`
Julia	`filter(pred, array)`	過濾器函數還接受`dict`資料類型，或通過列表推導式: `[x for x in array if pred(x)]`
Java 8+	`stream.filter(pred)`
JavaScript 1.6	`array.filter(pred)`
Kotlin	`array.filter(pred)`
Mathematica	`Select[list, pred]`
Objective-C (Cocoa在Mac OS X 10.4+中)	`[array filteredArrayUsingPredicate:pred]`	`pred`是一個NSPredicate （頁面存檔備份，存於互聯網檔案館）對象，它在表達力上有限
F#, OCaml, Standard ML	`List.filter pred list`
PARI/GP（英語：PARI/GP）	`select(expr, list)`	參數次序是在v. 2.4.2中是逆轉的。
Perl	`grep block list grep expr, list`
PHP	`array_filter(array, pred)`
Prolog	`filter(+Closure,+List,-List)`	自從ISO/IEC 13211-1:1995/Cor.2:2012^[12]，核心標準通過`call/N`^[13]包含閉包應用。
Python	`filter(func, list)`	或通過列表推導式: `[x for x in list if pred(x)]`。在Python 3中，`filter`被變更為返回一個迭代器而非一個列表^[14]。功能互補的，返回謂詞對其是假的元素之上的一個迭代器，在標準庫的`itertools`模組中也能獲得為`filterfalse`。
Ruby	`enum.find_all {block} enum.select {block}`	`enum`是個Enumeration
Rust	`iterator.filter(pred)`	`iterator`是一個`Iterator`^[15]而`filter`方法返回一個新的迭代器；`pred`是一個函數（特別是`FnMut`^[16]），它接受迭代器的專案並返回一個`bool`^[17]。
S, R	`Filter(pred,array) array[pred(array)]`	在第二種情況，pred必須是可向量化函數
Scala	`list.filter(pred)`	或者通過for-推導式: `for(x <- list; if pred) yield x`
Scheme R⁶RS	`(filter pred list)` `(remove inverted pred list)` `(partition pred list list)`
Smalltalk	`aCollection select: aBlock`
Swift	`array.filter(pred) filter(sequence, pred)`
XPath, XQuery（英語：XQuery）	`list[block]` `filter(list, func)`	在`block`上下文中專案`.`持有當前值

變體

過濾器建立它的結果而不修改最初的列表。很多程式語言還提供破壞性修改列表實際參數的有更快效能的變體。過濾器的其他變體（比如Haskell dropWhile^[18]和partition^[19]）也是常見的。常見的純函數式程式設計語言主記憶體最佳化（英語：Program optimization）是擁有輸入列表並過濾結果共用最長尾部。

參見

參照

^ filter （頁面存檔備份，存於互聯網檔案館） in the Haskell Standard Prelude
^ filter Portuguese Web Archive的存檔，存檔日期2016-05-15 in the OCaml standard library module list
^ The List structure. The Standard ML Basis Library. [2007-09-25]. （原始內容存檔於2008-02-01）.
^ filter/2 in the Erlang STDLIB Reference Manual documentation of the module lists
^ ^5.0 ^5.1 Function REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT （頁面存檔備份，存於互聯網檔案館） in the Common Lisp HyperSpec
^ filter （頁面存檔備份，存於互聯網檔案館） in SRFI 1
^ remove_if （頁面存檔備份，存於互聯網檔案館） and remove_copy_if （頁面存檔備份，存於互聯網檔案館） in the SGI Standard Template Library (STL) spec
^ where clause (C# Reference) （頁面存檔備份，存於互聯網檔案館）.
^ clojure.core/filter on ClojureDocs
^ Function COMPLEMENT （頁面存檔備份，存於互聯網檔案館） in the Common Lisp HyperSpec
^ Function EVENP, ODDP （頁面存檔備份，存於互聯網檔案館） in the Common Lisp HyperSpec
^ ISO/IEC 13211-1:1995/Cor 2:2012. [2021-02-11]. （原始內容存檔於2016-08-04）.
^ 存档副本. [2021-02-11]. （原始內容存檔於2021-05-07）.
^ Built-in Functions — Python 3.9.0 documentation. docs.python.org. [2020-10-28]. （原始內容存檔於2012-10-25）.
^ Trait std::iter::Iterator. [2021-02-11]. （原始內容存檔於2021-06-06）.
^ Trait std::ops::FnMut. [2021-02-11]. （原始內容存檔於2020-12-04）.
^ Primitive Type bool. [2021-02-11]. （原始內容存檔於2021-05-15）.
^ Haskell filter dropWhile. [2021-02-11]. （原始內容存檔於2021-05-07）.
^ Haskell filter partition. [2021-02-11]. （原始內容存檔於2021-05-01）.

[HaskellStandard-1] filter （頁面存檔備份，存於互聯網檔案館） in the Haskell Standard Prelude

[OcamlManual-2] filter Portuguese Web Archive的存檔，存檔日期2016-05-15 in the OCaml standard library module list

[3] The List structure. The Standard ML Basis Library. [2007-09-25]. （原始內容存檔於2008-02-01）.

[4] filter/2 in the Erlang STDLIB Reference Manual documentation of the module lists

[remove-if-5] 5.0 ^5.1 Function REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT （頁面存檔備份，存於互聯網檔案館） in the Common Lisp HyperSpec

[SRFI1-6] filter （頁面存檔備份，存於互聯網檔案館） in SRFI 1

[SGISTLSpec-7] remove_if （頁面存檔備份，存於互聯網檔案館） and remove_copy_if （頁面存檔備份，存於互聯網檔案館） in the SGI Standard Template Library (STL) spec

[8] where clause (C# Reference) （頁面存檔備份，存於互聯網檔案館）.

[9] ure.core/filter on ClojureDocs

[10] Function COMPLEMENT （頁面存檔備份，存於互聯網檔案館） in the Common Lisp HyperSpec

[11] Function EVENP, ODDP （頁面存檔備份，存於互聯網檔案館） in the Common Lisp HyperSpec

[Cor.2-12] ISO/IEC 13211-1:1995/Cor 2:2012. [2021-02-11]. （原始內容存檔於2016-08-04）.

[13] 存档副本. [2021-02-11]. （原始內容存檔於2021-05-07）.

[14] Built-in Functions — Python 3.9.0 documentation. docs.python.org. [2020-10-28]. （原始內容存檔於2012-10-25）.

[15] Trait std::iter::Iterator. [2021-02-11]. （原始內容存檔於2021-06-06）.

[16] Trait std::ops::FnMut. [2021-02-11]. （原始內容存檔於2020-12-04）.

[17] Primitive Type bool. [2021-02-11]. （原始內容存檔於2021-05-15）.

[18] Haskell filter dropWhile. [2021-02-11]. （原始內容存檔於2021-05-07）.

[19] Haskell filter partition. [2021-02-11]. （原始內容存檔於2021-05-01）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]