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]依據函數:

 

這個函數表達了如果 是偶數,則返回值是 ,否則是 ,這是謂詞。

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

語言比較

過濾器是很多程式語言的標準函數,比如Haskell[1]OCaml[2]Standard ML[3]Erlang[4]Common Lisp提供了函數remove-ifremove-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 R6RS (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是擁有輸入列表並過濾結果共用最長尾部。

參見

參照

  1. ^ filter頁面存檔備份,存於互聯網檔案館) in the Haskell Standard Prelude
  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
  5. ^ 5.0 5.1 Function REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT頁面存檔備份,存於互聯網檔案館) in the Common Lisp HyperSpec
  6. ^ filter頁面存檔備份,存於互聯網檔案館) in SRFI 1
  7. ^ remove_if頁面存檔備份,存於互聯網檔案館) and remove_copy_if頁面存檔備份,存於互聯網檔案館) in the SGI Standard Template Library (STL) spec
  8. ^ where clause (C# Reference)頁面存檔備份,存於互聯網檔案館).
  9. ^ clojure.core/filter on ClojureDocs
  10. ^ Function COMPLEMENT頁面存檔備份,存於互聯網檔案館) in the Common Lisp HyperSpec
  11. ^ Function EVENP, ODDP頁面存檔備份,存於互聯網檔案館) in the Common Lisp HyperSpec
  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).