🪓

メタ関数のカリー化

2021/03/03に公開

C++

tech

序文

メタ関数をカリー化したい、と誰もが一度は思うはず^[1]です。
なので早速やっていきます。

メタ関数の作成

まずやりたい事を明確にします。カリー化というぐらいですから、以下のように書きたいですね。

template <class T, class U> struct X {};
using curried = curry<X>::type;
static_assert(std::is_same<curried<T><U>, X<T, U>>::value);

しかし curried<T> などという書き方は出来ませんから、 curried::ident<T>::ident のように識別子を挟んでやる必要があります。
取り敢えずこれを作ることを目標にします。

では出力されて欲しい型を考えてみます。
先程のようにしたければ素直に

struct curried {
  template <class T>
  struct impl {
    template <class U>
    using ident = X<T, U>;
  };
  template <class T>
  using ident = impl<T>;
};

という型があれば良いですが、上記のままだと引数が増えた場合

template <class T1, class T2, class T3> struct Y {};

struct curried {
  template <class T1>
  struct impl1 {
  	template <class T2>
  	struct impl2 {
  	  template <class T3>
  	  using ident = Y<T1, T2, T3>;
  	};
  	template <class T2>
  	using ident = impl2<T2>;
  };
  template <class T>
  using ident = impl1<T>;
};

のようになり、生成しようとすると impl が衝突して厄介なことになりそうです。
なので一旦以下のような構造を考えます。

struct curried {
  using type = struct {
    template <class T>
    struct ident {
      using type = struct {
        template <class U>
        struct ident {
          using type = X<T, U>;
        };
      };
    };
  };
};

それぞれの階層に type を挟むことで衝突は避けれましたが、使おうとすると curried::type::ident<T>::type::ident::type のようになってしまいます。
しかし単純な再帰的構造で実装は楽そうですので、一度これで実装します。

template <class...> using void_t = void;

template <class, template <class...> class T, class... Ts>
struct curried {
  using type = struct {
    template <class U>
    using ident = curried<void, T, Ts..., U>;
  };
};

template <template <class...> class T, class... Ts>
struct curried<void_t<T<Ts...>>, T, Ts...>  {
  using type = T<Ts...>;
};

template <template <class...> class T>
struct curry { using type = curried<void, T>; };

template <template <class...> class T> 
using curry_t = typename curry<T>::type;

仕組みとしては、テンプレートテンプレートパラメータの T に対しパラメータパック Ts... を与えて実体化可能ならば適用し、不可能ならばパラメータパックに型を追加するための ident を提供する、といったものになります。

ここで、 curry_t<X>::type::ident<T>::type::ident::type の curry_t<X>::type 以降は ident<T>::type の繰り返しなので、curry に手を加えて

template <template <class...> class T>
struct curry { using type = typename curried<void, T>::type; };

さらに ident<T>::type に当たる部分をまとめて apply<T> とでも名付けてしまえば

template <class, template <class...> class T, class... Ts>
struct curried {
  using type = struct {
    template <class U>
    using apply = typename curried<void, T, Ts..., U>::type;
  };
};

晴れて curry_t<X>::apply<T>::apply のように書けるようになりました。

後は適宜ヘルパーメタ関数を用意してしまえば

template <class T, class... Us>
struct apply_to {};

template <class T>
struct apply_to<T> {
  using type = T;
};

template <class T, class U>
struct apply_to<T, U> {
  using type = typename T::template apply<U>;
};

template <class T, class U1, class U2, class... Us>
struct apply_to<T, U1, U2, Us...>
    : apply_to<typename apply_to<T, U1>::type, U2, Us...> {};

template <class T, class... Us>
using apply_to_t = typename apply_to<T, Us...>::type;

だいぶ使いやすくなると思います。

ラムダ計算

流石に作っただけでは味気ないので、何かやってみましょう。
手頃なものとしてはラムダ計算でしょうか。
まずは自然数を定義してみましょう。
もちろん自然数はゼロから^[2]ですので、はじめにゼロを作ります。

// λfx.x
template <class F, class X> using zero = X;
using _0 = curry_t<zero>;

そして succ 関数も作れば

// λnfx.f(nfx)
template <class N, class F, class X>
using succ_t = apply_to_t<F, apply_to_t<N, F, X>>;
using succ_c = curry_t<succ_t>;

自然数が作れるようになりました。

using _1 = succ_c::apply<_0>;
using _2 = succ_c::apply<_1>;
using _3 = succ_c::apply<_2>;
using _4 = succ_c::apply<_3>;
using _5 = succ_c::apply<_4>;

利便性のため integral_constant への変換も作っておきます。

template <int X> using int_t = std::integral_constant<int, X>;
template <class T> struct inc : int_t<T::value + 1> {};
using inc_c = curry_t<inc>;
template <class T> using to_num = apply_to_t<T, inc_c, int_t<0>>;

add mul pow を作れば、

template <class L, class R, class F, class X>
using add_t = apply_to_t<L, F, apply_to_t<R, F, X>>;
using add_c = curry_t<add_t>;

template <class L, class R, class F>
using mul_t = apply_to_t<L, apply_to_t<R, F>>;
using mul_c = curry_t<mul_t>;

template <class L, class R>
using pow_t = apply_to_t<R, L>;
using pow_c = curry_t<pow_t>;

後は思う存分ラムダ計算を楽しめます。

static_assert(to_num<apply_to_t<add_c, _2, _3>>::value == 5);

using f = mul_c::apply<_2>;
static_assert(to_num<f::apply<_3>>::value == 6);
static_assert(to_num<f::apply<_5>>::value == 10);

template <class F, class X, class Y>
using flip_t = apply_to_t<F, Y, X>;
using flip_c = curry_t<flip_t>;

using g = apply_to_t<flip_c, pow_c, _3>;
static_assert(to_num<g::apply<_2>>::value == 8);
static_assert(to_num<g::apply<_3>>::value == 27);

蛇足

技術系記事の執筆は初めてなので拙いものとなりましたがご容赦ください。
マサカリお待ちしています。

※この記事は、はてなブログに投稿した記事の移植版となります。

脚注

え？思わない？そうですか… ↩︎
ここではペアノ公理に従います ↩︎

GitHubで編集を提案

序文

メタ関数の作成

ラムダ計算

蛇足

Discussion