高階関数
高階関数（こうかいかんすう、）とは、第一級関数をサポートしているプログラミング言語において、関数（手続き）を引数にしたり、あるいは関数（手続き）を戻り値とするような関数のことである。
高階関数は厳密には第一級関数をサポートしているプログラミング言語において定義される。C言語やPascalでは、関数へのポインタを利用して高階関数を模倣することができるが、関数ポインタによって第一級関数をサポートしているとみなされてはいない。
高階関数は関数を引数にしたり、あるいは関数を戻り値とするものであり、引数や戻り値の関数もまた高階関数となり得る。高階関数は主に関数型言語やその背景理論であるラムダ計算において多用される。
また、ある関数（手続き）の引数となる関数（手続き）のことを関数引数や手続き引数と呼ぶこともある。
以下に示すcodice_1は与えられた演算を行い値を返すものである。遅延評価されるため、codice_2 は評価されずに codice_3 や codice_4 のように関数そのものを引数とすることができる。
複数の引数をとる関数を1変数関数に置き換えることをカリー化と呼ぶ。例えば二つの数を足し合わせる関数 codice_5 は以下のようになる。
ほとんどの型付き関数型言語においては、関数は最初からカリー化して与えるのが一般的である（つまり n 引数関数を、n 個の引数の直積を取る関数とするのではなく、1 引数の高階関数を n 個並べたような型で定義する。）
と記述すると、これは先ほどの codice_6 と同じく、2を足す関数になる。加算演算子（codice_7）が既にカリー化されているため、1 引数を適用するだけで関数として機能するのである。以下は実行例。
リストの各要素に対して与えられた条件式を適用し、真であるものだけをリストにまとめて返すものである。単純な条件式の代わりに真偽値を与える関数を指定したとき、高階関数であると言える。
例えば、リスト'(1 2 -3 -4 5)から、正の数のみを抽出するには以下のようにする。
複数のリストからタプルを要素とする1つのリストを生成する。
例えば、'(1 2 3)と'(a b c)に対してzipを行うと以下のようになる。
zipの逆操作。タプルを要素とする1つのリストから複数のリストを生成する。
schemeには実装されていないが実装されていれば以下のように動作する:
ただし、実際には単一の戻り値しか返せない処理系・言語の場合、この戻り値のタプルとして返すことがある。その場合は以下のようになる。
"map"関数はリスト構造の各要素に対して順々に与えられた関数を処理していくものである。関数プログラミングではないパラダイムの言語でも実装されていることがある。
例えば、リスト'(1 2 3)の各要素に対して1を足したリストを得たい場合は以下のようにすれば良い。
"fold" 関数は、堆積、畳み込みや折り畳みなどと呼ばれ、英語では"reduce"、"inject"とも表現される。foldはリストの各要素に対して与えられた関数を適用する。
例えば、リスト'(1 2 3)の各要素の総和を取るには以下のようにできる。
右方向の畳み込み（"foldr"）と左方向の畳み込み（"foldl"）があり、言語によっては最初から同様の機能が組み込まれていることがある（詳しくはの該当項目を参照）。
foldの逆変換。すなわち初期値から何らかの動作を行なってリストを生成する関数である。例えるならば漸化式を数列に直す操作に相当する。
seedにfuncを適用しfuncの戻り値をリストへ格納し、seedをiterate-updateで更新してfuncを適用しfuncの戻り値をリストへ格納し、…といった操作をseedがconditionを真にするまで繰り返す。
例えば、要素4からリスト'(3 2 1)を生成するには、以下のようにする。
複数のリストそれぞれを要素とするタプルを返す関数と見た時、直積集合を求める演算も高階関数と考えられる。R言語のouter関数などで実装されている。
（あるいは単にscan）とは、リストの各要素に対して繰り返し演算を行い累積した計算結果のリストを返す高階関数である。schemeでの実装例は以下のようになる。
prefix scanの中で、特に和の演算はprefix sum, cumulative sumとも呼ばれる。ここでは先ほど定義したcodice_8を使用して'(1 2 3 4 5 6 7 8 9 10)のprefix sumを求める例を示す。
prefix scanは並列アルゴリズム、GPGPUの分野で研究される。またprefix sumの特殊系としてもある。
手続き型言語や、手続き型をベースにしたオブジェクト指向言語でも、同等かそれに近い機能を実現させる機構を備えているものがある。CやFortranにおける関数ポインタなどがその一例である。ただし、言語にカリー化の機能やクロージャの機能はない。
例えばCで関数を引数にとる関数を書くと次のようになる。
一方、関数を戻り値とする関数を書くことは難しい。これはクロージャと呼ばれる戻り値となる関数の実行時にその関数を定義した時点での環境が必要になるためである。