カリー化と部分適用

カリー化と部分適用

先日同僚にカリー化を説明する機会がありました。その際に、簡潔に説明に適した自分用の資料があるといいなと思いましたので、こちらの記事を書くことにしました。
この記事ではカリー化と部分適用について解説します。歴史等には触れずにただその内容について述べます。

混同しやすいという情報があるのですが、割と違うレイヤの話なのでなぜなのかは不明ですが、関連性に関する私見も末尾に書いておきます。

カリー化

カリー化 (Currying)^[1]とは 複数の引数を取る関数を、単一の引数を取る関数に翻訳する手法 のことです。

簡単な例を見ます。以下のような2つの引数を持つ関数を考えます。

const add = (a: number, b: number) => a + b;
console.log(add(1, 3)); // 4

これは以下のような第一引数を受け取って"残りの引数を受け取る関数"を返す関数と同じような意味を持つと考えられます。

const add_curried = (a: number) => (b: number) => a + b;
console.log(add_curried(1)(3)); // 4

関数を値のように返す関数のことを高階関数と呼びます。

カリー化: "翻訳" とはなにか

カリー化とは翻訳手法です。テクニックです。ところで、ここでいう翻訳とは何でしょうか。

翻訳は、「コンパイル」「トランスパイル」「エミュレーション」「帰着」などのことだと思えばよいです。（この記事ではこれらの用語の違いには特に踏み入らないです）

例えば、チューリングマシンやチューリング完全という言葉は聞いたことがあるでしょうか。これは計算とはなにか、を数学的に追い求めるために作られた想像上のマシンです。計算の能力をチューリングマシンは形式化しました。これにより、計算の限界を研究することができました。チューリングマシンは理論的に非常に重要です。
ところで、チューリングマシンでわかった重要な事項は、本当に我々の身近なプログラミング言語に応用できるでしょうか？そのことを示すのが「帰着」です。（大雑把に書けば）プログラミング言語を万能チューリングマシンに翻訳可能ならばチューリング完全と呼びます。一方で、プログラミング言語上で万能チューリングマシンを「エミュレート」できることは結構簡単にわかると思います（チューリングマシンの定義を知っていれば）。たとえばBrain*uckを実装してみたことのある方は多いのではないでしょうか。チューリングマシンは同じくらい単純な仕組みですので、似たようなものだと思えばよいでしょう。^[2]

これと同様に、カリー化も、理論的に意味のある対象に現代のプログラミング言語を「帰着」できることに意義があります。

型理論にはラムダ計算という非常にミニマルな計算体系があります。これは単一の引数しか受け取らない関数とその適用のみでなされる体系です。
JavaScriptで (x) => ... と f(...) だけを許す、みたいな体系です。例えば以下のような値を考えたりできます。

const k = (a) => (b) => a;
const s = (f) => (g) => (a) => f(a)(g(a));

この記事ではこれ以上深入りしませんが、この究極の純粋関数型みたいな体系もまた一つの計算の形式化です。^[3]

そして、こういった体系はやはりそれ自体で研究が進められており、実在するプログラミング言語をこれに帰着させることで得られるものがあります。その意味で意義があります。

ところで、ラムダ計算を単純に複数の引数を取るように拡張することもできるでしょう。それをしないのはなぜか、といえば、（これは論理学系の証明あるあるなのですが）体系を複雑化すればするほど、その特性を証明する際に必要な分岐が増えてしまうからです。体系は単純だと実用しづらいけれども、理論的にはとても重要なのです。

おまけ1: 高階関数と第一級関数

高階関数と第一級関数というのを聞いたことがあるかもしれません。これらについて私なりのまとめを書いておきます。

高階関数とはWikipedia^[4]には「関数を受け取るか関数を返すかする関数」のこととされています。

ところで「高階」というのは何でしょうか。数学、特に論理学周辺ではこの「高階」という用語は $n$階 を考えたときに $n \ge 2$ や $n \ge 3$ のものを一般に考えたもの、もしくはその階層を全て含めて一個の階層に潰したもの、を指します。

ということは、高階関数について考える前に $n$階関数を考えましょう。

n階関数

まず アトム型 を任意の文字を用いて $A, B, C, N, \mathrm{Bool}, \cdots$ のように考えます。これらは関数ではないとします。これらの階層 $\mathrm{rank}$ を $0$ と定義します。

次に、任意の関数を含む型は次の規則で構成されるように要求します。

• アトム型は型である: $A$
• 型から型への関数型は型である: $T \to T$
• これ以外は型ではない

そして、すべての型に対する階層 $\mathrm{rank}$ を次のように再帰的に定義します

• アトム型は階層0: $\mathrm{rank}(A)$
• 型から型への関数型は引数と返り値のうちより高い階層に1を足したもの: $\mathrm{rank}(T_1 \to T_2) = \max(\mathrm{rank}(T_1), \mathrm{rank}(T_2)) + 1$

そして任意の型 $T$ を持つ値について、 $\mathrm{rank}(T) \ge 1$ ならその数を$n$として $n$階関数であると呼び、 $n \ge 2$ については高階関数と呼ぶことにしましょう。

これで高階関数が定義できました。さらに、上記に書いたように階層を一つに潰すことを指して高階関数と呼ぶこともあるでしょう。

例を考えてみます。

• $\mathrm{rank}(\mathrm{Bool}) = 0$
• $\mathrm{rank}(\mathrm{Bool} \to \mathrm{Bool}) = 1$
  • よって $\mathrm{Bool} \to \mathrm{Bool}$ は1階関数
• $\mathrm{rank}((\mathrm{Bool} \to \mathrm{Bool}) \to \mathrm{Bool}) = 2$
  • よって $(\mathrm{Bool} \to \mathrm{Bool}) \to \mathrm{Bool}$ の値は2階関数、そして高階関数でもある
• $\mathrm{rank}((\mathrm{Bool} \to \mathrm{Bool}) \to (\mathrm{Bool} \to \mathrm{Bool})) = 2$
• $\mathrm{rank}(((\mathrm{Bool} \to \mathrm{Bool}) \to \mathrm{Bool}) \to (\mathrm{Bool}) = 3$
  • よって $((\mathrm{Bool} \to \mathrm{Bool}) \to \mathrm{Bool}) \to (\mathrm{Bool})$ の値は3階関数、そして高階関数でもある

少なくとも、こう考えておくと第一級関数というものが考えやすくなると思います。

厳密な階層がある現実の例

このような階層化は馴染みがないと思うかもしれませんが、例えばTypeScriptの型レベルにおいてはこのような階層化が見られます。

type A = number;
type B = (n: number) => number;
type I<F> = (f: F) => F;
type J<F> = (n: number, f: F) => F;

このとき、 I に I<A> や I<B> のような適用はできても、 I<J> のような適用はできないですよね。これは A や B が1階カインド、 I や J が2階カインドのためです。

カインドというのは "型の型" に相当するものです。

第一級関数

第一級関数^[5]は、第一級オブジェクトとしてとして利用できる関数、というように定義されます。より細かくは、第一級オブジェクトというのは、関数に渡したり、関数から返したり、変数に格納できたりする対象をいいます。

たとえばJSやLua、Pythonにおいては関数は第一級です。一方C言語やRustなどでは直接は代入できず、関数ポインタやトレイトを経由して部分的に実現されます。

逆に第一級オブジェクトではない例を無理やり考えてみると、例えばC++のクラスやRustであればトレイトそのものやstructそのものなどがありますね。

一見、高階関数と第一級関数は同じもの...？となりそうですが、高階関数を上記のように整理すれば、第一級関数により高階関数を実現するのだ、という整理もできそうですよね。次の例も見てみてください。

何階の関数？

ところで、以下のような、受け取った $n$ に対して $n$ 階の関数を返す関数は何階の関数でしょうか？

// 擬似コード
function hyper(n) {
    if (n === 0) return 0;
    else return (() => hyper(n - 1));
}

これは、まず厳密に階層化されている型システムにおいては存在しえませんね。(付け不能)

これを型付け可能な型システムも考えられます。面白くない例として型を一つしか持たない自明な型システムを考えられます。ある意味階層を単純に潰したパターンとも言えるでしょう。もしくはより強力なシステムを利用すればこれはより素直に実現できるでしょう。

第一級関数を許した場合にこのような扱いが難しい例が出てくることもありますが、それにより高階関数が実現できるのだ、というのが私なりの整理です。

カリー化: Haskellとカリー化

Haskellは複数の引数を取る関数を定義できますが、それは実態はカリー化された高階関数と見ることもできます。こうした言語レベルのカリー化の同一視はしばしば見られます。これはすべて、カリー化された高階関数と、多変数関数は同一視できる、という上記の発想をもとにしています。

f :: Int -> Int -> Int -> Int
f a b c = a * b + c

main = print (f 1 2 3)

そもそも型定義が最初からカリー化されたあとの見た目なので自明かもしれませんが、上記のような関数について、途中まで部分適用して別の高階関数にわたすといったことができます。

f :: Int -> Int -> Int -> Int
f a b c = a * b + c

g :: (Int -> Int) -> Int
g h = h (h 100)

main = print (g (f 1 3))

おまけ2: カリー化は指数法則である

おまけなので必須ではないです。数学の背景知識が少し必要です。

指数法則というのは (1) $a^{(b + c)}=a^b \cdot a^c$、 (2) $a^{(b\cdot c)}=(a^b)^c$ , (3) $(a\cdot b)^c = a^c \cdot b^c$ のような指数に関する法則のことです。

ここでは (2) のものがカリー化であるという話をします。

集合論におけるカリー化を考えてみます。

集合 $A$ から $X$ への関数 $A \to X$ 全体の集合というのを考えてみます。

複数の引数

複数の引数はどう扱うべきでしょうか。例えばプログラミング言語でも、返り値が複数ある場合というのは、ペアを利用することがありますね。(TypeScript, Rust, Goなど)
これと同様に、引数も複数あればペアだと捉えましょう。

そして、集合論においてペア全体の集合は直積^[6]として表されます。

直積というのは、TSでいうところのタプル型( [T1, T2] など)です。直積 $X \times Y$ は $X$ のすべてと $Y$ のすべてのありうる組み合わせすべて、を表すものになります。

関数の列挙

２つの要素を持つ集合 $\mathrm{Bool} \coloneqq \{\mathrm{true}, \mathrm{false}\}$ を考えてみます。

$\mathrm{Bool} \to \mathrm{Bool}$ としてはどんな関数が考えられるでしょうか？

例えば、 $\mathrm{f}: \mathrm{Bool} \to \mathrm{Bool}$ であって、次の定義を満たす関数を考えます。

• $\mathrm{f}(\mathrm{false}) = \mathrm{true}$
• $\mathrm{f}(\mathrm{true}) = \mathrm{fales}$

入力が2通りあり、その返り値が2通りずつあるわけですから、 $2^2=4$通り考えられます。実際いかがその全てです。

• $f_1(\mathrm{false})=\mathrm{false}$, $f_1(\mathrm{true})=\mathrm{false}$ (定数関数)
• $f_2(\mathrm{false})=\mathrm{false}$, $f_2(\mathrm{true})=\mathrm{true}$ (恒等関数)
• $f_3(\mathrm{false})=\mathrm{true}$, $f_3(\mathrm{true})=\mathrm{false}$ (Not関数)
• $f_4(\mathrm{false})=\mathrm{true}$, $f_4(\mathrm{true})=\mathrm{true}$ (定数関数)

ラベル付きの直積

関数を提示するというのは、その引数と返り値のペアを列挙することに相当します。関数というのはラベル付きの直積のよう見えます。

$(\mathrm{Bool}から\mathrm{Bool}への関数全体) = \overset{(引数が\mathrm{false}のとき)}{\{\mathrm{false}, \mathrm{true}\}} \times \overset{(引数が\mathrm{true}のとき)}{\{\mathrm{false}, \mathrm{true}\}}$ (仮)

同様に２変数関数の場合は同様に以下のように考えられそうです。

$(\mathrm{Bool} \times \mathrm{Bool} から \mathrm{Bool} への関数全体) =\\\overset{(引数が(\mathrm{false}, \mathrm{false})のとき)}{\{\mathrm{false}, \mathrm{true}\}} \times \overset{(引数が(\mathrm{false}, \mathrm{true})のとき)}{\{\mathrm{false}, \mathrm{true}\}} \times \overset{(引数が(\mathrm{true}, \mathrm{false})のとき)}{\{\mathrm{false}, \mathrm{true}\}} \times \overset{(引数が(\mathrm{true}, \mathrm{true})のとき)}{\{\mathrm{false}, \mathrm{true}\}}$ (仮)

ということは、引数のパターンの数の分の直積を考えることになりそうです。直積は掛け算のような記号を利用しています^[7]から、横に並べたものを指数のように書いてみることが考えられます。

$(\mathrm{Bool}から\mathrm{Bool}への関数全体) = \mathrm{Bool}^2$ (仮)
$(\mathrm{Bool}\times\mathrm{Bool}から\mathrm{Bool}への関数全体) = \mathrm{Bool}^4$ (仮)

しかし、ラベル付きであるということをよりわかりやすくするために、指数部に集合をそのまま置くことをしてみます

$(\mathrm{Bool}から\mathrm{Bool}への関数全体) = \mathrm{Bool}^\mathrm{Bool}$
$(\mathrm{Bool}\times\mathrm{Bool}から\mathrm{Bool}への関数全体) = \mathrm{Bool}^{\mathrm{Bool}\times\mathrm{Bool}}$

そして、これが集合論においてよく見かける関数全体の集合の表記方法です^[8]。

この表記法は次のような性質があるという点でも合理的です。

性質: 任意の有限集合 $A, B$ について $|A^B| = |A|^{|B|}$ (ただし $0^0=1$ とします)

ここで記号 $|X|$ は集合 $X$ の濃度(要素の個数)を指します。

カリー化

さて、この表記において2変数関数のカリー化を見てみます。まず引数が $B \times C$ で返り値が $A$ である関数全体は $A^{B \times C}$ とかけます。

ところで、任意の関数 $f \in A^{B \times C}$ について、 $g(c)(b) = f(b, c)$ となるような関数 $g$ を考えてあげれば、これは $C$ をとって $A^B$ を返す関数ですから、 $(A^B)^C$ の元と考えることができます。 (前項の説明と引数の順を意図的に入れ替えてますが、引数は基本的に順不同なので無視してください)

そうすればこれは $A^{B \times C}$ と $(A^B)^C$ の何らかの同値性を行っていると取れます。一番簡単には一対一対応があるという話ですので、濃度が等しいという話と捉えて頂いても問題ありません。

この意味で、指数法則の集合論版の証明のアイデアの根幹はカリー化である、という意味で、「カリー化とは指数法則だ」、ということでした。

***

なお、ここでは有限集合に限定していましたが、この議論は無限集合の濃度（順序数と基数）にも拡張できます。詳しくはまた別の機会で...

部分適用

部分適用^[9]というのは、部分に適用するということです。本当にそれだけです。

適用というのは関数に引数を与えてその返り値を得ることをいいます。

例えば、 f(5) は関数 f に 5 を適用したものです。

以下の関数を考えます。

const f = (a: number, b: number, c: number) => a ** 2 + b * c;

この内容が意味するところは考えなくても大丈夫です。(実際適当です)

通常の適用というのは f(3, 5, 1) のように行います。

部分適用は複数の引数のうちの一部のみに適用することです。 a または b のみに適用する事を考えてみましょう。

const f_a_is_3 = (b: number, c: number) => 3 ** 2 + b * c;
const f_b_is_5 = (a: number, c: number) => a ** 2 + 5 * c;

部分適用はこれで完了です。 f_a_is_3_applied は f に第一引数 a を 3 として部分適用した関数である、といえます。

console.log(f_a_is_3(5, 1)); // 14
console.log(f_a_is_5(3, 1)); // 14

ところで、 a もしくは b に任意の x を部分適用できるように抽象化するにはどうしたら良いでしょうか？これは高階関数を使うことでTypeScriptでは実現できます。

const f_a_is_x = (x: number) => (b: number, c: number) => x ** 2 + b * c;
const f_b_is_x = (x: number) => (a: number, c: number) => a ** 2 + x * c;

// 以下のように書き換えられる
const f_a_is_3 = f_a_is_x(3);
const f_b_is_5 = f_b_is_x(5);

f_a_is_x は上記で書いたカリー化に似ていますね。実際、引数が2つしかない関数においてはこれはカリー化と一致します。

しかし、あくまでもカリー化になったものは部分適用の値を一般化したものであり、部分適用とは f から f_a_is_3 を得ることです。 f から f_a_is_x を得ることではないです。

部分適用は、本当に、部分に適用する、それだけです。なお、すべての引数に適用することを対比して完全適用と呼ぶこともあります。

JSにおける部分適用

JavaScriptにおいて部分適用をするために Function.prototype.bind()^[10]が紹介されることがあります。これは実際に以下のように利用することができます。

const f_a_is_3 = f.bind(null, 3);
console.log(f_a_is_3(5, 1)); // 14

これがおすすめされているのを見かけることもありますが、よほどパフォーマンス等の問題や制約でもない限り特におすすめだとは思っていません。
この書き方だと f_a_is_3 が any になるのが一つと、先頭から連続した部分にしか部分適用できないというのがもう一点です。

おまけ3: 部分適用のカリー化はカリー化である

おまけなので必須ではないです。こちらはTypeScriptのパラメータ多相だけわかれば問題ないです。

ここでは2変数のカリー化の一般化を考えます。カリー化したい2変数関数を受け取り、そのカリー化された関数を返す関数を考えます。

const curry = <X, Y, Z>(f: (x: X, y: Y) => Z): (x: X) => (y: Y) => Z => {
  return (x) => (y) => f(x, y);
};

[TypeScript Playground]

このカリー化をする関数は以下のように使えます。

const f = (x: number, y: string) => x + y.length;
const f_curried = curry(f);
console.log(f_curried(2)('hello')); // 7

これで const f_curried: (x: number) => (y: string) => number という型がついています。

次に対象の関数と第一引数を受け取り、部分適用した結果を返す関数を考えます。

const p_app = <X, Y, Z>(f: (x: X, y: Y) => Z, x: X): (y: Y) => Z => {
  return (y) => f(x, y);
};

[TypeScript Playground]

使い方は以下のようになります。

const f = (x: number, y: string) => x + y.length;
const add_2_to_length = p_app(f, 2);
console.log(add_2_to_length('hello')); // 7

部分適用することで、与えられた文字列の長さに2を足す、部分適用された関数 add_2_to_length を得ることができました。

ところで p_app もまた2変数関数なので、これを curry を利用してカリー化する事ができます。するとこれは curry と同じ2変数関数をカリー化する関数です。

const curry = <X, Y, Z>(f: (x: X, y: Y) => Z): (x: X) => (y: Y) => Z => {
  return (x) => (y) => f(x, y);
};
const p_app = <X, Y, Z>(f: (x: X, y: Y) => Z, x: X): (y: Y) => Z => {
  return (y) => f(x, y);
};

const curry2 = curry(p_app);

const f = (x: number, y: string) => x + y.length;
const f_curried2 = curry2(f);
console.log(f_curried2(2)('hello')); // 7

[TypeScript Playground]

つまり、カリー化の差を無視する世界にとって、カリー化と部分適用はやっぱり同じだったわけですね！

......(^_^;)

はい、すみません、これは詭弁です。あくまでも、特定の抽象化されたカリー化と 第一引数のみへ の部分適用は、カリー化の差を除いて一致するというだけですね。

そもそもなんですけどね、カリー化を同一視したら、どちらも恒等関数^[11]です。

＊＊＊＊＊＊

異論や専門家の方のご意見もお待ちしておりますので、ぜひコメントをお願いいたします。

脚注

1. Wikipedia [日本語: カリー化] [英語: Currying]

2. ところでチューリングマシンは無限のメモリを仮定します。しかし現実には無限のメモリはきっとないでしょう。そのうえでプログラミング言語はチューリング完全と言えるのか、という疑問が湧くかもしれません。なにかをチューリング完全と呼ぶとき、メモリが無限にあることや、それに耐えるような仕様の変更が少なからずある、理想化されているというのが前提にあります。意外と明示的にこれが述べられていることは少ないでしょうから、これを知らないと混乱しかねません。

3. そして、このラムダ計算もまたチューリング完全になります。もし興味があれば私が書いたZenn記事TypeScriptから構造体を奪って、関数だけでまた構造体を得るまでの道のり (チャーチ・エンコーディング)はきっと面白いと思います

4. [日本語: 高階関数] [英語: Higher-order function]

5. Wikipedia [英語: First-class function]

6. Wikipedia [日本語: 直積集合]

7. そしていくつかの面で直積は積のような振る舞いを見せます。だからこそ直積という名前と掛け算の記号を借りているのでしょう。

8. より正確な定義は一般に "関係" を用いて行われます。

9. Wikipedia [英語: Partial application]

10. MDN: Function.prototype.bind()

11. 恒等関数: 受け取った値をそのまま返す関数のこと。Identity Function.