查看“︁Filter (高阶函数)”︁的源代码

{{NoteTA|G1=IT}}
在[[函数式编程]]中，'''过滤器'''（filter）是一个[[高阶函数]]，它按某种次序处理一个[[数据结构]]（通常是[[列表 (抽象数据类型)|列表]]），来产一个新的数据结构，它精确的包含最初数据结构中给定{{en-link|谓词 (数理逻辑)|Predicate (mathematical logic)|谓词}}对其返回[[布尔值]]<code>true</code>的那些元素。

==定义==

=== Python ===
在[[Python]]中，<code>filter</code>在说明文档中的语法是<code>filter(function,iterable)</code>
可以用如下办法用[[列表推导式]]实现<syntaxhighlight lang="python3">
output = [x for x in iterable if function]
</syntaxhighlight>在Python2中<code>filter</code>返回一个<code>list</code>，而在Python3中<code>filter</code>返回一个迭代器对象。

=== Haskell ===
在[[Haskell]]中，<code>filter</code>可以如下这样实现：
<syntaxhighlight lang="haskell">
filter :: (a -> Bool) -> [a] -> [a]
filter _ []     = []
filter p (x:xs) = [x | p x] ++ filter p xs
</syntaxhighlight>

这里的<code><nowiki>[]</nowiki></code>指示空列表，<code>++</code>是列表串接算子，而<code>[x | p x]</code>指示有条件持有一个值<code>x</code>的列表，如果条件<code>p x</code>成立（求值为<code>True</code>）。

==例子==

=== 在[[Haskell]]中代码例子 ===
<syntaxhighlight lang="haskell">
filter even [1..10]
</syntaxhighlight>

求值得到列表<code>2, 4, …, 10</code>，这是通过应用谓词<code>even</code>到整数列表<code>1, 2, …, 10</code>的按原次序的所有元素，并建立谓词对其返回布尔值<code>true</code>的那些元素的一个新的列表，因而给出的是只包含原列表的偶数成员的一个列表。反过来，代码例子：
<syntaxhighlight lang="haskell">
filter (not . even) [1..10]
</syntaxhighlight>
求值得出列表<code>1, 3, …, 9</code>，这是通过搜集整数列表<code>1, 2, …, 10</code>中，谓词对其返回布尔值<code>false</code>的那些元素（这里的<code>.</code>是{{en-link|函数复合 (计算机科学)|Function composition (computer science)|函数复合算子}}）。

=== 在[[Python3]]中代码例子 ===
<syntaxhighlight lang="python3">
>>>print(list(filter(lambda x:x % 2 == 0,[1,2,3,4,5,6,7,8])))  #输出偶数
[2, 4, 6, 8]

</syntaxhighlight>

=== 可视的例子 ===
下面是一个过滤器过程的每个步骤的可视演示，对于整数列表<code>X = [0, 5, 8, 3, 2, 1]</code>依据函数：
::<math>f(x) = \begin{cases} True &\text{ if } x \equiv 0 \pmod{2}\\ False & \text{ if } x \equiv 1 \pmod{2} .\end{cases}</math>

这个函数表达了如果<math>x</math>是偶数，则返回值是<math>True</math>，否则是<math>False</math>，这是谓词。
[[File:Filter-steps-loillierbe.gif|alt=applying filter function processing steps|none|thumb|353x353px|在应用过滤器在列表上的时候的处理步骤的演示]]

==语言比较==
过滤器是很多[[编程语言]]的标准函数，比如Haskell<ref name="HaskellStandard">[http://haskell.org/onlinereport/standard-prelude.html#$vfilter <code>filter</code>] {{Wayback|url=http://haskell.org/onlinereport/standard-prelude.html#$vfilter |date=20210507023825 }} in the Haskell Standard Prelude</ref>、[[OCaml]]<ref name="OcamlManual">[http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html <code>filter</code>] {{Webarchive|url=http://arquivo.pt/wayback/20160515115311/http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html |date=2016-05-15 }} in the [[OCaml]] standard library module <code>list</code></ref>、[[Standard ML]]<ref>{{cite web|url=http://www.standardml.org/Basis/list.html#SIG:LIST.filter:VAL|work=The Standard ML Basis Library|title=The List structure|accessdate=2007-09-25|archive-date=2008-02-01|archive-url=https://web.archive.org/web/20080201135810/http://www.standardml.org/Basis/list.html#SIG:LIST.filter:VAL}}</ref>或[[Erlang]]<ref>[http://www.erlang.org/doc/doc-5.5.4/lib/stdlib-1.14.4/doc/html/lists.html#filter/2 <code>filter/2</code>] in the Erlang STDLIB Reference Manual documentation of the module <code>lists</code></ref>。[[Common Lisp]]提供了函数<code>remove-if</code>和<code>remove-if-not</code><ref name="remove-if">[http://www.lispworks.com/documentation/HyperSpec/Body/f_rm_rm.htm#remove-if-not ''Function'' '''REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT'''] {{Wayback|url=http://www.lispworks.com/documentation/HyperSpec/Body/f_rm_rm.htm#remove-if-not |date=20201112023548 }} in the [[Common Lisp HyperSpec]]</ref>。{{en-link|Scheme实现要求|Scheme Requests for Implementation}}（SRFI）1提供了[[Scheme]]语言过滤器的一个实现<ref name="SRFI1">[http://srfi.schemers.org/srfi-1/srfi-1.html#FilteringPartitioning <code>filter</code>] {{Wayback|url=http://srfi.schemers.org/srfi-1/srfi-1.html#FilteringPartitioning |date=20210529181946 }} in SRFI 1</ref>。[[C++]]提供了{{en-link|Algorithm (C++)|Algorithm (C++)|算法}}<code>remove_if</code>（可变）和<code>remove_copy_if</code>（不可变）；[[C++11]]补充提供了<code>copy_if</code>（不可变）<ref name="SGISTLSpec">[http://www.sgi.com/tech/stl/remove_if.html <code>remove_if</code>] {{Wayback|url=http://www.sgi.com/tech/stl/remove_if.html |date=20171116103950 }} and [http://www.sgi.com/tech/stl/remove_copy_if.html <code>remove_copy_if</code>] {{Wayback|url=http://www.sgi.com/tech/stl/remove_copy_if.html |date=20171116105043 }} in the SGI [[Standard Template Library]] (STL) spec</ref>。[[Smalltalk]]为搜集提供了<code>select:</code>方法。过滤器还可以在支持[[列表推导式]]的语言中使用它来实现。

{| class="wikitable" style="font-size: 85%"
|+ 在各种语言中的Filter
! 语言 !! Filter !! 注释
|-
| [[APL语言|APL]]
| <code>(''pred'' ''array'')/''array''</code>
|
|-
| [[C♯|C#]] 3.0
| <code>''ienum''.Where(''pred'')</code><br/>或<br/><code>where</code>子句<ref>[https://msdn.microsoft.com/en-us/library/bb311043.aspx where clause (C# Reference)] {{Wayback|url=https://msdn.microsoft.com/en-us/library/bb311043.aspx |date=20160908184526 }}.</ref>
| 这里是一个扩展方法<br />ienum是一个IEnumerable<br />在所有.NET语言中都是类似的
|-
| {{en-link|ColdFusion标记语言|ColdFusion Markup Language|CFML}}
| <code>obj.filter(func)</code>
| 这里<code>obj</code>是一个数组或结构。<code>func</code>接受作为参数的是每个元素的值。
|-
| [[Clojure]]
| <code>(filter ''predicate'' ''list'')<ref>[http://clojuredocs.org/clojure_core/1.3.0/clojure.core/filter clojure.core/filter on ClojureDocs]</ref></code>
| 或通过[[列表推导式#Clojure|列表推导式]]: <code>(for [x ''list'' :when (''pred'' x)] x)</code>
|-
| [[Common Lisp]]
| <code>(remove-if ''inverted-pred'' ''list'')<br />(remove-if (complement ''pred'') ''list'')<br />(remove-if-not ''pred'' ''list'')</code>
| 函数<code>remove-if-not</code>已经废弃<ref name="remove-if"/>，支持等价的谓词取补的<code>remove-if</code><ref>[http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/fun_complement.html ''Function'' '''COMPLEMENT'''] {{Wayback|url=http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/fun_complement.html |date=20190917222824 }} in the [[Common Lisp HyperSpec]]</ref>。因此过滤器<code>(remove-if-not #'oddp '(0 1 2 3))</code>应当写为<code>(remove-if (complement #'oddp) '(0 1 2 3))</code>或更简单的<code>(remove-if #'evenp '(0 1 2 3))</code>，这里的<code>evenp</code>返回的<code>oddp</code>的反转值<ref>[http://clhs.lisp.se/Body/f_evenpc.htm ''Function'' '''EVENP, ODDP'''] {{Wayback|url=http://clhs.lisp.se/Body/f_evenpc.htm |date=20111115010916 }} in the [[Common Lisp HyperSpec]]</ref>。
|-
| [[C++]]
| <code>std::remove_copy_if(''begin'', ''end'', ''result'', ''prednot'')<br />std::copy_if(''begin'', ''end'', ''result'', ''pred'') (C++11)</code>
| 在头文件<algorithm>中<br />begin, end, result是迭代器<br />谓词是反转的
|-
| [[D语言|D]]
| <code>std.algorithm.filter!(''pred'')(''list'')</code>
|
|-
| [[Erlang]]
| <code>lists:filter(''Fun'', ''List'')</code>
| 或通过[[列表推导式#Erlang|列表推导式]]: <code>[ X <nowiki>||</nowiki> X <- List, Fun(X) ]</code>
|-
| [[Groovy]]
| <code>''list''.findAll(''pred'')</code>
| 
|-
| [[Haskell]]
| <code>filter ''pred'' ''list''</code>
| 或通过[[列表推导式#Haskell|列表推导式]]: <code>[x <nowiki>|</nowiki> x <- ''list'', ''pred'' x]</code>
|-
| [[Haxe]]
| <code>''list''.filter(''pred'')</code><br/><code>Lambda.filter(''list'', ''pred'')<br/></code>
| 或通过[[列表推导式#Haxe|列表推导式]]: <code>[x <nowiki>|</nowiki> x <- ''list'', ''pred'' x]</code>
|-
| [[J语言|J]]
| <code>(#~ ''pred'') ''list''</code>
| 一元hook的一个例子。#复制，~逆转实际参数。<code>(f g) y = y f (g y)</code>
|-
| [[Julia (编程语言)|Julia]]
| <code>filter(''pred'', ''array'')</code>
| 过滤器函数还接受<code>''dict''</code>数据类型，或通过[[列表推导式]]: <code>[''x'' for ''x'' in ''array'' if ''pred(x)'']</code>
|-
| [[Java]] 8+
| <code>''stream''.filter(''pred'')</code>
|
|-
| [[JavaScript]] 1.6
| <code>''array''.filter(''pred'')</code>
|
|-
|[[Kotlin]]
|<code>''array''.filter(''pred'')</code>
|
|-
| [[Mathematica]]
| <code>Select[''list'', ''pred'']</code>
|
|-
| [[Objective-C]] ([[Cocoa]]在Mac [[OS X]] 10.4+中)
| <code>[''array'' filteredArrayUsingPredicate:''pred'']</code>
| <code>''pred''</code>是一个[https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSPredicate_Class/Reference/NSPredicate.html NSPredicate] {{Wayback|url=https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSPredicate_Class/Reference/NSPredicate.html |date=20090825213439 }}对象，它在表达力上有限
|-
| [[F♯|F#]], [[OCaml]], [[Standard ML]]
| <code>List.filter ''pred'' ''list''</code>
|
|-
| {{en-link|PARI/GP|}}
| <code>select(''expr'', ''list'')</code>
| 参数次序是在v. 2.4.2中是逆转的。
|-
| [[Perl]]
| <code>grep ''block'' ''list''<br /> grep ''expr'', ''list''</code>
|
|-
| [[PHP]]
| <code>array_filter(''array'', ''pred'')</code>
|
|-
| [[Prolog]]
| <code>filter(+Closure,+List,-List)</code>
| 自从ISO/IEC 13211-1:1995/Cor.2:2012<ref name="Cor.2">{{Cite web |url=http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=58033 |title=ISO/IEC 13211-1:1995/Cor 2:2012 |access-date=2021-02-11 |archive-date=2016-08-04 |archive-url=https://web.archive.org/web/20160804040307/http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=58033 }}</ref>，核心标准通过<code>call/N</code><ref>{{Cite web |url=http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call |title=存档副本 |access-date=2021-02-11 |archive-date=2021-05-07 |archive-url=https://web.archive.org/web/20210507045548/https://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call }}</ref>包含闭包应用。
|-
| [[Python]]
| <code>filter(''func'', ''list'')</code>
| 或通过[[列表推导式#Python|列表推导式]]: <code>[x for x in ''list'' if ''pred''(x)]</code>。在Python 3中，<code>filter</code>被变更为返回一个[[迭代器]]而非一个列表<ref>{{Cite web|title=Built-in Functions — Python 3.9.0 documentation|url=https://docs.python.org/3/library/functions.html#filter|access-date=2020-10-28|website=docs.python.org|archive-date=2012-10-25|archive-url=https://web.archive.org/web/20121025141808/http://docs.python.org/py3k/library/functions.html#filter}}</ref>。功能互补的，返回谓词对其是假的元素之上的一个迭代器，在标准库的<code>itertools</code>模块中也能获得为<code>filterfalse</code>。
|-
| [[Ruby]]
| <code>''enum''.find_all {''block''}<br /> ''enum''.select {''block''}</code>
| <code>''enum''</code>是个Enumeration
|-
| [[Rust]]
| <code>''iterator''.filter(''pred'')</code>
| <code>''iterator''</code>是一个<code>Iterator</code><ref>{{Cite web |url=https://doc.rust-lang.org/std/iter/trait.Iterator.html |title=Trait std::iter::Iterator |access-date=2021-02-11 |archive-date=2021-06-06 |archive-url=https://web.archive.org/web/20210606143458/https://doc.rust-lang.org/std/iter/trait.Iterator.html }}</ref>而<code>filter</code>方法返回一个新的迭代器；<code>''pred''</code>是一个函数（特别是<code>FnMut</code><ref>{{Cite web |url=https://doc.rust-lang.org/std/ops/trait.FnMut.html |title=Trait std::ops::FnMut |access-date=2021-02-11 |archive-date=2020-12-04 |archive-url=https://web.archive.org/web/20201204082353/https://doc.rust-lang.org/std/ops/trait.FnMut.html }}</ref>），它接受迭代器的项目并返回一个<code>bool</code><ref>{{Cite web |url=https://doc.rust-lang.org/std/primitive.bool.html |title=Primitive Type bool |access-date=2021-02-11 |archive-date=2021-05-15 |archive-url=https://web.archive.org/web/20210515071646/https://doc.rust-lang.org/std/primitive.bool.html }}</ref>。
|-
| [[S语言|S]], [[R语言|R]]
| <code>Filter(''pred'',''array'')<br />''array''[''pred''(''array'')]</code>
| 在第二种情况，pred必须是可向量化函数
|-
| [[Scala]]
| <code>''list''.filter(''pred'')</code>
| 或者通过for-推导式: <code>for(x <- ''list''; if ''pred'') yield x</code>
|-
| [[Scheme]] R<sup>6</sup>RS
| <code>(filter ''pred'' ''list'')</code><br /><code>(remove ''inverted pred'' ''list'')</code><br /><code>(partition ''pred'' ''list'' ''list'')</code>
|
|-
| [[Smalltalk]]
| <code>''aCollection'' select: ''aBlock''</code>
|
|-
| [[Swift]]
| <code>''array''.filter(''pred'')<br /> filter(''sequence, ''pred'')</code>
|
|-
| [[XPath]], {{en-link|XQuery|}}
| <code>list[block]</code><br /> <code>filter(list, func)</code>
| 在<code>block</code>上下文中项目<code>.</code>持有当前值
|}

==变体==
过滤器建立它的结果而不修改最初的列表。很多编程语言还提供破坏性修改列表实际参数的有更快性能的变体。过滤器的其他变体（比如Haskell <code>dropWhile</code><ref>{{Cite web |url=http://haskell.org/onlinereport/standard-prelude.html#$vdropWhile |title=Haskell filter ''dropWhile'' |access-date=2021-02-11 |archive-date=2021-05-07 |archive-url=https://web.archive.org/web/20210507023825/https://www.haskell.org/onlinereport/standard-prelude.html#$vdropWhile }}</ref>和<code>partition</code><ref>{{Cite web |url=http://www.haskell.org/onlinereport/list.html#sect17.3 |title=Haskell filter ''partition'' |access-date=2021-02-11 |archive-date=2021-05-01 |archive-url=https://web.archive.org/web/20210501120124/https://www.haskell.org/onlinereport/list.html#sect17.3 }}</ref>）也是常见的。常见的[[纯函数式编程]]语言{{en-link|程序优化|Program optimization|内存优化}}是拥有输入列表并过滤结果共享最长尾部。

==参见==
* [[Map (高阶函数)]]
* [[Fold (高阶函数)]]
* [[列表推导式]]
* [[卫语句]]

==引用==
{{Reflist|2}}

[[Category:高阶函数]]
[[Category:编程语言比较]]