高階関数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

高階関数(こうかいかんすう、: higher-order function)とは、関数(手続き)を引数にしたり、あるいは関数(手続き)を戻り値とするような関数のことである。

概要[編集]

高階関数は厳密には第一級関数をサポートしているプログラミング言語において定義されるため、一般にリフレクションなしではプログラムの実行時に動的に生成することができないCのような関数ポインタをサポートしている言語は第一級関数をサポートしているとは見なされていない。

高階関数は関数を引数にしたり、あるいは関数を戻り値とするものであり、引数や戻り値の関数もまた高階関数となり得る。高階関数は主に関数型言語やその背景理論であるラムダ計算において多用される。

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

種類[編集]

関数を呼び出す関数[編集]

以下に示す(apply_2_3 f)は与えられた演算を行い値を返すものである。遅延評価されるため、f は評価されずに (apply_2_3 add)(apply_2_3 mul) のように関数そのものを引数とすることができる。

(define (add x y) (+ x y))
(define (mul x y) (* x y))
(define (apply_2_3 f) (f 2 3))
 
(apply_2_3 add) ; => (add 2 3) => 5
(apply_2_3 mul) ; => (mul 2 3) => 6

カリー化[編集]

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

; 通常の定義,呼び出し
(define (add x y) (+ x y))
(add 2 3) ;=> 5
; カリー化を施した定義,呼び出し
(define (add x) (lambda (y) (+ x y)))
((add 2) 3) ;=> 5

ほとんどの型付き関数型言語においては、関数は最初からカリー化して与えるのが一般的である(つまり n 引数関数を、n 個の引数の直積を取る関数とするのではなく、1 引数の高階関数を n 個並べたような型で定義する。)

例えば Haskell において、

(2 +)

と記述すると、これは先ほどの (add 2) と同じく、2を足す関数になる。加算演算子(+)が既にカリー化されているため、1 引数を適用するだけで関数として機能するのである。以下は実行例。

Prelude> 2 + 3
5
Prelude> (2 +) 3
5

map[編集]

map関数はリスト構造の各要素に対して順々に与えられた関数を処理していくものである。関数型言語以外の言語でも実装されていることがある。

(map func list0 list1 ... listN)

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

(map (lambda (n) (+ 1 n)) '(1 2 3))
;=> '(2 3 4)

filter[編集]

リストの各要素に対して与えられた条件式を適用し、真であるものだけをリストにまとめて返すものである。単純な条件式の代わりに真偽値を与える関数を指定したとき、高階関数であると言える。

fold[編集]

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

右方向の畳み込み(foldr)と左方向の畳み込み(foldl)があり、言語によっては最初から同様の機能が組み込まれていることがある(詳しくはfoldの英語版記事の該当項目を参照)。

Right-fold-transformation.png Left-fold-transformation.png

unfold[編集]

foldの逆変換。すなわち初期値から何らかの動作を行なってリストを生成する関数である。例えるならば漸化式数列に直す操作に相当する。

手続き型言語における高階関数[編集]

手続き型言語や、手続き型をベースにしたオブジェクト指向言語でも、同等かそれに近い機能を実現させる機構を備えているものがある。CFortranにおける関数ポインタなどがその一例である。ただし、言語にカリー化の機能や関数閉包の機能はない。

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

typedef int (*Function) (int, int) ;
 
int foldl (int values [], int values_length, Function f, int identityElement)
  {
  int folded = identityElement ;
  for (int i=0 ; i<values_length ; ++i)
    {folded = (*f) (folded, values [i]) ;} /* 左結合 */
  return folded ;
  }
 
int foldr (int values [], int values_length, Function f, int identityElement)
  {
  int folded = identityElement ;
  for (int i=values_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) ;
  return 0;
  }

一方、関数を戻り値とする関数を書くことは難しい。これは関数閉包と呼ばれる戻り値となる関数の実行時にその関数を定義した時点での環境が必要になるためである。

脚注[編集]

  1. ^ : functional argument/parameter
  2. ^ : procedural argument/parameter

関連項目[編集]