高階関数

高階関数とは、第一級関数をサポートしているプログラミング言語において少なくとも以下のうち1つを満たす関数である。

関数を引数に取る
関数を返す

1. 概要
-----

高階関数は厳密には第一級関数をサポートしているプログラミング言語において定義される。C言語やPascalでは、関数へのポインタを利用して高階関数を模倣することができるが、関数ポインタによって第一級関数をサポートしているとみなされてはいない。高階関数は主に関数型言語やその背景理論であるラムダ計算において多用される。

また、ある関数の引数となる関数のことを関数引数や手続き引数と呼ぶこともある。

2. 種類
-----

ここでは処理系に実装されていることが多いものだけをあげているが、高階関数も普通の関数と同様に、プログラマが自由に定義して利用できるということを特記しておく。

2.1. 関数を呼び出す関数
--------------

以下に示す関数apply_2_3は、与えられた関数に引数2と3を渡して呼び出し、その返り値を返す高階関数である。関数定義であるために、f は評価はされても、式は呼び出されず、 や  のように関数そのものを引数として渡して呼び出すことで評価される。

 )  )  )

 ; =>  => 5  ; =>  => 6<WtXmlEndTag />

2.2. カリー化
---------

複数の引数をとる関数を1変数関数に置き換えることをカリー化と呼ぶ。例えば二つの数を足し合わせる関数 add は以下のようになる。

通常の定義,呼び出し )  ;=> 5

カリー化を施した定義,呼び出し  ))  3) ;=> 5<WtXmlEndTag />

組み込みの関数が最初からカリー化されている言語がある。これは、関数呼び出しが常に1引数を取る関数を返すと定義するのと同じである

例えば en において、  と記述すると、これは先ほどの  と同じく、2を足す関数になる。関数 + が既にカリー化されているため、1 引数を適用するだけで関数として機能する。以下は実行例。 Prelude> 2 + 3 5 Prelude>  3 5

2.3. filter
-----------

リスト中の各要素をおのおの引数として渡し、引数として渡された関数を呼び出し、その返り値が真なら返り値のリストに残し、偽なら排除される。排除したい要素に対して偽値を返す、述語のような役割の関数を与えて利用する。 

例えば、リスト'から、正の数のみを抽出するには以下のようにする。 )

=> '<WtXmlEndTag />

2.4. zip
--------

複数のリストからタプルを要素とする1つのリストを生成する。 

例えば、'と'に対してzipを行うと以下のようになる。  ')

=> '  )<WtXmlEndTag />

これは引数を再構成するのに便利だが、高階関数ではない。

2.5. unzip
----------

zipの逆操作。タプルを要素とする1つのリストから複数のリストを生成する。 

以下のように動作する:   ))

=> ' '<WtXmlEndTag />

ただし、実際には単一の戻り値しか返せない処理系・言語の場合、この戻り値のタプルとして返すことがある。その場合は以下のようになる。    ))

=>   )  ))

=>    )<WtXmlEndTag />

これも引数の再構成に便利だが、高階関数ではない。

2.6. map
--------

//map//関数はリスト構造の各要素に対して順々に与えられた関数を処理していくものである。関数プログラミングではないパラダイムの言語でも実装されていることがある。 

例えば、リスト'の各要素に対して1を足したリストを得たい場合は以下のようにすれば良い。  ) ')

=> '<WtXmlEndTag />

2.7. for-each
-------------

mapと同じように動くが、結果を返さない。つまり、出力など、副作用を期待して利用する。

2.8. fold
---------

//fold// 関数は重畳関数、堆積、畳み込みや折り畳みなどと呼ばれ、英語では//reduce//、//inject//とも表現される。foldはリストの各要素に対して与えられた関数を適用する。 

例えば、リスト'の各要素の総和を取るには以下のようにできる。 )

=> 4<WtXmlEndTag />

右方向の畳み込みと左方向の畳み込みがあり、言語によっては最初から同様の機能が組み込まれていることがある。

)=> 6 ))と同じ ')

=> ' )))と同じ<WtXmlEndTag />

)=> 6 2 ) 3) と同じ ')

=> ' . 1) . 2) . 3) 1) 2 ) 3) と同じ<WtXmlEndTag />

2.9. unfold
-----------

foldの逆変換。すなわち初期値から何らかの動作を行なってリストを生成する関数である。例えるならば漸化式を数列に直す操作に相当する。  seedにfuncを適用しfuncの戻り値をリストへ格納し、seedをiterate-updateで更新してfuncを適用しfuncの戻り値をリストへ格納し、…といった操作をseedがconditionを真にするまで繰り返す。

例えば、要素4からリスト'を生成するには、以下のようにする。 x)  ) 3)

=> '<WtXmlEndTag />

2.10. 直積
--------

複数のリストそれぞれを要素とするタプルを返す関数と見た時、直積集合を求める演算も高階関数と考えられる。R言語のouter関数などで実装されている。

2.11. prefix scan
-----------------

prefix scanとは、リストの各要素に対して繰り返し演算を行い累積した計算結果のリストを返す高階関数である。schemeでの実装例は以下のようになる。   ) l)) ) ))))

prefix scanの中で、特に和の演算はprefix sum, cumulative sumとも呼ばれる。ここでは先ほど定義したscanを使用して'のprefix sumを求める例を示す。 )

=> '<WtXmlEndTag />

prefix scanは並列アルゴリズム、GPGPUの分野で研究される。またprefix sumの特殊系としてsegmented scanもある。

3. 関数型言語以外の言語と高階関数
------------------

関数型言語ではなくても、高階関数のような処理を行える場合がある。CやFortranにおける関数ポインタなどがその一例である。これらは言語にカリー化の機能やクロージャの機能がないという、制限はある。C#, C++, Tcl など、関数型言語でなくてもラムダ式がサポートされている言語は多い。

例えばCで関数を引数にとる関数を書くと次のようになる。

include /* int の二項演算 */ typedef int ;

/* 左結合 */ int foldl { int folded = identity_element; for  { folded = ; } return folded; }

/* 右結合 */ int foldr { int folded = identity_element; for  { folded = ; } return folded; }

/* 加算 */ int add { return x + y; }

/* 乗算 */ int mul { return x * y; }

/* 使用例 */ int main { int values[5] = {31, 4, 159, 26, 53}; int sum = foldl, add, 0); int product = foldl, mul, 1); assert; assert; return 0; }<WtXmlEndTag /> 一方、関数を戻り値とする関数を書くことは難しいため、クロージャを高階関数に渡すことができず、便利に使えない。高階関数が別の引数も受け付けるようにすれば、環境を閉じ込めることは不可能でないが、汎用性が低くなってしまう。

4. 脚注
-----

4.1. 出典
-------

5. 関連項目
-------

汎関数 - 数学における同様の概念
モノイド