Chapter 22. 高階関数

高階関数は、その引数に他の関数を取る関数です。 int, bool, char, double, string のような基本型の範囲を表わすために BT を使ってみましょう。 単純な型 T は次の帰納的定義に従って形作られます:

• BT は単純な型です。

• T₀, T₁, ... T_n が単純な型であれば、(T₁, ..., T_n) -> T₀ も単純な型です。

order を次のように定義された、単純な型から自然数への関数だとします:

• order(BT) = 0

• order((T₁, ..., T_n) -> T₀) = max(order(T₀), 1 + order(T₁), ..., 1 + order(T_n))

単純な型 T の関数 f が与えられた時、order(T) = n なら f は n 階関数であると呼ぶことにします。 例えば、型 (int, int) -> int の関数は1階関数であり、型 int -> (int -> int) の関数もまた1階関数です。 さらに型 ((int -> int), int) -> int の関数は2階関数になります。 実際には、ほとんどの関数は1階関数で、ほとんどの高階関数は2階関数になります。

例として次のように、引数として整数から整数への関数 f を取り、f の根を探すような2階関数 find_root を実装してみましょう:

fn find_root
(
  f: int -<cloref1> int
) : int = let
//
fun loop
(
  f: int -<cloref1> int, n: int
) : int =
  if f (n) = 0 then n else (
    if n <= 0 then loop (f, ~n + 1) else loop (f, ~n)
  ) // end of [else] // end of [if]
in
  loop (f, 0)
end // end of [find_root]

もう一つの例として、関数の根を見つけるために、次のように有名なニュートン・ラフソン法 (Newton-Raphson's method) を実装してみましょう:

typedef
fdouble = double -<cloref1> double
//
macdef epsilon = 1E-6 (* precision *)
//
// [f1] is the derivative of [f]
//
fun
newton_raphson
(
  f: fdouble, f1: fdouble, x0: double
) : double = let
  fun loop (
    f: fdouble, f1: fdouble, x0: double
  ) : double = let
    val y0 = f x0
  in
    if abs (y0 / x0) < epsilon then x0 else
      let val y1 = f1 x0 in loop (f, f1, x0 - y0 / y1) end
    // end of [if]
  end // end of [loop]
in
  loop (f, f1, x0)
end // end of [newton_raphson]

// square root function
fn sqrt (c: double): double =
  newton_raphson (lam x => x * x - c, lam x => 2.0 * x, 1.0)
// cubic root function
fn cbrt (c: double): double =
  newton_raphson (lam x => x * x * x - c, lam x => 3.0 * x * x, 1.0)

高階関数は、共通した柔軟なコードの共有をサポートするためによく使われます。 関数引数はガベージコレクション (GC) を通して回収されるヒープに確保されたクロージャとしてしばしば表現されるため、GC を無効化した状態で高階関数は使われることは稀です。 ATS では、安全な作法で明示的に解放できる線形クロージャによって、GC 不在の環境における高階関数をサポートすることができます。 (GC が利用できないか単純に無効化された) システムプログラミングにおいて広範囲に高階関数を使うことができるのです。 線形クロージャの詳細については別の機会に紹介します。

この章で紹介したコード全体は オンライン から入手できます。