高階関数

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

* 関数（手続き）を引数に取る
* 関数を返す

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

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

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


```python
add = lambda x, y: x + y
mul = lambda x, y: x * y
apply_2_3 = lambda f: f(2, 3)

apply_2_3(add)  # 5
apply_2_3(mul)  # 6
```


### カリー化

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

```python
# 通常の定義と呼び出し
add = lambda x, y: x + y
add(2, 3)  # 5
# カリー化を施した定義と呼び出し
add = lambda x: lambda y: x + y
add(2)(3)  # 5
```


組み込みの関数が最初からカリー化されている言語がある。これは、関数呼び出しが常に1引数を取る関数を返すと定義するのと同じである（つまりn引数関数を、n個の引数の直積を取る関数とするのではなく、1引数の高階関数をn個並べたような型で定義する）。例えばHaskellにおいて、(2 +)と記述すると、これは先ほどの add(2) と同じく、2を足す関数になる。関数 + が既にカリー化されているため、1引数を適用するだけで関数として機能する。2 + 3も(2 +) 3もどちらも5になる。

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

### map
*map*関数はリスト構造の各要素に対して順々に与えられた関数を処理していくものである。ほとんどのプログラミング言語で実装されている。例えば、Pythonでリスト[1, 2, 3]の各要素に対して1を足したリストを得たい場合は以下のようにすれば良い。

```python
list(map(lambda x: x + 1, [1, 2, 3]))  # [2, 3, 4]
```


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

### filter
リスト中の各要素をおのおの引数として渡し、引数として渡された関数を呼び出し、その返り値が真なら返り値のリストに残し、偽なら排除される。排除したい要素に対して偽値を返す、述語のような役割の関数を与えて利用する。例えば、Pythonでリスト[1, 2, -3, -4, 5]から、正の数のみを抽出するには以下のようにする。

```python
list(filter(lambda x: x > 0, [1, 2, -3, -4, 5]))  # [1, 2, 5]
```


filterの並列アルゴリズムに関しては並列アルゴリズムを参照。

### fold
*fold* 関数は、堆積、畳み込みや折り畳みなどと呼ばれ、英語では*reduce*、*inject*とも表現される。foldは逐次処理を表現するためにあり、初期状態から始めて、funcは (状態, 要素) → 次の状態 という関数で、foldは最終状態を返す。状態遷移列を返すものがscanである。

関数型言語では、参照透過性を重んじていて、変数は書き換えてはならないが、下記のPythonの実装は変数stateを書き換えていて、変数書き換え無しで実装するには関数の再帰を使用する形となるが、読みやすくするための糖衣構文としてfoldがある。

Pythonでの実装例。

```python
def fold_left(iterable, func, initial):
    state = initial
    for x in iterable:
        state = func(state, x)
    return state
```



```python
def fold_right(iterable, func, initial):
    state = initial
    for x in reversed(iterable):
        state = func(x, state)
    return state
```


例えば、Pythonの場合、リスト[1, 2, 3, 4]の各要素の総和を取るには以下のようにできる。functools.reduceはfold_left相当である。初期状態を省略するとリストの先頭の要素が初期状態になる。

```python
from functools import reduce
reduce(lambda x, y: x + y, [1, 2, 3, 4])  # (((1 + 2) + 3) + 4) = 10
```


左方向の畳み込み（*foldl*）と右方向の畳み込み（*foldr*）とがあり、言語によっては最初から同様のものが標準ライブラリに含まれていることがある（詳しくはfoldの英語版記事の該当項目を参照）。


```python
# A123
fold_left([1, 2, 3], lambda s, i: f"{s}{i}", "A")
```



```python
# 123A
fold_right([1, 2, 3], lambda i, s: f"{i}{s}", "A")
```


foldは二項演算子 \oplus が結合法則を満たす場合は並列化が可能であり、上記のfold_leftの例ならば(A \oplus 1) \oplus (2 \oplus 3) = A1 \oplus 23 = A123 と計算すれば良い。

### scan
累積和（scan）は、逐次処理を表現するためにあり、初期状態から始めて、funcは (状態, 要素) → 次の状態 という関数で、scanは状態遷移列を返す。最終状態だけを返すのがfoldである。

Pythonでの実装例。

```python
def inclusive_scan(iterable, func, initial):
    state = initial
    for x in iterable:
        state = func(state, x)
        yield state
```



```python
def exclusive_scan(iterable, func, initial):
    state = initial
    for x in iterable:
        yield state
        state = func(state, x)
    # yield state  # この行を追加する流儀と追加しない流儀がある
```


scanの中で、特に二項演算子が足し算の場合はprefix sum, cumulative sumとも呼ばれる。ここではPythonで[1, 2, 3, 4, 5]の累積和を求める例を示す。itertools.accumulateはscan相当である。初期状態を省略するとリストの先頭の要素が初期状態になる。

```python
from itertools import accumulate
list(accumulate([1, 2, 3, 4, 5], lambda x, y: x + y))  # [1, 3, 6, 10, 15]
```


foldやscanは二項演算子が結合法則を満たす場合は並列化が可能であり、GPGPUの分野で使用されている。並列アルゴリズムの詳細は累積和を参照。

scanの特殊系としてもある。

### unfold
関数型言語では、数学的な関数で処理を記述するのを基本としており、goto、break、continueなどの処理の流れを変える命令は使わないという考え方で、その際、breakを使って中断するような逐次処理を書けるようにするためにunfoldがある。breakを使わずに実装する際は、関数の再帰を使い実装できるが、読みやすくするための糖衣構文がunfoldである。

初期状態initialから始めて、
* 処理を継続する際は、funcは 前の状態 → (出力要素, 次の状態) という関数になる。
* 処理を終了させる際は、以下のPythonの実装例ではNoneを返すと終了する。Haskellは`Nothing`、ScalaとOcamlとF#は`None`を返すと終了する。

多くのプログラミング言語の標準ライブラリで実装されているわけでは無いが、Haskell、Scala、OCaml、F#などで実装されている。


```python
def unfold(func, initial):
	state = initial
	while True:
		x = func(state)
		if x is None:
			break
		else:
			element, state = x
			yield element
```


"123"からリスト['1', '2', '3']を生成する例。状態は "123" → "23" → "3" → "" と遷移する。

```python
list(unfold(lambda s: (s[0], s[1:]) if s != "" else None, "123"))  # ['1', '2', '3']
```


## 関数ポインタ

現代では、ほとんどのプログラミング言語でクロージャ（ラムダ式）が使えるが、それらが使えない言語もあり、CやFortranにおける関数ポインタなどがその一例である。これらは言語にカリー化の機能やクロージャの機能がないという、制限はある。

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

```c
#include <assert.h>

/* int の二項演算 */
typedef int (*Function)(int, int);

/* 左結合 */
int foldl(int values[], int length, Function f, int identity_element) {
  int folded = identity_element;
  for (int i = 0; i < length; i++) {
    folded = (*f)(folded, values[i]);
  }
  return folded;
}

/* 右結合 */
int foldr(int values[], int length, Function f, int identity_element) {
  int folded = identity_element;
  for (int i = length - 1; 0 <= i; i--) {
    folded = (*f)(values[i], folded);
  }
  return folded;
}

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

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

/* 使用例 */
int main(void) {
  int values[5] = {31, 4, 159, 26, 53};
  int sum = foldl(values, sizeof values / sizeof(int), add, 0);
  int product = foldl(values, sizeof values / sizeof(int), mul, 1);
  assert(sum == 273);
  assert(product == 27168648);
  return 0;
}
```

一方、関数を戻り値とする関数を書くことは難しいため、クロージャを高階関数に渡すことができず、便利に使えない。高階関数が別の引数も受け付けるようにすれば、環境を閉じ込めることは不可能でないが、汎用性が低くなってしまう。

## 脚注

### 出典

## 関連項目
* 汎関数 - 数学における同様の概念
* モノイド