猫でも杓子でもわかる Functor in C++0x

関手というのがどうもよくわからず。

ということなので、釣り記事を書こうと思います。
Haskell とか使ってる人って、これぐらい全部わかってるイメージがありますし、矢張り釣り針は大きいほうがいいので、C++ で説明してみようと思います。C++ の関数型表記だとちょっとイマイチなので C++0x を使います。
ガンガン嘘をつくので突っ込んでください。

関手というのは、めちゃくちゃ簡単にいうと「圏をとり圏を返す関数」です。あっ、みなさんが大好きな圏がしょっぱなから出てきましたね！モナドなう〜。
でも圏、カテゴリってなんだろう？

圏というのは、一言でいうと「対象とその射からなる構造」です*1。
対象、射って何だろう？ということなんですけど…

突然ですが bool ってご存知ですか？勿論そりゃご存知でしょうけれども、少し説明してみます。
C++ には bool という型があって、この型の値としては true と false があります。
更に C++ には std::logical_not というクラステンプレートがあって、そこにパラメタを与えてやった std::logical_not() は auto (bool) -> bool *2 な関数オブジェクトです。std::logical_not()(true) == false, std::logical_not()(false) == true です。auto (bool) -> bool な関数オブジェクトの例としては、他にも std::bind(std::logical_or(), true, _1) や std::bind(std::logical_and(), false, _1) みたいなものも考えられますね。最初の例は、true と false でそれぞれ行き来できますけど、後の二つは一方からもう一方へしかいけない、という違いがあります。

// std::logical_not<bool>() の世界 行ったりきたりできる
true ←→ false
// std::bind(std::logical_or<bool>(), true, _1) の世界 一方通行　
true ← false
// std::bind(std::logical_and<bool>(), false, _1) の世界 一方通行　
true → false

そんなことは分かってるよ、と言われるとは思いますが。これは重要なファクターです。*3

「○○っていうのは、これこれこういう値があって、それに適用できる一引数関数としてこういうのがあるよ、その場合、それぞれの値間の関係はこうなるよ」ということを上では詳しく説明したわけですけれど、実はこれが「対象とその射」の説明になっています。
対象というのは、C++ でいうところの「値の集合」つまり「型」のことです。
射というのは「値から値への対応を表すものの集合」つまり上のグラフの矢印です。グラフを描くのは関数なので、結局のところ射とは「関数（オブジェクト）」のことです。
ということで圏とは、C++ でいうところ「型」と「関数」であらわされる物、です。はい、圏わかりました！これで圏論の基礎が読めます！*4

ということで関手です。「圏をとり圏を返す関数」です。しかし圏をとって圏を返すっていうのはよく意味が分かりませんね。

C++ には std::iterator_traits というクラステンプレートがあります。これは、イテレータ型のさまざまな（中略）です。
というわけで、クラステンプレートを型の特性を調べるための手段として利用することがある C++ ですけれども、じゃあもうクラステンプレートは「型を扱うの関数」ということにしちゃいましょう。

template <typename Arg> struct Function; // 私は Arg をとって型 Function<Arg> を返す関数です

うーん……

template <typename T> struct F; // 私は型 T をとって型 F<T> を返す関数です

うーん……？

template <typename T> struct F;

アッすごいぞ、これはもうどこからどうみても関数ですね！

それと C++ には std::map というコンテナをマッピングする関数オブジェクトとして振舞うテンプレートクラスが…ないんですけど…まあ書くことはできます。書きっぱなしコードなので、コンパイル通らなかったらごめんなさい。

template <template <typename E/*lement*/> class C/*ontainer*/> // Allocator がない、と騒ぐエキスパートの皆様、お願いですから少し静かにしていてください
struct map {
  template <typename T>
  auto operator()(std::function<auto (T) -> T>, C<T>) -> C<T>;
};

まあ適当に定義されてると仮定して、とりあえず使ってみましょう。

std::vector<bool> vb = { true, false, true, false };
std::vector<bool> ret = map<vector>()(std::logical_not<bool>(), vb); // { false, true, false, true }

うーん map()(std::logical_not(), ...) とか毎回書いてられませんね、ということで bind しちゃうかもしれません。

std::function<auto (vector<bool>) -> vector<bool>> f = std::bind(map<vector>(), std::logical_not<bool>(), _1);

毎回 bind するのもめんどくさい！と、こういうコードを書くかもしれません。

template <template <typename E> class C>
struct map {
  template <typename T>
  auto operator()(std::function<auto (T) -> T>) -> std::function<auto (C<T>) -> C<T>>; // const なんてつけませんよ、サンプルコードですからね
};

色々やってるうちに auto (T) -> T な関数を auto (C) -> C(T) な関数にしちゃう関数オブジェクトテンプレートができてしまいました。

気持ち悪いコードばかりでうんざりしてると思いますが、もうちょっとです。ここまでに出てきた二つのコードをまとめます。

// 型 T をとり型 F<T> を返す関数、としてのクラステンプレート
template <typename T> struct F;

// auto (T) -> T な関数をとり auto (C<T>) -> C(T) な関数を返す関数オブジェクトテンプレート
template <template <typename E> class C>
struct map {
  template <typename T>
  auto operator()(std::function<auto (T) -> T>) -> std::function<auto (C<T>) -> C<T>>;
};

何かかぶってる部分ありますね。まとめちゃいましょう

// 型 T をとり型 F<T> を返す関数、としてのクラステンプレート
template <template <typename E> class C>
struct map {
  // auto (T) -> T な関数をとり auto (C<T>) -> C(T) な関数を返す関数テンプレート
  template <typename T>
  auto operator()(std::function<auto (T) -> T>) -> std::function<auto (C<T>) -> C<T>>;

なわけですけど、そうでした、圏の話をしているんでした。型＝対象、関数＝射です。

// 対象をとり対象を返す関数
template <template <typename E> class C>
struct map {
  // 射をとり射を返す関数
  template <typename T>
  auto operator()(std::function<auto (T) -> T>) -> std::function<auto (C<T>) -> C<T>>;

オヤオヤ、これはもしかして…「対象をとり対象を返す関数」と、「射をとり射を返す関数」、この二つをあわせれば、「圏を取り圏を返す関数」ができるんじゃないか！？

はいできました、ということで C++ 的には関手というのは、

型パラメタを一つ持つクラステンプレートをパラメタに持ち、型 T をパラメタに持ち、引数に auto (T) -> T な関数を取り、auto (C) -> な関数を返す関数テンプレートをメンバにもつクラステンプレート

のことです！とってもわかりやすい！やりましたね！

これで皆さんわかった気分になって*5、Haskell の Functor 型クラスを見たりするわけですけど、

class Functor f where
  fmap :: (a -> b) -> f a -> f b

何か…違う…違うぞ…！おい！コノヤロウ！型パラメタの数が違うじゃねえか！と、皆さんお怒りになる。

実は「対象というのは、C++ でいうところの「値の集合」つまり「型」のことです」とか書きましたが、これは説明を簡単にするための嘘でした。実際には、特定の型の値の集合である必要はないです。更に、射の集合を現す関数の、引数型と返値型も、一致していなくてもいいです。一致してないとダメなんて言ってませんけどね。引数型と返値型が、それぞれ射の「入口」と「出口」を十分に表せればそれで十分、ということです。「入口」「出口」って何だ？ということなんですが。
そこでミルキィホームズです。ミルキィホームズを知らない、という人はちょっと圏論について学ぶには早すぎると思うので、出直してきてください。今ならニコニコ動画で 808 円も払えば全 12 話を視聴することができます！とってもお値打ち価格です。
ということでミルキィホームズの四人をあらわす型を書いてみましょう。

struct MH {
  static MH sharo, nero, elly, cordelia;
private:
  MH() { };
};
MH MH::sharo, MH::nero, MH::elly, MH::cordelia;

ミルキィホームズの四人が、それぞれかわいいかどうかを返す関数は以下のようになるでしょう。

auto kawaii(MH) -> bool { return true; }

ここで MH と kawaii で定義される構造について考えてみます。
まず型としては、MH の他に、関数の返値型である bool があります。ということで登場人物が増えて、値としては、　

sharo, nero, elly, cordelia, true, false

が出てくることになるわけです。更に、射としては、

sharo -----> true    false
              ^
nero ---------+
              |
elly ---------+
              |
cordelia -----+

のような false さんが若干かわいそうなグラフで描かれる、四本の射が存在します。*6
ここで「入口」つまり矢印のお尻のほうをよくよく見ると、実は bool 型の値は出てこない。逆に「出口」つまり矢印の頭のほうを見ると、今度は MH 型の値は出てこない。「入口」というのは関数の引数型に、「出口」というのは関数の返値型に対応していて、それらが異なることもまああるんだなーっていう話でした。

それで、ペドさんがシャロいことを表す関数も考えてみると、

auto sharoi(MH mh) -> bool { return mh == MH::sharo; }

その operator== はどこからきた、って突っ込みはなしでお願いします…グラフを書いてみると、

sharo -----> true    false
                       ^
nero ------------------+
                       |
elly ------------------+
                       |
cordelia --------------+

今度の結果には false さんもしてやったりです。でも大丈夫、true さんシャロ厨*7だから win-win の関係です。

うーん、何かもう正直どうでもよくなってきましたね…

そんなわけでちょっと見直してみましょう。

template <template <typename E> class C>
struct map {
  template <typename T>
  auto operator()(std::function<auto (T) -> T>) -> std::function<auto (C<T>) -> C<T>>;

別に返値型と引数型は一致してなくてもいい、ということでパラメタ増やしてみます。

template <template <typename E> class C>
struct map {
  template <typename T, typename U>
  auto operator()(std::function<auto (T) -> U>) -> std::function<auto (C<T>) -> C<U>>;

class Functor f where
  fmap :: (a -> b) -> f a -> f b

完全に一致…！

まあいい加減定義してみましょうか。boost::optional 使います。

struct map<boost::optional> {
  template <typename T, typename U>
  auto operator()(std::function<auto (T) -> U> f) -> std::function<auto (boost::optional<T>) -> boost::optional<U>> {
    std::function<auto (boost::optional<T>) -> boost::optional<U>> ret = [f](boost::optional<T> v) {
      return v ? f(v.get()) : boost::optional<U>();
    }
    return ret;
  }
};

Haskell の Maybe というやつですね。何も面白くない。

そんなわけで関手というのは C++ 的には

型パラメタを一つ持つクラステンプレートをパラメタに持ち、型 T, U をパラメタに持ち、引数に auto (T) -> U な関数を取り、auto (C) -> C<U> な関数を返す関数テンプレートをメンバにもつクラステンプレート

のこと、ということになりました。

飽きたのでまとめ

ミルキィホームズ BD/DVD 第二巻が 2/25 日に発売になります。シャロさんのねんどろいどぷちも付くんですよ〜吸いましょう！
まあ普通に一つずつ組み立てていく形で説明するほうがわかりやすいと思いました。

*1:identity と composition は今回はスルーします、使わないので。domain, codomain とかそれに類する何かは、グラフ出してるのでそれで勘弁してください

*2:bool (bool) です

*3:重ファクといいます

*4:うそです

*5:るといいなあ？

*6:ここでも identity は矢張りスルーです

*7:ボクが決めました