第一級関数

計算機科学において、第一級関数（だいいっきゅうかんすう、英: first-class function、ファーストクラスファンクション）とは、関数を第一級オブジェクトとして扱うことのできるプログラミング言語の性質、またはそのような関数のことである。その場合その関数は、型のある言語では function type（en:Function type）などと呼ばれる型を持ち、またその値は関数オブジェクトなどになる。具体的にはプログラムの実行時に生成され、データ構造に含めることができ、他の関数の引数として渡したり、戻り値として返したりすることのできる関数をいう。この概念はメタプログラミングとは異なり、コンパイラ呼び出しやeval関数によって生成された関数は含まれない。無名関数も参照。 第一級関数は関数型言語には必要不可欠であり、高階関数のような形で日常的に用いられる。例として、関数とリストを引数に取り、リストの各要素に関数を適用した結果のリストを返すmap (mapcar) 関数が挙げられる。map関数をサポートするプログラミング言語は、何らかの形で関数を関数の引数として渡すことを許容しなければならない。 Schemeでの例: (map func list0 list1 ... listN) スタックベースのプログラミング言語では、高階関数の実装における自由変数の取り扱いに関して困難な問題が生じる。これはFunarg問題（"function argument" の略称、英: funarg problem）として知られている。 型理論では、型Aの値を受け取り、型Bの値を返す関数をA → B（もしくはBA）と書く。これはP → Qと似ているが実は同じもので、カリー・ハワード対応（カリー・ハワード同型対応、英: Curry-Howard correspondence）によれば、関数型は論理包含に関係しており、ラムダ抽象は自然演繹における仮説、関数の適用はモーダスポネンスに相当する。また多くのプログラミング言語の機能として、型理論は第一級関数が連想配列などのデータ構造をモデルするのにも用いられる。 圏論においては、第一級関数は閉圏に相当する。たとえば単純型付きラムダ計算（英: simply typed lambda calculus）は、カルテシアン閉圏（デカルト閉圏）の言語に相当する。 HaskellやLisp、ML、Schemeのような関数型言語は第一級関数を全面的にサポートしている。他に第一級関数をサポートしているプログラミング言語としては、ECMAScript (ActionScript、JavaScript)、Io、Lua、Nemerle、Perl、PHP、Python、Ruby、Scala、Tcl/Tkなどが挙げられる。 C言語やC++、Pascalなどのプログラミング言語は関数へのポインタをサポートしており、データ構造に含めたり他の関数に引数として渡したりすることができる。しかし、関数ポインタによって第一級関数をサポートしているとみなされてはいない。 C++はoperator()を含むユーザ定義演算子をサポートしており、operator()を持つクラスは関数オブジェクトとして扱うことができる。関数オブジェクトはC++では他の第一級オブジェクトと同じように操作することができる。また、C++11では無名関数がサポートされている。 #include <cmath> #include <iostream> #include <functional> auto derivative = [](std::function<double(double)> f, double delta) { return [=](double x) { return (f(x + delta) - f(x)) / delta; }; }; int main() { double (*psin)(double) = std::sin; auto cos = derivative(psin, 0.000001); std::cout << cos(0) << std::endl; } alias real delegate(real x) Delegate; Delegate makeDerivative(Delegate f, real deltaX) { return delegate real (real x) { return (f(x + deltaX) - f(x)) / deltaX; }; } void main() { real mySin(real s) { return std.math.sin(s); } Delegate cos = makeDerivative(&mySin, 0.000001); writefln(cos(0)); } -module(calculus). -export([derivate/2]). % F: 数値を受け取り数値を返す関数 % DeltaX: 小さい正の数 % Fの近似導関数を返す。 derivative(F, DeltaX) -> fun(X) -> (F(X + DeltaX) - F(X)) / DeltaX end. (define square (lambda (x) (* x x))) ;変数に関数リテラルを代入 (define fns (list + sin square)) ;リストの要素を関数に (define (compose f g) (lambda (x) (f (g x)))) ;2つの関数を引数として受け取り ;合成関数を返す関数 ((compose sqrt square) -3) ;他の関数の戻り値としての関数、引数に-3を適用 ;結果は3 (define fns-squared (map (lambda (fn) (compose square fn)) fns)) ;関数のリストを ;sqrt関数に合成 -> 関数のリスト (map (lambda(fn) (fn 3)) fns-squared) ;すべての関数に引数を3で適用 ;結果はリスト (9 0.01991485667481699 81) (lambda (a b) (* a b)) ; 関数リテラル ((lambda (a b) (* a b)) 4 5) ; 関数に4と5を渡す この例では第一級関数はIPアドレスのテーブルのソート戦略を指定するのに使われている。 network = { {name = "grauna", IP = "210.26.30.34"}, {name = "arraial", IP = "210.26.30.23"}, {name = "lua", IP = "210.26.23.12"}, {name = "derain", IP = "210.26.23.20"}, } テーブルのホスト名を辞書順の逆でソートするには、次のように書く。 table.sort(network, function (a,b) return (a.name > b.name) end) PROC newton = (REAL x, error, PROC (REAL) REAL f, f prime) REAL: # ニュートン法 # IF f(x) <= error THEN x ELSE newton (x - f(x) / f prime (x), error, f, f prime) FI; print(( newton(0.5, 0.001, (REAL x) REAL: x**3 - 2*x**2 + 6, (REAL x) REAL: 3*x**2 - 4**x), newline )); // 関数リテラル function(message){ print(message); }; // 関数リテラルをコールバックに代入 SomeObject.SomeCallBack = function(message){ print(message); }; arguments.calleeプロパティを使うとJavaScriptでも無名再帰関数を書くことができる。なお、ECMAScript5のstrict modeではarguments.calleeの使用は禁じられている。 my $divisor = 10; my $checker = sub { my $val = shift; if ($val % $divisor ) { return 0; } else { return 1; } }; これはPerlにおける第一級関数だけでなく、クロージャの例にもなっている。また留意すべきこととして、オブジェクト指向Perlにおいてはクラスに関数のリファレンスをblessすることが可能である。 Pythonではdef文またはlambda式によって関数を生成する。第一級関数としては十分柔軟であるが、lambda式によって定義できる関数の本体は式に限られ、文を含む関数を生成することはできない。 >>> #いくつかの組み込み関数とそれらの逆関数 >>> from math import sin, cos, acos, asin >>> # ユーザ定義関数とそれらの逆関数を追加 >>> cube = lambda x: x * x * x >>> croot = lambda x: x ** (1/3.0) >>> # 関数の戻り値から関数を生成する第一級関数 >>> # compose(f,g)(x) == f(g(x)) >>> compose = lambda f1, f2: ( lambda x: f1(f2(x)) ) >>> # 第一級関数は配列の要素として扱える >>> funclist = [sin, cos, cube] >>> funclisti = [asin, acos, croot] >>> # 整数のように自然にリストから関数を適用 >>> [compose(inversef, f)(.5) for f, inversef in zip(funclist, funclisti)] [0.5, 0.49999999999999989, 0.5] >>> JavaScriptは第一級関数をサポートする。関数はレキシカルスコープを作り出す。 // f: 数値を受け取って数値を返す関数 // deltaX: 微小な正の数 // fの近似導関数を返す関数 function makeDerivative ( f, deltaX ) { return function (x) { return ( f(x + deltaX) - f(x) ) / deltaX; }; } var cos = makeDerivative( Math.sin, 0.000001 ); // cos(0) ~> 1 // cos(Math.PI/2) ~> 0 C# 2.0から匿名メソッド (anonymous method) を、またC# 3.0からラムダ式を、それぞれサポートする。 using System; class Program { // f: doubleを受け取ってdoubleを返す関数 // deltaX: 微小な正の数 // fの導関数の近似を返す関数 static Func<double, double> MakeDerivative(Func<double, double> f, double deltaX) { return (x) => (f(x + deltaX) - f(x - deltaX)) / (2 * deltaX); } static void Main() { var cos = MakeDerivative(Math.Sin, 0.00000001); Console.WriteLine(cos(0)); // 1 Console.WriteLine(cos(Math.PI / 2)); // 0 } } def deriv(f, dx) ->(x){ (f[x + dx] - f[x]) / dx } end sin = ->(x){ Math.sin(x) } cos = deriv(sin, 0.00000001) puts sin[Math::PI / 2] puts cos[Math::PI / 2] import Math._ def deriv(f:Double => Double, dx:Double) = (x:Double) => (f(x + dx) - f(x)) / dx val cos = deriv(sin, 0.00000001) Console.println(sin(Pi / 2)) Console.println(cos(Pi / 2)) derivative f delta = \x -> (f (x+delta) - f x) / delta main = do let sin' = derivative sin 0.00000001 let x = pi / 3 print (sin x) print (sin' x) <?php $greet = function($name) { echo "Hello $name"; }; $greet('World'); // Hello Worldを出力 無名関数 クロージャ 関数オブジェクト 第一級オブジェクト ^ Programming language pragmatics, by Michael Lee Scott, section 11.2 "Functional Programming". Rosetta CodeにおけるFirst-class functions