フィルタ（高階関数）

関数型プログラミングにおいて、filter は、データ構造(通常はリスト) を何らかの順序で処理し、指定された述語がブール値を返す元のデータ構造の要素を正確に含む新しいデータ構造を生成する高階関数です。 true

Haskellでは、コード例

 フィルター偶数[ 1 .. 10 ]  

は、1、2、… 、10 の整数のリストの各要素に述語をevenこの順序で適用し、述語がブール値 true を返す要素の新しいリストを作成することにより、リスト 2、4、…、10 に評価され、その結果、そのリストの偶数のメンバーのみを含むリストが生成されます。逆に、コード例

 フィルター(ない.偶数) [ 1 .. 10 ]    

even述語がブール値 false を返す整数のリスト 1、2、…、10 の要素を収集して、リスト 1、3、…、9 に評価されます( は関数合成演算子.です)。

X = [0, 5, 8, 3, 2, 1]以下に、関数に従って整数のリストのフィルター処理の各ステップのビューを示します。$${\displaystyle f(x)={\begin{cases}\mathrm {True} &{\text{ if }}x\equiv 0{\pmod {2}}\\\mathrm {False} &{\text{ if }}x\equiv 1{\pmod {2}}.\end{cases}}}$$

この関数は、が偶数の場合、戻り値は であり、そうでない場合は であることを表します。これが述語です。 ${\displaystyle x}$${\displaystyle \mathrm {真} }$${\displaystyle \mathrm {False} }$

filterは多くのプログラミング言語、例えばHaskell、^[1] OCaml、^[2] Standard ML、^[3] Erlangの標準関数です。^[4] Common Lispは関数remove-ifとを提供しますremove-if-not。^[5] Scheme Requests for Implementation (SRFI) 1は、言語Schemeのfilterの実装を提供します。^[6] C++はアルゴリズム remove_if(mutating)とremove_copy_if(non-mutating)を提供します。C ++11はさらにcopy_if(non-mutating)を提供します。^[7] Smalltalkはコレクション用のメソッドを提供します。filterは、リスト内包表記select:をサポートする言語ではそれを使用して実現することもできます。

Haskell では、filter次のように実装できます。

 フィルター:: ( a -> Bool ) -> [ a ] -> [ a ]フィルター_ [] = []フィルターp ( x : xs ) = [ x | p x ] ++フィルターp xs        
         
            

ここで、[]は空のリスト、++はリスト連結演算を表し、 は条件が成り立つ場合（ と評価される場合）、条件[x | p x]付きで値 を保持するリストを表します。 xp xTrue

フィルターは元のリストを変更せずに結果を作成します。多くのプログラミング言語では、パフォーマンスを高速化するために、代わりにリスト引数を破壊的に変更するバリアントも提供されています。フィルターの他のバリアント（Haskell dropWhile^[14]およびpartition^[15]など）も一般的です。純粋に関数型のプログラミング言語の一般的なメモリ最適化は、入力リストとフィルタリングされた結果に最長の共通テール（テール共有）を持たせることです。

• マップ（高階関数）
• リストの理解
• ガード（コンピューティング）