Filter (高階函數)

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

## 定義

### Python

在Python中，`filter`在說明文檔中的語法是`filter(function,iterable)` 可以用如下辦法用列表推導式實現

```python3
output = [x for x in iterable if function]
```

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

### Haskell

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

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

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

## 例子

### 在Haskell中代碼例子

```haskell
filter even [1..10]
```

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

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

求值得出列表`1, 3, …, 9`，這是通過搜集整數列表`1, 2, …, 10`中，謂詞對其返回布爾值`false`的那些元素（這裡的`.`是函數複合 (電腦科學)）。

### 在Python3中代碼例子

```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$，這是謂詞。

<image>

## 語言比較

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

語言｜Filter｜注釋

APL｜`(''pred'' ''array'')/''array''`

C# 3.0｜`''ienum''.Where(''pred'')`或`where`子句｜這裡是一個擴展方法ienum是一個IEnumerable在所有.NET語言中都是類似的

ColdFusion標記語言｜`obj.filter(func)`｜這裡`obj`是一個陣列或結構。`func`接受作為參數的是每個元素的值。

Clojure｜`(filter ''predicate'' ''list'')<ref>[http://clojuredocs.org/clojure_core/1.3.0/clojure.core/filter clojure.core/filter on ClojureDocs]</ref>`｜或通過列表推導式: `(for [x ''list'' :when (''pred'' x)] x)`

Common Lisp｜`(remove-if ''inverted-pred'' ''list'')<br />(remove-if (complement ''pred'') ''list'')<br />(remove-if-not ''pred'' ''list'')`｜函數`remove-if-not`已經廢棄，支持等價的謂詞取補的`remove-if`。因此過濾器`(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`的反轉值。

C++｜`std::remove_copy_if(''begin'', ''end'', ''result'', ''prednot'')<br />std::copy_if(''begin'', ''end'', ''result'', ''pred'') (C++11)`｜在頭文件中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'')<br/>`｜或通過列表推導式: 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｜`select(''expr'', ''list'')`｜參數次序是在v. 2.4.2中是逆轉的。

Perl｜`grep ''block'' ''list''<br /> grep ''expr'', ''list''`

PHP｜`array_filter(''array'', ''pred'')`

Prolog｜`filter(+Closure,+List,-List)`｜自從ISO/IEC 13211-1:1995/Cor.2:2012，核心標準通過`call/N`包含閉包應用。

Python｜`filter(''func'', ''list'')`｜或通過列表推導式: `[x for x in ''list'' if ''pred''(x)]`。在Python 3中，`filter`被變更為返回一個迭代器而非一個列表。功能互補的，返回謂詞對其是假的元素之上的一個迭代器，在標準庫的`itertools`模塊中也能獲得為`filterfalse`。

Ruby｜`''enum''.find_all {''block''}<br /> ''enum''.select {''block''}`｜`''enum''`是個Enumeration

Rust｜`''iterator''.filter(''pred'')`｜`''iterator''`是一個`Iterator`而`filter`方法返回一個新的迭代器；`''pred''`是一個函數（特別是`FnMut`），它接受迭代器的項目並返回一個`bool`。

S, R｜`Filter(''pred'',''array'')<br />''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'')<br /> filter(''sequence, ''pred'')`

XPath, XQuery｜`list[block]` `filter(list, func)`｜在`block`上下文中項目`.`持有當前值

## 變體

過濾器建立它的結果而不修改最初的列表。很多程式語言還提供破壞性修改列表實際參數的有更快性能的變體。過濾器的其他變體（比如Haskell `dropWhile`和`partition`）也是常見的。常見的純函數式程式語言程序優化是擁有輸入列表並過濾結果共享最長尾部。