プログラマーのための圏論を読みます。

数学的に厳密にはやってくれないだろうから、そっちはお気持ちが分かればOKとする。他の知識との紐づけができたら最高です。

あと、「私なりの深ぼり」を重視する。

# 1 圏：合成の本質

• 圏は、複数の対象とそれらをつなぐ射で構成される
• 「圏の本質は合成」らしい
  • 確かに、可換図式がすべての土台になりそうだし、言わんとしていることはわかるか...？
• パイプって関数の合成と思って良いんだ
• Haskellでは次のように合成を表現できる

f :: A -> B
g :: B -> C
g . f

シンプルで嬉しいね。

圏において「合成」が満たすべき性質

• 合成は結合的である
• 任意の対象 $A$ について、合成の単位元となる射 $\mathrm{id}_{A}$ が1つ存在する
  • このとき、任意の射 $f:A \to B$ に対して $\mathrm{id}_{B} \circ f = f$ かつ $f \circ \mathrm{id}_{A} = f$ が成り立つ

# 1.4 課題

1. 恒等関数を、好きな言語で（それがたまたまHaskellなら2番目に好きな言語で）できるだけうまく実装せよ。
2. 合成関数を好きな言語で実装せよ。このメソッドは2つの関数を引数として受け取り、その合成である関数を返す。
3. 合成関数が恒等関数と整合しているかテストするプログラムを作成せよ。
4. ワールドワイドウェブは、何らかの意味で圏だろうか？　リンクは射だろうか？
5. Facebookは人を対象とし友達関係を射とする圏だろうか？
6. 有向グラフが圏になるのはどのような場合だろうか？

# 2 型と関数

• 型とは値の集合
  • Bool = {True, False}
  • Char = {a, b, ...}
• Haskellの型と関数の圏は $\mathbf{Set}$ ではなく $\mathbf{Hask}$ と表される
  • Haskellにおいて関数は有限時間内に値を定めることができない場合があるため区別する
    • 停止性問題
  • とは言っても $\mathbf{Set}$ と思っておいて概ね大丈夫！らしい
• プログラム意味論
  • 操作的意味論
    • 記号に対して、操作によって意味を与える
    • CやC++はこっちをベースに設計されている
  • 表示的意味論
    • 記号に対して、対応する数学的な意味を対応付けることで意味を与える
    • Haskellはこっちをベースに設計されている

int fact(int n) {
    int i;
    int result = 1;
    for (i = 2; i <= n; ++i)
        result *= i;
    return result;
}

fact n = product [1..n]

• 関数の副作用にモナドという「意味」を与えることで、複雑な処理も表示的意味論で扱えるようになる

• Haskellにおける「引数をとらない関数」
  • Void は空集合を表すので、absurd :: Void -> a は、定義はできるが実行はできない
    • 空集合の元を用意することはできないため
  • () は単集合を表す
    • () は unit と呼ぶ
    • C++の void はこっちに近い
      • 例えば、inf f44() {return 44;} は f44() と実行できるが、「インスタンスが1つしか存在しないダミー値」を引数に取る、と捉えられる

f44 :: () -> Integer
f44 () = 44

• unit を返す関数も unit と呼ぶ

unit :: a -> ()
unit _ = ()

• Haskellにおいて、Bool は二元集合である
  • Bool を返す関数は 述語 と呼ばれる
    • これ、一階述語論理とセットかも

data Bool = True | False

• boolがC++ではintに変換される

暗黙の型変換に頼るのはバグの温床であり、高品質なプログラムは実装の詳細からは独立して機能すべきだ

なるほどねえ。

# 2.7 課題

1. 好きな言語で高階関数（または関数オブジェクト）memoizeを定義せよ。この関数は純粋関数fを引数として受け取り、次の点を除いてfと同じ動作をする関数を返す。すなわち、memoizeの結果として返される関数は、もとの関数を引数ごとに1回だけ呼び出し、結果を内部に格納し、その後は同じ引数で呼び出されるたびに格納済みの結果を返す。メモ化 (memoize) された関数ともとの関数は、パフォーマンスを見れば区別できる。たとえば、評価に時間のかかる関数のメモ化を試みること。最初に呼び出したときは結果を待つ必要があるが、同じ引数を使って次に呼び出したときは結果をすぐ得られるだろう。

2. 乱数を生成するためにあなたが普段使う標準ライブラリー関数をメモ化してみよ。うまくいくか？

3. ほとんどの乱数発生器はシードで初期化できる。シードを受け取り、そのシードで乱数発生器を呼び出し、結果を返す関数を実装せよ。その関数をメモ化せよ。うまくいくか？

4. 以下のC++関数のうち、純粋なのはどれか？　これらをメモ化してみて、何度も呼び出したときに何が起こるかを、メモ化した場合とそうでない場合について観察せよ。

   1. 本文中で例示した階乗関数。
   Copy

   std::getchar()
   

   Copy

   bool f() {
       std::cout << "Hello!" << std::endl;
       return true;
   }
   

   Copy

   int f(int x) {
       static int y = 0;
       y += x;
       return y;
   }
   

5. Boolを取りBoolを返す関数は何種類あるか？　それらすべてを自分で実装できるか？

6. Void型、() (unit) 型、Bool型だけを対象とする圏の図を描け。ただし、射についてはこれらの型の間のすべての可能な関数に対応するようにせよ。射には関数名のラベルを付けよ。

# 3 圏のさまざま

圏の定義だけ、正確にまとめます。

• 圏 $\mathcal{C}$ は、次のデータからなる
  • 対象の集まり
  • 任意の対象 $A, B$ について、$A$ から $B$ への射の集まり $\mathrm{Hom}_{\mathcal{C}}(A, B)$
  • 任意の射 $f:A \to B$ と $g:B \to C$ について、それらを合成した射 $g \circ f:A \to C$
  • 任意の対象 $A$ について、恒等射 $\mathrm{id}_{A}:A \to A$
• ただし、合成と恒等射は次の性質を満たす
  • 結合律：$(h \circ g) \circ f = h \circ (g \circ f)$
  • 単位律：任意の射 $f:A \to B$ について、$\mathrm{id}_{B} \circ f = f$ かつ $f \circ \mathrm{id}_{A} = f$

• 空圏
  • 対象も射も0個の圏
• 有向グラフから生成される自由圏
  • 任意の有向グラフに対して、次のような圏を構成することができる
    • すべての頂点を対象とし、
    • すべてのパスを射とし、
    • パスの連結を合成とし、
    • 長さ 0 のパスが恒等射になる
• 順序集合
  • 任意の前順序集合 $(X,\le)$ から、次のような圏を作れる
    • 対象は $X$ の元
    • $x \le y$ のとき、$x$ から $y$ への射がちょうど1つ存在する
    • $x \nleq y$ のとき、$x$ から $y$ への射は存在しない
  • ただし、
    • 反射律 $x \le x$ が恒等射 $\mathrm{id}_{x}:x \to x$ に対応する
    • 推移律 $x \le y,\; y \le z \Longrightarrow x \le z$ が射の合成に対応する
  • 前順序集合から作られる圏では、任意の2対象の間の射は高々1つしかない。
    • このような圏は細い圏 (thin category) と呼ばれる。
  • 前順序集合からなる圏 $\mathcal{C}$ について、
    • $\mathrm{Hom}_{\mathcal{C}}(a,b)$ は空集合 or 単集合
    • $\mathrm{Hom}_{\mathcal{C}}(a,a)$ は単集合
  • 前順序集合では循環が起こり得るが
  • 半順序集合では循環は起こり得ない
    • 循環を作る射があるとすると、それは恒等射になる

モノイドの話。

Haskellにおけるモノイドは

class Monoid m where
    mempty  :: m
    mappend :: m -> m -> m

と表される。ただし、単位元の存在と結合法則を表現する方法はない。これを保証するのはプログラマの責任。

class Semigroup m => Monoid m where
    mempty :: m

こっちは「String が Monoid のインスタンスである」という宣言。

instance Monoid String where
    mempty = ""
    mappend = (++)

"Hello" ++ "world!"
(++) "Hello" "world!"

Haskellでは関数の等しさを次の2つのように表現できる。

mappend = (++)
mappend s1 s2 = (++) s1 s2

プログラムとしては同値だが、数学的に解釈すると、

• 前者は $\mathbf{Hask}$ 圏の射の等しさを考えていて、
  • 「これらの射は等しい」
• 後者は集合論まで降りてきて、外延的等価性を考えている
  • 「すべての引数に対して、これらの射は同じ結果を返す」

と思える。

C++では、次の書き方が一番「モノイドに近い」らしい。

template<typename T>
struct mempty;

template<typename T>
T mappend(T, T) = delete;

template<typename M>
concept Monoid = requires (M m) {
    { mempty<M>::value() } -> std::same_as<M>;
    { mappend(m, m) } -> std::same_as<M>;
};

template<typename T>
struct mempty;

template<typename T>
T mappend(T, T) = delete;

template<>
struct mempty<std::string> {
    static std::string value() { return ""; }
};

template<>
std::string mappend(std::string s1, std::string s2) {
    return s1 + s2;
}

• ただ一つの対象を持つ圏はモノイドである
  • 具体的には、
    • その対象から自分自身への射を元とし
    • 合成を演算
    • 恒等射を単位元とするモノイドになる

# 気になったところを見ていく

• 圏論における「=」って?
  • それを定義するのは圏論の仕事ではない
  • 例えば、
    • $\mathbf{Set}$ における射の「=」は、関数の「=」なので、外延的に等価なら「=」である
    • 前順序集合で構成した圏において、2つの対象間には唯一つだけ射があるため、「=」の満たすべき反射律により、2つの射の始点と終点が同じならそれらは「=」である
  • では、圏の定義における射の間の「=」はなに?
    • $\mathrm{Hom}_{\mathcal{C}}(A, B)$ を集合としているので、一般の集合について使われる「=」と捉える
    • さらには、集合論の背景にある一階述語論理における「=」まで辿れる
      • 厳密には一階述語論理の意味論#等号によって定められている、と思える
      • が、個人的には二階述語論理を仮定して $x=y\Longleftrightarrow(\forall P P(x)\Longleftrightarrow P(y))$ と定義してしまうのがわかりやすい
        • 二階述語論理は数学では基本的に仮定しないらしい
        • 強い道具だけど扱いづらさもある (理解してない)
          • 妥当な式をすべて機械的に列挙できない
          • ゲーテルの完全性定理が成立しない
          • 証明体系だけでは意味論的妥当性を完全には捉えられない
  • 同値関係としてオリジナルの「＝」を定めるのは？
    • 商集合を考えればOK！
      • 圏の定義の $=$ を同値関係 $\sim$ で書き換えてしまうと、$\forall x,y((x\sim y\Longleftrightarrow(\forall P(P(x)\Longleftrightarrow P(y)))))$ を確認しなくてはならなくなる (同値関係には代入原理がないため)
      • 商集合を考えるとそれを回避できるのはなぜ？
        • 同値類間の「＝」に置き換えるからか
• 「可換性」ってどこからでてくる?
  • 「=」により自然に
• 圏論的モノイドって、なんのためにそんなものを考えるの？
  • 嬉しそうな主張雑に考えてみる
    • 「任意の圏はモノイドを包含する」
      • したがって「圏はモノイドの一般化」？
    • (全然思いつかなかった)
  • 周辺を見てみる
    • 「モノイド準同型はそのまま圏論的モノイド間の関手になる」
    • 「モノイド作用はそのまま圏論的モノイドから $\mathbf{Set}$ への関手になる」
• 自由圏の普遍性について
  • 自由圏は普遍性によって特徴づけられる
• 🧠そもそも普遍性って何が嬉しいの？
  • おおざっぱに下2つな気がした
    • 構成でなく性質による定義
    • 道具として優秀

# 3.6 課題

1. 以下から自由圏を生成せよ。
   1. 1つのノードを持ち、辺のないグラフ
   2. 1つのノードと1つの（有向）辺を持つグラフ（ヒント：この辺は自身と合成できる）
   3. 2つのノードと、それらの間の（有向）辺を1つ持つグラフ
   4. 1つのノードと、アルファベットa, b, c … zでマークされた26個の（有向）辺を持つグラフ
2. 以下はどんな順序だろうか？
   1. 複数の集合を要素とする集合と、その上の包含関係。なお、AがBに包含されるとは、Aの全要素がBの要素でもあることを指す。
   2. C++の型の集合とその上の部分型関係。なお、T1がT2の部分型であるとは、T2へのポインターを期待する関数にT1をコンパイルエラーを発生させずに渡せることを指す。
3. Boolが2つの値TrueとFalseの集合であることを踏まえて、それが2つの演算子&& (AND) と|| (OR) のそれぞれについて（集合論的）モノイドをなすことを示せ。
4. AND演算子を伴うBoolモノイドを圏として表せ。射と合成の規則を列挙せよ。
5. モジュロ3加算をモノイドの圏として表せ。

# 4 クライスリ圏

これは純粋関数ではない。

string logger;

bool negate(bool b) {
     logger += "Not so! ";
     return !b;
}

こうすると純粋関数になる。

pair<bool, string> negate(bool b, string logger) {
     return make_pair(!b, logger + "Not so! ");
}

これだと引数が増えて嫌なのでもっと良い方法がほしい。
できればこうしたい。

pair<bool, string> negate(bool b) {
     return make_pair(!b, "Not so! ");
}

どうすればできるか。

まず戻り値を「装飾」する。ログも含めて1つの型と捉えるってことですね。

template<typename A>
using Writer = pair<A, string>;

Writer<string> toUpper(string s) {
    string result;
    int (*toupperp)(int) = &toupper;
    transform(begin(s), end(s), back_inserter(result), toupperp);
    return make_pair(result, "toUpper ");
}

Writer<vector<string>> toWords(string s) {
    return make_pair(words(s), "toWords ");
}

だが、この2つの toUpper と toWords の合成を考えると、

Writer<vector<string>> process(string s) {
    auto p1 = toUpper(s);
    auto p2 = toWords(p1.first);
    return make_pair(p2.first, p1.second + p2.second);
}

とても煩雑。よくないね！

# 4.1 Writer圏

出発点としては、通常通り、型と関数の圏を考える。が、戻り値を「装飾」したので、射は再定義する必要がある。

例としてこの isEven を考える。

pair<bool, string> isEven(int n) {
     return make_pair(n % 2 == 0, "isEven ");
}

実際には違うわけだが、int -> bool とみなす。

したがって、例えば、次のような bool -> bool と合成できるはずである。

pair<bool, string> negate(bool b) {
     return make_pair(!b, "Not so! ");
}

素直に考えると、合成はこうなる。

pair<bool, string> isOdd(int n) {
    pair<bool, string> p1 = isEven(n);
    pair<bool, string> p2 = negate(p1.first);
    return make_pair(p2.first, p1.second + p2.second);
}

これを抽象化して、次のように書ける。

template<typename A, typename B, typename C>
function<Writer<C>(A)> compose(function<Writer<B>(A)> m1,
                               function<Writer<C>(B)> m2)
{
    return [m1, m2](A x) {
        auto p1 = m1(x);
        auto p2 = m2(p1.first);
        return make_pair(p2.first, p1.second + p2.second);
    };
}

[キャプチャ](引数) {
    処理
}

恒等射は当然こう。

template<typename A>
Writer<A> identity(A x) {
    return make_pair(x, "");
}

当然、string に限らず、単位元と演算が定義されている型 (すなわちモノイド) なら同じ事ができる。

# 4.2 HaskellにおけるWriter

Haskellだともっとシンプルに書けるよね〜という話。

# 4.3 クライスリ圏

以上で定義した圏は、クライスリ圏の一例らしい。

# 4.4 課題

引数が取り得る値のすべてに対して定義されているわけではない関数は、部分関数と呼ばれる。これは実際には数学的な意味での関数ではないので、標準的な圏の枠組みには合わない。しかし、装飾された型optionalを返す関数でなら表せる。

Copy

template<typename A> class optional {
    bool _isValid;
    A    _value;
public:
    optional()    : _isValid(false) {}
    optional(A v) : _isValid(true), _value(v) {}
    bool isValid() const { return _isValid; }
    A value() const { return _value; }
};

たとえば、以下は装飾された関数safe_rootの実装だ。

Copy

optional<double> safe_root(double x) {
    if (x >= 0) return optional<double>{sqrt(x)};
    else return optional<double>{};
}

課題は以下のとおりだ。

1. 部分関数についてクライスリ圏を構築せよ（合成と恒等射を定義せよ）。
2. 引数が0でない場合にその逆数を返す装飾された関数safe_reciprocalを実装せよ。
3. 関数safe_rootとsafe_reciprocalを合成して、可能なすべての場合にsqrt(1/x)を計算するsafe_root_reciprocalを実装せよ。

以下が与えられているとする。

template<typename A> class optional {
    bool _isValid;
    A    _value;
public:
    optional()    : _isValid(false) {}
    optional(A v) : _isValid(true), _value(v) {}
    bool isValid() const { return _isValid; }
    A value() const { return _value; }
};


optional<double> safe_root(double x) {
    if (x >= 0) return optional<double>{sqrt(x)};
    else return optional<double>{};
}

1

template<typename A, typename B, typename C>
function<optional<C>(A)> compose(function<optional<B>(A)> f,
                               function<optional<C>(B)> g)
{
    return [f, g](A x) {
        auto res = f(x);
        if (res.isValid()) {
            return g(res.value());
        } else {
            return optional<C>{};
        }
    };
}

template<typename A>
optional<A> identity(A x) {
    return optional<A>{x};
}

2

optional<double> safe_reciprocal(double x)
{
    if (x == 0) return optional<double>{};
    else return optional<double> {1.0 / x};
}

3

optional<double> safe_root_reciprocal(double x) {
    return compose<double, double, double>(safe_reciprocal, safe_root)(x);
}