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).