カリー化関数 (curried function) について

Scheme

SML という言語のテキストを読んでいて、これまで自分がカリー化という言葉をよく理解せずに使っていたことに気付きました。

どうやら部分適用の概念と混同していたようです。

一般に、ML や Haskell のような関数型言語においては、カリー化とは n 要素タプルを取る関数

fun f (x,y) = z

を、n 引数関数

fun curried_f x y = z

に変形することと同義らしいです。(n > 1, z は適当な式とします)

ML 等では n 引数を取る関数

fun f x1 x2 ... xn = z   (* 1 *)

は、実体としては次のように1引数関数が n 個連なったものとして定義されています。

val f = fn x1 => fn x2 => ... fn xn => z   (* 2 *)

(1 と 2 は同値であり、1 は 2 の構文糖衣に過ぎません)

f は、最初の引数を渡すと第2引数を受け取る関数を返し、それに次の引数を与えると第3引数を受け取る関数を返す…、という高階関数として定義されているわけです。これがいわゆるカリー化なんですね。

そして、カリー化関数の適用のイメージを Scheme 的に表してみると、

((...((f x1) x2)...) xn)

のように、最後の引数を与えるまでは常に部分適用が行われていることになります。この適用過程の途中で自由にストップすることもできます。

n 要素タプルの場合はそれができない (n 個の値全てを一度に与えなければいけない) わけなんですが、n 引数関数 (カリー化関数) にすることで部分適用が可能になる、ということで、カリー化と部分適用とが対になる概念であることが分かりました。


一方、Scheme でカリー化関数を定義するには、基本的に

(define f
  (lambda (x1)
    (lambda (x2)
      ...
      (lambda (xn)
        z))))

と、lambda をネストさせることになります。また、カリー化せず普通に多変数関数として定義されたものは、自然に部分適用することができません。

比較してみましょう。

SML:

fun add x y = x+y;
val add1 = add 1;
add1 2 = 3;     (* true *)

add 1 を評価すると、y を受け取って 1+y を計算する関数が返されます。

Scheme:

(define (add x y) (+ x y))
(define add1 (lambda (y) (add 1 y)))
(= (add1 2) 3)  ; #t

y を受け取って (add 1 y) を評価する関数を新たに作っています。

SML 版との違いに注目してください。add 関数の呼び出しが残っている分、無駄がありますよね。

ここにカリー化の、部分適用以外の利点を見ることができます: もし、カリー化された関数の前半の方で重たい処理を済ませておければ (そしてそれを何度も適用する必要があるなら)、部分適用によって軽い処理だけを後に残すことができるんです。

このような段階的な効率化の手法をステージング、と言うそうです。部分的なメモ化、とも言えるでしょう。


ところで、lambda を書かずに済む関数定義の書式:

(define (f x)
  ...)

を MIT スタイルと言いますが、MzScheme ではこれをさらに拡張したスタイルがサポートされています:

(define ((add x) y) (+ x y))
(define add1 (add 1))
(= (add1 2) 3)  ; #t

カリー化関数が自然に定義できるようになっているんです。MIT スタイル同様、定義の形が適用と同じ形になっています。