C++ でカリー化関数を書いてみる(2変数限定)

概要

Scala の勉強中に、 Scala では2変数関数のカリー化関数が下記のようにコンパクトに書けることを知った。

curry.scala

/** カリー化 f(a, b) --> f(a)(b) */
def curry[A, B, C] (f: (A, B) => C) : A => (B => C) = {
	(a : A) => ( (b : B) => f(a, b) )
}

/** アンカリー化 f(a)(b) --> f(a, b) */
def uncurry[A, B, C](f : A => (B => C) ) : (A, B) => C = {
	(a : A, b : B) => f(a)(b)
}

短く高階関数が書けることに感動し、これと同じようなものを c++11 で書けるかどうか試してみた。
まず最初に最終的に出来上がったコードを載せ、そのあと出来上がるまでの過程を書いていく。

最終コード

curry.cpp

#include <iostream>
#include <sstream>
#include <functional>

using namespace std;

/** カリー化 f(a, b) --> f(a)(b) */
template <typename A, typename B, typename C>
function < function < C(B) >(A) > curry(function<C(A, B)>& f)
{
    return [&](A& a) -> function < C(B) > {
        return [=](B& b) -> C {
            return f(a, b);
        };
    };
}

/** アンカリー化 f(a)(b) --> f(a, b) */
template <typename A, typename B, typename C>
function< C(A, B) > uncurry(function < function < C(B) >(A) >& f)
{
    return [&](A& a, B& b) -> C {
        return f(a)(b);
    };
}

int main(int argc, char* argv[])
{
    // テスト用関数。 2つの文字列を連結する
    function< string(string, string) > func = [](string a, string b) {
	return a + b;
    };

    // 普通に使用
    cout << func("Hello, ", "World!") << endl;

    // カリー化して使用
    auto func2 = curry(func);
    cout << func2("Hello, ")("World!") << endl;

    // カリー化されたものをさらにアンカリー化して使用
    auto func3 = uncurry(func2);
    cout << func3("Hello, ", "World!") << endl;

    return 0;
}

出力

Hello, World!
Hello, World!
Hello, World!

解説

Wikipedia
カリー化 (currying, カリー化された=curried) とは、複数の引数をとる関数を、引数が「もとの関数の最初の引数」で戻り値が「もとの関数の残りの引数を取り結果を返す関数」であるような関数にすること（あるいはその関数のこと）である。

要するに f(A, B, C, D, ...) -> Z のような複数の引数を持つ関数を受け取ったとき、 f = g(A) -> ( h(B, C, D, ...) -> Z ) のような形に分解して、f の第一引数 A を部分適用可能にするような関数を作るための関数である。
今回は２変数関数のカリー化関数を作るので、入力される関数は (A, B) -> C 「A, B 型の変数（or 関数）を受け取ったらC型の結果を返すような関数」 で、出力は A -> (B -> C) 「A を受け取ったら、B->C の関数を返す」 ような関数。

宣言部分

c++ では関数を関数の引数として渡すためには std::function ないし boost::function を使うのが便利。今回は std::function を使う。関数名は curry とする。

入力の型

curry の入力である 「A, B 型の変数（or 関数）を受け取ったらC型の結果を返すような関数」 は std::function を使うと

function< C(A, B) >

と書ける。

出力の型

curry の出力である 「A を受け取ったら、B->C の関数を返す関数」 は、 std::function を使うと

function < function < C(B) >(A)>

と書ける。入力に比べてちょっと複雑だが、 A を受け取ったら、 function < C(B) > を出力する function(関数オブジェクト)と読むと意味が分かりやすい。

以上から、 curry 関数の宣言は下記のようになる。

template <typename A, typename B, typename C>
function < function < C(B) >(A) > curry( function< C(A, B) >& f );

実装部分

宣言部分が出来たので実装を書いていく。
カリー化できるためには、最低限下記２つのことが出来る必要がある。

1. オリジナルの関数を、 A, B を受け取るまで記憶する
2. 第一引数パラメータ A を、 B が適用されるまで記憶する

struct を使って実装すると下のようになる。

CurryImpl.h

/** A -> (B -> C) 型の関数オブジェクト */
template <typename A, typename B, typename C>
struct CurryImpl {

	// コンストラクタでオリジナルの関数をキャプチャ
	CurryImpl(function<C(A, B)>& f) : mFunc(f) {}

	/** B -> C 型の関数オブジェクトをリターンする */
	function< C(B) > operator () (A& a) {
		return CurryImpl2(mFunc, a);
	}

	function<C(A, B)> mFunc;
	
	/** B -> C 型の関数オブジェクト*/
	struct CurryImpl2 {

		// コンストラクタでオリジナル関数と第一引数をキャプチャ
		CurryImpl2(function<C(A, B)>& f, A& a) : mFunc(f), mA(a) {}

		C operator () (B& b) {
			return mFunc(mA, b);
		}
		
		function<C(A, B)> mFunc;
		A mA;
	};
};

• CurryImpl は function< function< C(B) >(A) > 形式の関数オブジェクトで、コンストラクタでオリジナルの関数 f をコピーする。
• CurryImpl に A 型の変数 a を渡すと function< C(B) > 形式の関数オブジェクト CurryImpl2 をリターンする。
• CurryImpl2 は CurryImpl から受け取った f, a を保持する。
• CuuryImpl2 に B 型の変数 b を渡すと、保持していた f,a を使って f(a, b) を実行し、結果（C型）をリターンする。

ここで、 CurryImpl, CurryImpl2 は f(a,b) の適用までに生み出されるテンポラリな型であるため名前がある必要はない。
そこでラムダを使って CurryImpl, CurryImpl2 を書くと下のようになる。

template <typename A, typename B, typename C>
std::function < std::function < C(B) >(A) > curry(std::function<C(A, B)>& f)
{
    return [&](A& a) -> std::function < C(B) > {
        return [=](B& b) -> C {
            return f(a, b);
        };
    };
}

アンカリー化関数は同じような手順で作成でき、カリー化より簡単なので省略する。

わからなかったところ

コピーキャプチャ or 参照キャプチャ？

今回、 curry の実装は (B -> C) の関数オブジェクトを作るところで f と a の情報をコピーするように実装したが、コピーでなく参照を保持する形でも一応コンパイル可能だった。

template <typename A, typename B, typename C>
std::function < std::function < C(B) >(A) > curry(std::function<C(A, B)>& f)
{
    return [&](A& a) -> std::function < C(B) > {
        return [&](B& b) -> C {
            return f(a, b);
        };
    };
}

だがそれで上記の main 関数を実行すると、 f(a, b) を実行する行で、 f, a の参照が無効になっていてランタイムエラーで落ちてしまった。この場合オリジナルの関数 func はスコープ内で生きているため有効なポインタを取ってこれると思われるのだが、うまい実装方法がわかなかった。