ATSプログラミング入門:
PrevChapter 3. 関数Next

高階関数

高階関数とは別の関数を引数として取るような関数です。 例えば、次に定義する関数 rtfind は高階関数の例です: 

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

整数から整数への関数が与えられた時、 rtfind は関数の根となるような最初の自然数を探します。 例えば、 rtfind を多項式の関数 lam x => x * x - x - 110 に呼び出すと 11 が返ります。 もし根を持たない関数に適用されると、 rtfind は無限ループすることに注意してください。

高階関数はコードの再利用を促進します。ここではその単純な例を示そうと思います。 次に定義する関数 sum と prod は 1 から与えられた自然数までの和と積をそれぞれ計算します: 

fun sum (n: int): int = if n > 0 then sum (n-1) + n else 0
fun prod (n: int): int = if n > 0 then prod (n-1) * n else 1

関数 sum と prod の間における類似点は明白です。 高階関数 ifold を定義して、 sum と prod を ifold にもとづいて実装することができます: 

//
fun ifold
  (n: int, f: (int, int) -> int, ini: int): int =
  if n > 0 then f (ifold (n-1, f, ini), n) else ini
//
fun sum (n: int): int = ifold (n, lam (res, x) => res + x, 0)
fun prod (n: int): int = ifold (n, lam (res, x) => res * x, 1)
//

もし 1 から与えられた自然数 n までの範囲の整数の二乗の和を計算するのであれば、 ifold を使って次のようにたやすく定義できます: 

fun sqrsum (n: int): int = ifold (n, lam (res, x) => res + x * x, 0)

1 から n までの整数の中で与えられた数 d の倍数を選んで二乗の和を計算するために、 sqrsum を一般化して次の関数 sqrmodsum を作ることを考えましょう: 

fun sqrmodsum
  (n: int, d: int): int =
  ifold (n, lam (res, x) => if x mod d = 0 then res + x * x else res, 0)
// end of [sqrmodsum]

無環境関数とクロージャ関数の差異に慣れていない人にとって、 この一般化が実際には動かないことは少し意外かもしれません。 その単純な理由は ifold は二番目の引数に無環境関数が渡されることを期待していますが、 sqrmodsum の本体で ifold に渡す関数は d を使っているため明らかに無環境ではないためです。 この問題に対処するために、次のような ifold の変形を実装し、 それからその変形にもとづいて sqrmodsum を実装することができます: 

//
fun
ifold2
(
  n: int, f: (int, int) -<cloref1> int, ini: int
) : int =
  if n > 0 then f (ifold2 (n-1, f, ini), n) else ini
// end of [ifold2]
//
fun
sqrmodsum (n: int, d: int): int =
  ifold2 (n, lam (res, x) => if x mod d then res + x * x else res, 0)
// end of [sqrmodsum]
//

ifold2 は確かに ifold よりも一般的ですが、代償を伴います。 sqrmodsum が呼び出されると、クロージャ関数をヒープの中に生成してから ifold2 に渡さなければなりません; このクロージャ関数は関数が返った後はもはや使いません。 そのメモリはガベージコレクション (GC) が回収するまで解放されません。 そのため GC が無効な場合 sqrmodsum のような関数呼び出しは、 たやすくメモリリークを引き起こしてしいまいます。 幸運にも、明示的にプログラマが解放することで、 GC がなくともメモリリークを引き起こさない線形クロージャ関数も ATS は備えています。 この興味深いプログラミングの機能は別の章で紹介します。

より多くのATSの機能が導入されれば、高階関数はより効果的にコードの再利用ができるようになるでしょう。

PrevHomeNext
無環境関数とクロージャ関数Up例: 二分探索遊び