メタ関数のカリー化

序文

メタ関数をカリー化したい、と誰もが一度は思うはずです。
(え、思わない?そうですか…)
なので早速やっていきます。

メタ関数の作成

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

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

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

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<U>::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<U>::typecurry_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<U> のように書けるようになりました。

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

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;

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

ラムダ計算

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

// λ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);

蛇足

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


  1. ここではペアノ公理に従います

ブログ、始動…?

取り敢えず、はてなブログとやらに登録してブログを書いてみることにした。

と言っても、かなり不定期更新になるだろう。

 

競技プログラミングの参加記及び精進録、またプログラミングの話題を綴ることが多いと思うが、日常的な話も挟んでいきたい。とはいえ、日常的に何か話すことがあるのかと言われるとその自信は無いのだが。

 

文体はその日の気分によって変わる可能性が大いにあるので、気にしないで欲しい。兎に角今回はこの文体の気分だ。ツイッターが主な生息地である以上其処での呟きを拡張したものとして使われる可能性もあるのだ、いちいち気にしてはきりが無いだろう。

 

ひとまず、最初の投稿はこの様な具合だろうか。ではまた。