Wikipedia

高階関数

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

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

概要

編集

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

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

関数を呼び出す関数

編集

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

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 は以下のようになる。 

# 通常の定義と呼び出し
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を足したリストを得たい場合は以下のようにすれば良い。 

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

for-each

編集

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

filter

編集

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

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での実装例。 

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

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相当である。初期状態を省略するとリストの先頭の要素が初期状態になる。 

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

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

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

foldは二項演算子   が結合法則を満たす場合は並列化が可能であり、上記のfold_leftの例ならば  と計算すれば良い。

scan

編集

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

Pythonでの実装例。 

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

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相当である。初期状態を省略するとリストの先頭の要素が初期状態になる。 

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の特殊系としてsegmented scan（英語版）もある。

unfold

編集

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

初期状態initialから始めて、

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

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

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" → "" と遷移する。 

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

関数ポインタ

編集
→「関数へのポインタ」も参照

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

例えば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;
}

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

脚注

編集
[脚注の使い方]

出典

編集
  1. ^ 英: functional argument/parameter
  2. ^ 英: procedural argument/parameter
  3. ^ “Data.List”. hackage.haskell.org. 2025年3月25日閲覧。
  4. ^ “Seq”. scala-lang.org. 2025年3月25日閲覧。
  5. ^ “OCaml library : Seq”. ocaml.org. 2025年3月25日閲覧。
  6. ^ Contributors, F# Software Foundation; Microsoft; F#. “Seq (FSharp.Core)”. FSharp.Core. 2025年3月25日閲覧。

関連項目

編集
「https://ja.wikipedia.org/w/index.php?title=高階関数&oldid=104235068」から取得