iOSDC Japan 2018 「圏論とSwiftへの応用」発表スライドメモ

この記事は、先日の **[iOSDC Japan 2018](https://iosdc.jp/2018/)** で発表した **[「圏論とSwiftへの応用」](https://speakerdeck.com/inamiy/iosdc-japan-1)** のスライドメモです。

来月10月16日に開催される **[プログラマのための圏論勉強会 - connpass](https://cat4pg.connpass.com/event/100728/)** の予習用の入門資料としてお使いください。
（さらに勉強したい方は、 [圏論のオススメ勉強法（プログラマ向け）](https://qiita.com/inamiy/items/922d4220bf407efa2dab) を合わせて読むと、キャッチアップしやすいと思います）

## スライド・動画・補足記事

- Slide: [圏論とSwiftへの応用 / iOSDC Japan 2018 - Speaker Deck](https://speakerdeck.com/inamiy/iosdc-japan-1)
- 動画: https://www.youtube.com/watch?v=zvrgfsDfxf8
- 関連記事: 
    - [圏論のオススメ勉強法（プログラマ向け）](https://qiita.com/inamiy/items/922d4220bf407efa2dab)
    - [iOSDC Japan 2018 で発表した「圏論とSwiftへの応用」の補足 - Qiita](https://qiita.com/inamiy/items/c4e85f22273e98b8db26)

## スライドメモ

<img width="800" alt="category-p01.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/c7b54482-ea4c-f01e-d10e-8b2b44582bcf.png">

それでは発表を始めます。
本日のテーマは **「圏論」** です。
英語では、 **Category Theory** といいます。

---

<img width="800" alt="category-p05.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/b494eeba-9d15-105c-024c-ca926a33f096.png">

圏論を「1枚の絵」で表すとしたら、このような図になります。
**丸を書いて、矢印を書く。** たったこれだけ。簡単そうでしょう？

---

<img width="800" alt="category-p06.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/0cd17ea2-78dc-37a5-87b5-febd68c54e0f.png">

圏論を言葉で説明するとこうなります。
まず **「点」と「矢印」を使った学問** であること。
それは、 **数学におけるFoundation.framework** のようなものだと思ってください。
Foundationがないと、他のフレームワークが動かないですよね？それくらい重要な分野です。
その裏付けとして、圏論の **応用範囲は非常に広い** です。
例えば、数学や論理学、計算機科学（プログラミング含む）、理論物理学など、ありとあらゆる科学分野で使われています。
また、圏論の素晴らしい点として、 **数学の知識が無くても学べます**。
そして圏論は、 **関数型プログラミング** において大活躍します。
今日はそれを見ていきます。

---

<img width="800" alt="category-p07.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/b5b31bd8-e351-f469-397b-57595206fe70.png">

ちなみに、圏論の話は、 **型システム** にも密接に関係してきます。
例えば、**再帰的な代数的データ型** や **全称量化（ジェネリクス）**、 **存在量化（Swiftプロトコル、existential container）** といった、Swiftでおなじみの言語機能は圏論からも学べますし、さらには多相関数を引数として使える **高ランク多相**、型コンストラクタを型引数として使える **高カインド多相**、 値に依存する型が作れる **依存型** といった、より高度な「型レベルプログラミング」の概念にまで発展していきます。

---

<img width="800" alt="category-p08.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/037bf446-ca2b-1645-8d3f-cc73817ba5eb.png">

つまり、 圏論を学ぶことで **「型」をより深く理解する** ことができ、 **現状のSwiftの理解** に加えて、 **将来の可能性も見いだせる** ということになります。

iOSエンジニアの私たちはこれまで、「C言語」「Objective-C」「Swift」と学んできたわけですが、 **究極のゴールはずばり「圏論」** です。
ぜひ、今日の発表の通して、皆さんの中にある「究極生命体」が誕生してもらえればと思います。

---

<img width="800" alt="category-p09.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/c4a6033a-d4f9-fb76-98db-bc5fd6050907.png">

ここで1つお断りとして、現在のSwift 4.2の言語仕様で圏論を語るには、どうしても足りない機能があります。
なので今日は、 **「疑似Swift」** を使って説明します。
所々、シンタックスが変わっている点がありますが、その辺は、目を瞑ってもらえれば幸いです。

---

<img width="800" alt="category-p10.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/34f7092d-1140-d04e-4bc6-f33640172b94.png">

というわけで、まず最初に、 **圏の定義** から見ていきましょう。

---

<img width="800" alt="category-p11.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/77237702-efc0-dd77-bee3-d95dab6c3cb3.png">

まず、先ほどの図式の丸を「点」と見なして、A、B、Cとラベル付けします。
これらの点のことを **「対象 (object)」** と呼びます。

---

<img width="800" alt="category-p12.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/b4793f9a-353b-3e12-4419-e62210e4e7a9.png">

それから、対象の間を「矢印」が張り巡っていきます。
これらの矢印のことを **「射 (arrow, morphism)」** と呼びます。
これら **対象と射をグルーピング** したものを **圏** といいます。

---

<img width="800" alt="category-p13.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/c9c83670-5950-985f-da50-2021b25d2e83.png">

圏の例としては、 **プログラミングにおける「型」** があります。
**点として「型」** を当てはめると、実は **矢印は「関数」** に相当します。
「型」と「関数」で構成される圏のことを **「型の圏」** といいます。

---

<img width="800" alt="category-p14.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/e3b59bcc-0463-2588-0888-6d62f42d0d9e.png">

試しに、 `String` / `Int` / `Bool` を当てはめて、それらの間の関数を考えてみましょう。
思いつく限り、いろいろなパターンがあると思います。
そうすると、このような図を書くことができます。
なんとなく、圏のイメージが湧いたでしょうか？

---

<img width="800" alt="category-p15.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/1a7e9deb-693e-d7d5-1886-4bc8a6f06ccf.png">

それでは前に戻って、 **「圏」が満たすべき性質（定義）** について簡単に紹介します。

---

<img width="800" alt="category-p16.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/d9b722e0-4bf7-8556-4138-f1684ac862d3.png">

まず、すべての点について、**「恒等射」** とよばれる、自分自身へと向かう矢印が存在します。
この関数は、「呼び出したところで何もしない」関数になります。

---

<img width="800" alt="category-p17.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/76a97056-7f0f-26bf-edad-a960e48cac03.png">

次に、矢印は、A → B → C と連続で続く場合に、 **「合成」** することができます。
この図の場合、`f`、`g`と続いたら、AからCは `g ⚬ f` という矢印を作ることができます。
ここで、 ⚬ は **合成演算子** です。

---

<img width="800" alt="category-p18.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/fa06b2bb-2247-f96a-301f-62e06b016476.png">

例えば、型の圏で、2つの関数 `count` と `isEven` があったとしたら、それらを合成して、 `isEven ⚬ count` と1つの関数にまとめることができます。

---

<img width="800" alt="category-p19.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/cfd67e65-06bc-bb1b-10d5-df3d68edb008.png">

ここで、合成に関する重要な規則があります。
例えば、黒の矢印 `f`、`g`、`h` の3つがあった場合、まず2つを合成したオレンジの矢印ができて・・・

---

<img width="800" alt="category-p20.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/5585f662-783e-e01c-72cb-f8ef9260631d.png">

それから「オレンジと残りの黒い矢印を合成」すると、「赤の矢印」ができます。
これは、 右回りと左回りの2パターンの作り方があって、それらは共に等しいです。
つまり、 **`f`、`g`、`h` の合成の順序はどちらから先にやっても良い** ということです。
これを **「結合律」** と呼びます。

---

<img width="800" alt="category-p21.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/3309391e-7455-d10b-8c69-d97b4ea229be.png">

以上をまとめると、圏の定義はこのようになります。
他にも、 **「domain / codomain」** という用語があり、矢印の「開始地点」と「終了地点」という意味です。

---

<img width="800" alt="category-p22.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/6a74a4dc-f28b-f9e2-8ef9-e74558c22fd4.png">

これをSwiftで表現すると、こうなります。

- まず、恒等射に関しては、 **`func id`** というものが作れます。
これは、 **ジェネリックな`A` を渡したら`A` がそのまま返ってくる、何も計算しない関数** です。
- もうひとつ、合成に関しては、 **`func ⚬`** という記号をここでは使います。 **2つの連続する関数を受け取ったら、内部でそれらを順番に呼ぶ関数** です。

圏の定義については、まずはこの2つの関数を覚えておけば合格です。

---

<img width="800" alt="category-p23.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/d6ec351e-ea21-4b39-a906-9bc6e74c20a2.png">

次に **「関手」** を見ていきましょう。
英語では **「Functor」** といいます。

---

<img width="800" alt="category-p24.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/72a78c62-5d34-1ecb-d195-f69e7dbb73dc.png">

「関手」を大雑把に説明すると、 **「左の圏」を丸ごと対象として、中身の形をそのまま維持しながら「右の圏」へと写す「射」** になります。（上の図のオレンジの矢印のことです）

---

<img width="800" alt="category-p25.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/3c92ee86-10c3-acf4-5ce2-b70cedc353eb.png">

つまり、内部の対象がそのままの形で写り・・・

---

<img width="800" alt="category-p26.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/f96c2d24-7d6a-6eed-624d-5b67c61afe13.png">

さらに、射がそのままの形で写ることで、 **内部の形（構造）がそのまま維持** されています。
これが「関手」の定義です。

---

<img width="800" alt="category-p27.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/ef8dbc4b-514b-219b-d218-775539b0eb76.png">

例えば、型の圏で考えるなら、 **「配列 `Array`」は関手の1つ** です。
左側のプリミティブな型に対し、その配列を作ると、右側の関数は、`map` を使って写すことができます。

---

<img width="800" alt="category-p28.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/a57e30ff-bea9-02b6-141e-e29f9352831e.png">

ちなみに、圏論での一般的な表現は、このようになります。
先ほど **`Array` や `map` と書いていたところが、`F` に置き換わっています** 。

ここで注目してほしいのは、右側の黒い矢印の `F(g ⚬ f)` です。

---

<img width="800" alt="category-p29.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/86103def-ce30-e863-0baf-83a8aca142a8.png">

実は、右側の圏だけに着目すると `F(f)` と `F(g)` という矢印がすでに存在しています。
つまり、これらを合成すると、 `F(g) ⚬ F(f)` となって、やはり黒の矢印が得られます。

---

<img width="800" alt="category-p30.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/188ef96e-5634-7aa9-1237-95c5b1b4d82c.png">

関手の定義は、 **`F(g ⚬ f)` と `F(g) ⚬ F(f)`を等しいものとして扱います** 。

---

<img width="800" alt="category-p31.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/e9e3049e-842d-6459-7e75-f7a5f7d3342b.png">

というわけで、関手についておさらいすると、こうなります。
関手は基本的に、 **圏から圏へのマッピングで、形を保つもの** と覚えてください。

---

<img width="800" alt="category-p32.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/ff6a8b0b-313f-6b43-a84c-e305781ddd12.png">

では試しに、関手をSwiftで書くと、どうなるでしょう？
残念ながら、現在のSwiftは、言語仕様上、関手を作ることはできません。
が、今は疑似Swiftの世界なので、何でもありです。
なので、試しにこんなprotocolを書いてみました。

注目してほしいのは、 `static func map` です。
これはスタティックメソッドですが、 **第一引数に `self` をおくことで、インスタンスメソッドとしても使えるというルール** にします。
そうすると、`Array` を `Functor` に適合させれば、配列の `map` は、下の使用例のコードのように「中身を入れ替える」操作になります。

---

<img width="800" alt="category-p33.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/663cba2f-6083-e8b5-bedc-94895727ba83.png">

この例から言えることは、2つ：

- まず、 **関手とは「`map` ができる」こと**
- そして `map`とは、**「コンテナを変えずに中身を変える」** こと

ちなみに、これはこれで正しいのですが、いわゆる **pointwiseな考え方** です。
実はもっと素晴らしい、関数型的な見方があるので、紹介したいと思います。

---

<img width="800" alt="category-p34.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/1069fd2d-c0f6-6c97-ed98-6ec2d253db95.png">

先ほど、`static func map` の第一引数に `self` をおく話をしました。
が、今度は下のprotocolのように、 **`self` を第二引数においてみます**。
これは、引数順序を入れ替えただけなので、同じ結果になります。
そして、これをさらにカリー化します。
すると、別の形の `static func map` が得られますが、型から分かるように、 **「`map` は `A -> B` の関数から `F<A> -> F<B>` の関数への変換」** を表しています。
これを **関数持ち上げ (リフト、lifting)** と言います。

---

<img width="800" alt="category-p35.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/1c1ac77a-a301-b459-86f5-6ee831db2285.png">

これを図式で説明すると、まさに先ほどの通りです。
ああ、単に **`f` が `F(f)` に写っただけ** だね、と。たった、それだけのことです。
が、 **とても重要なものの見方** なので、ぜひ覚えていって下さい。

---

<img width="800" alt="category-p36.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/b0993b5c-95b5-7c0d-1272-93589af0fb04.png">

この考え方は、登場人物が関数（つまり射）しか存在しないので、**「射が中心の、 pointfree な考え方」** といいます。

---

<img width="800" alt="category-p37.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/e9d34f64-bc66-07a7-faa2-89b33c392cd1.png">

さて話を戻して、先ほど `F(g ⚬ f)` は `F(g) ⚬ F(f)` に等しい、という話をしましたが・・・

---

<img width="800" alt="category-p38.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/d5cdeede-b347-92ac-301a-ac0c75bdf903.png">

これをSwiftで説明すると、こうなります。
すなわち、 **関数合成してから `map` を1回行う** のと、 **個々に `map` を呼んでから関数合成する** ことは同じです。
ちなみに、 **「 `map` を2回行う」ということは、2回 for文を回しているようなもので、中間表現を作ることなので、無駄なコストが発生** しています。
なので、`map`を1回にするだけの方が、パフォーマンス改善につながりますし、こういうのは **最適化できる余地** があります。
なので、 **コンパイラ方面に興味のある人** にとっても、圏論は非常に有意義な学問なんですね。

---

<img width="800" alt="category-p39.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/2bfaa5ee-e94b-f94d-72bc-aa9905153873.png">

ここで余談として、今まで2つの圏を区別して考えてきましたが、
実際のところはどちらもSwiftの型なので、 **1つの圏としてまとめて扱うことができます** 。

---

<img width="800" alt="category-p40.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/ecba445e-e49c-3d7a-aba1-2ee8d6c1362c.png">

そうすると、このような図になります。
関手 `Array` は自分自身の圏に向かう射になります。これを **「自己関手」** と呼びます。
実は、 **私たちが普段 Functor と呼んでいたものは、自己関手 (Endofunctor) のこと** だったんですね。

---

<img width="800" alt="category-p41.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/91697d6c-8fce-608b-57dc-04aae8e6f5fd.png">

では続きまして、 **「自然変換」** について説明します。
英語で、Natural Transformationといいます。

---

<img width="800" alt="category-p42.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/0ea08db5-d8a0-e46d-27c0-66c624cf1662.png">

「自然変換」は、先ほど話した関手が **同じ方向に2つあるパターン** です。
**関手`F`と`G`があって、それぞれ左の圏の構造を右に反映している** のが分かります （黄色と緑の点線）。

---

<img width="800" alt="category-p43.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/2d719649-4418-f5c7-9e83-1254cc3fc267.png">

ここで、自然変換の定義は、 **本来矢印である2つの関手を対象とみなして、「その間にさらに伸びる射」** になります。
これはつまり、 **関手の間にさらに関係性がある（矢印の間にさらに矢印がある）** ことを意味します。
この自然変換`α`は、写った先の圏では、「複数のジェネリックな射」として現れます。
そう、実は **自然変換とはジェネリック関数** のことなんですね。
別名、**多相関数** とも言います。

---

<img width="800" alt="category-p44.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/a768451f-4b1a-3c47-c29d-2ef8614d3851.png">

ここで注目してほしいのは、 **関手によってできた黒の矢印** と、 **自然変換によってできた赤の矢印** が組み合わさって、四角形ができていることです。
実はこの四角形は、右回りの合成でも、左回りの合成でも、どちらも等しくなります。
これを **可換図式** といいます。

---

<img width="800" alt="category-p45.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/c4e24791-279f-99f2-8089-0f5d220eddae.png">

というわけで、今述べた自然変換の定義がこちらです。

---

<img width="800" alt="category-p46.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/e636301d-b849-abfb-6a29-27904243804b.png">

この意味をSwiftで説明すると、こうなります。
まず **自然変換の関数の型は `F<A> -> G<A>` で、中身を変えずにコンテナを変える「ジェネリック関数」** を表します。
そして、これを `func alpha` とおくと、実は、 **先に`map` してから自然変換 `alpha` を計算しても、先に自然変換 `alpha` してから `map` しても同じ** であることが言えます。

---

<img width="800" alt="category-p47.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/72eaab33-63cc-220e-b0ae-da076df88686.png">

試しに、配列の最初の要素を取ってくる `Array.first` を例にとってみましょう。
これは **`Array` から `Optional` へのジェネリック関数** なので、まさに自然変換の形です （NOTE: `Optional` も関手の1つ）。
そして、先ほどの可換式に当てはめると、このように書けます。
つまり、 **map で文字列変換してから「最初の要素を取り出し」** ても、 **「最初の要素を取り出し」てから `map` で文字列変換しても結果が変わらない** ということです。
普段、プログラミングしていたら当たり前のように見える話ですが、これをきちんと形式化したものが自然変換になります。
ここで重要なのは、 どちらのフローで計算しても結果が変わらないのだとしたら、 **計算量が少ない方が良い** に決まっていますよね？
この場合ですと、「最初の要素を取り出し」てから `map` した方が早いので、ここでも **コンパイラの最適化の余地がある** といえます。

---

<img width="800" alt="category-p48.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/1a500337-4718-728c-3075-dc25c5712339.png">

続いて **「米田の補題」** です。
英語では Yoneda Lemma といいます。

---

<img width="800" alt="category-p49.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/6bca880b-932b-401f-4a53-32fbde768c2a.png">

「米田の補題」は、先ほどの自然変換の話において、 **「Hom関手」と呼ばれる「関数の集合の関手」** というものを考えることで、導くことができます。
ただ、それを説明するために30分の発表では短すぎるので、雰囲気だけお伝えします。

参考： [iOSDC Japan 2018 で発表した「圏論とSwiftへの応用」の補足 - 米田の補題について - Qiita](https://qiita.com/inamiy/items/c4e85f22273e98b8db26#%E7%B1%B3%E7%94%B0%E3%81%AE%E8%A3%9C%E9%A1%8C%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6)

---

<img width="800" alt="category-p50.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/c834eaff-db0b-8acf-7cd2-077fbb1dcb5f.png">

まず、右の「集合の圏」にあるこの青い集合。
通常は、空っぽの集合（値が入っていない）の場合もありうるのですが、「Hom関手」を使う場合は特別で、この場合だと **$\mathrm{id}_A$ という恒等射が値が必ず存在します** 。

---

<img width="800" alt="category-p51.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/40fcdaf5-8e23-5c46-5168-2710ce19f7ca.png">

すると、右上の赤い集合には $f$ が必ずいて・・・

---

<img width="800" alt="category-p52.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/a71c9f38-8fa5-d552-8037-1926321b88cb.png">

そして 自然変換`α` を通して、下の集合にも値が入ってきます。
つまり、 **すべての集合に、値が必ず存在します。**

---

<img width="800" alt="category-p53.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/dd5399ab-ed86-6cca-7b17-814b14a18e78.png">

これの意味は、まず **自然変換 $\alpha$ が決まれば、必然的に $\alpha_A$ の値が求まります** し・・・

---

<img width="800" alt="category-p54.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/e3208db5-4df8-0366-085f-493ab3dbe2f3.png">

逆に **$\alpha_A$ が決まると、可換図式から、$\alpha_B$、$\alpha_C$ ...も決まって、結果的に自然変換 $\alpha$ そのものが決まります**。

---

<img width="800" alt="category-p55.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/d8fd0c10-fc90-fcd8-d03e-76b919c0eba3.png">

これを **米田の補題** と言い、式で表すとこのように書けます。
上の式はHom関手の意味を知らないと分かりにくいですが、型で表現した下の式は、もう少し簡単になります。
これの意味するところは、 **左辺の「自然変換（つまりジェネリック関数）」の型** と、 **右辺の「値」の型** が1:1の関係になる、ということです。
**関数と値が同じになる** ・・・なんだか、すごくないですか？

---

<img width="800" alt="category-p56.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/7a0ff674-b535-10ec-91c9-0385033e690d.png">

実際に、Swiftで例をお見せします。
例えば、`let fa` という「値」と、それを「ジェネリック関数」で包んだ `func closure`、つまりクロージャーがあったとしたら、 **両者は同じものとみなせます** 。
これはつまり、 **「同型」の関係** です。
「同型」の意味は、お互いに **相互変換が可能** ということです。

---

<img width="800" alt="category-p57.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/5b82d66f-c04d-e20d-66ae-e60d0677e66e.png">

実際に、相互変換するコードをSwiftで書くと、このようになります
上の関数 `faToClosure` は、「値から自然変換」に変換。
下の関数 `closureToFa` は、「自然変換から値」に逆変換します。
実装方法に関しては、この書き方以外にありません。

ちなみに下の `closureToFa` は、引数にジェネリック関数を受け取っていますが、これは **ランク2多相** と呼ばれるもので、残念ながらまだSwiftには実装されていません。

---

<img width="800" alt="category-p58.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/76df5a4f-0cac-99ae-39db-ff409c282791.png">

一応、参考までに、 **「同型」の話** についてもっと知りたい方は、以前、私が発表した「代数的データ型」の資料がありますので、機会があったらぜひチェックしてみてください。

参考： [Algebraic Data Type in Swift - Speaker Deck](https://speakerdeck.com/inamiy/algebraic-data-type-in-swift)

---

<img width="800" alt="category-p59.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/3aed88ca-c712-16e2-10d6-c07d37167883.png">

では、この米田の補題から、どういったことが分かるでしょうか？
一つの例として、**「CPS変換」**があります。
CPSというのは **Continuation Passing Style** の略で、 **「継続」と呼ばれるコールバック形式の書き方** だと思ってください。
米田の補題では、 **`F(T) = T` とおくと継続** が得られ、 **`F(T) = X -> T` とおくと、米田埋め込み** と言われる **「CPS変換」** が得られます。
後者は、 `∀B. (A -> B) -> (X -> B` と `X -> A` が同型（相互変換が可能）なので、「右辺から左辺に変換する関数」として、実際にSwiftのコードで書いてみると、下のような `func cpsTransform` が書けます。

---

<img width="800" alt="category-p60.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/eadc2d61-2d9f-528f-2b92-89e411b6139f.png">

それでは、この「CPS変換」は一体何の役に立つのでしょうか？
実は、 **「末尾再帰の最適化」** の話に関係してきます。
例えば、上のコードのように、階乗を計算する `func factorial`があったとします。
これは末尾再帰の形ではないので、`n`の数が大きくなるほど、スタックを食いつぶして、最終的にオーバーフローでクラッシュします。
ここで、先ほどの CPS変換 `cpsTransform` を使うと、あら不思議、 **継続を使った、末尾再帰のコードに勝手に最適化** されました。
ちなみにSwiftコンパイラは、裏側でこのような末尾再帰最適化を自動で行っているので、普段のiOS開発で意識することはほとんどないでしょう。

---

<img width="800" alt="category-p61.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/fee782b8-2a3f-c39f-1512-3b721a293dc7.png">

・・・というわけで、米田の補題はここまで。
それでは本日のメインディッシュである **「随伴」** を見ていきます。
英語で Adjunctionといいます。

随伴は、圏論だけでなく、Swiftプログラミングにおいてもとても重要な概念です。

---

<img width="800" alt="category-p62.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/f6b96fb9-8a7a-feae-f823-172d090f417d.png">

図で説明すると、このようになります。
まず2つの圏があり、関手`F` と`G` がそれぞれ **逆方向** に伸びています。
そして、何か `C` と `D` という対象があったら、`F(C)`、`U(D)` に写したりできます。

---

<img width="800" alt="category-p63.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/7b88a9a2-cad8-14c2-59fd-9f8c03c4fb10.png">

ここで、青と赤の対象の間の **ピンク色の「矢印の集合」** に注目すると・・・

---

<img width="800" alt="category-p64.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/9425a619-e6f4-886d-67f1-e7c301bd86e3.png">

随伴の定義は、 **「射の集合」が「1:1の関係」** になることです。
つまり、**2つの圏が同型（や同値）ではなく、それを弱めた「射の集合のみが同型」** になります。
同型であることは、つまり **「左側の射の集合」から「右側の射の集合」に変換する関数 `leftAdjunct` と、逆変換 `rightAdjunct` の2つの関数を定義する** ことができます。

---

<img width="800" alt="category-p65.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/3880f6e4-d609-8804-b89b-4ff823d7ab6e.png">

随伴の関係を式で書くと、このようになります。
ちなみに **⊣ は随伴の記号** です。
`F`、`U`をそれぞれ、 **左随伴関手、右随伴関手** と呼びます。

---

<img width="800" alt="category-p66.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/d177a8cf-e43c-cef8-3e89-03b1f747f549.png">

随伴の（直接的・間接的な）関係は、実に様々なパターンがあります。
例えば、

- **足し算と掛け算**が、対角関手を経て、間接的につながっている
- （この後話す） **タプル（積）と関数（指数対象）**
- **存在量化（プロトコル）と全称量化（ジェネリクス）** の間接的な関係
- **自由関手と忘却関手**

などがあります。

---

<img width="800" alt="category-p67.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/47aa9a26-8317-ba2c-322f-838d960cb0f4.png">

それでは、随伴を疑似Swiftを使って表してみましょう。
随伴を定義するには、**leftAdjunct と `rightAdjunct` が必要** でした。
なので、このようなprotocolの形で書けると思います。

---

<img width="800" alt="category-p68.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/44b4c1ad-d39f-4e9a-62de-50d06a6d89bf.png">

試しに、**左随伴にタプル、右随伴に関数型**を使うSwiftの例を上げます。
`typealias` で `Tuple<A, B>` と `Func<A, B>` を用意します。

---

<img width="800" alt="category-p69.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/5245fa44-4009-8af8-ce77-e756cb48b16b.png">

まず、関手であることを示すために、`protocol Functor` を採用します。
すると、このような形で書くことができます。

---

<img width="800" alt="category-p70.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/5ee87475-f8f4-ff99-fe32-e30ef522510e.png">

それから `protocol Adjunction` を採用すると、このようになります。
ここで注目してほしいのは、 **leftAdjunct と `rightAdjunct` の中身** です。

- `leftAdjunct` は、**`c` を引数に、 `a` を引数にそれぞれ受け取り、タプルにしてから関数 `f` に適用**している
- `rightAdjunct` は、**タプルを引数に受け取ってから、個々に分解して、関数 `f` にそれらを部分適用** している

つまり、 **個々の引数をタプルにまとめたり、逆にタプルを個々の引数に分解している** わけです。
・・・これらのメソッド、何かに見覚えがありませんか？

---

<img width="800" alt="category-p71.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/221ce4c4-0202-6c64-c145-d009a5a1ceb2.png">

そう、 **カリー化** ですね。
見覚えがあるかもしれませんが、 `func curry` と `func uncurry` はこのように書けます。

参考： https://github.com/thoughtbot/Curry

---

<img width="800" alt="category-p72.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/336fa1d2-e5f7-d5ab-3258-f6b047a164a0.png">

というわけで、タプルと関数型の随伴の場合、 **`leftAdjunct` と `rightAdjunct` は、実は `func curry` と `func uncurry` に対応**します。

---

<img width="800" alt="category-p73.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/af003694-449e-9122-7562-d27d1aee09dd.png">

次に、**随伴のもう一つの定義**を見ていきます。

---

<img width="800" alt="category-p74.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/b6c40d37-ff0f-3a1b-2c74-ae3510512568.png">

先ほど、2つの圏の射 $f$ と $\overline{f}$ は、1:1 で対応している、という話をしました。

---

<img width="800" alt="category-p75.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/658fa8a4-7562-bec6-285c-2619a525a532.png">

ここで、2つの関手 `F` と `G` を **1回ずつ適用して戻ってくる場合** を考えてみます。
すると、このような図が書けます。
（前の状態に戻ってきていないので、随伴が同型とは異なることが分かります）

ここで、新しくできた `F(U(D))` と `U(F(C))` について、それぞれどのような関係があるかを見てみます。

---

<img width="800" alt="category-p76.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/a48c0a7f-6519-55a1-fdb7-3262db8b1348.png">

まず、関手の性質で、これら黒の矢印は、関手 `F`、 `G` によるリフトであることが分かります。

---

<img width="800" alt="category-p77.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/4c3084fa-a271-6bd2-e2fd-ba5545782792.png">

次に、随伴関係から、実は **ピンクの射の集合もまた1:1の関係** があります。
（3つ前のスライドで、 **`D = F(C)` とおくことで、左の圏の2つの対象が1つにつぶれるイメージ**です）

ここで、 **左の対象には必ず1つ以上の射があり、それが `id`** です。
それを `leftAdjunct` して対応する右側の圏の射を **`unit` (単元)** と定義します。

---

<img width="800" alt="category-p78.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/37f0ede9-5b12-3487-1ea4-20cd4b48f95c.png">

同様に、右の圏の`id` に対応する左の圏の射を **`counit` (余単元)** と定義します。

---

<img width="800" alt="category-p79.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/e2429dd7-d999-ccf1-6df2-b359bf91cc8d.png">

そうすると、この図のような三角形が出来上がるわけですが、これらは可換になります。

---

<img width="800" alt="category-p80.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/61c568b9-ff83-277d-dd6c-98ff9ce02f3b.png">

いま見てきたことは、 **`leftAdjunct`/`rightAdjunct`の代わりに、 `unit`/`counit` を使っても随伴が定義できる** 、というものです。

---

<img width="800" alt="category-p81.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/013ea024-bff8-e0ee-daa1-0c4ea8ce2a5e.png">

さて、ここでちょっとした型遊びをします。
先ほどの `counit: F<U<D>> -> D` で、 `D` はどんな型でも良いので、 試しに `D = F<C>`を代入してみます。
すると、 `counit: F<U<F<C>>> -> F<C>` になります。
これをさらに 関手 `U` でリフトすると、 `U<F<U<F<C>>>> -> U<F<C>>` が得られます。
これを **`join` という名前の関数** で定義します。

---

<img width="800" alt="category-p82.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/94864b6d-0fb6-7e56-ca70-07c5aea7ccac.png">

すると、このようにまとめられますが、ここで、`U<F<...>>` というのがたくさん出てきているので、`U<F<C>> = M<C>` とおいてしまいます。

---

<img width="800" alt="category-p83.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/de47a76c-1736-4f31-02c9-0cd27460ca5a.png">

すると、このようにシンプルになりました。
こうなると、さらに `join` と `map` を組み合わせて `flatMap` なんてのも作れたりします。

・・・ん？ `flatMap`？
どこかで聞き覚えがありますね。

---

<img width="800" alt="category-p84.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/dc4396b6-b86d-5269-66a3-02217f8a9ed1.png">

そう、実はこのM、 **モナド** のことなんです。

---

<img width="800" alt="category-p85.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/11396fb1-4d04-2360-5101-0f3c355cf7bf.png">

モナドは、簡単に言うと、 **右随伴関手に左随伴関手を合成したもの** です。
そして、 **合成したものは、元の圏に戻ってくるので、モナドは自己関手** です。
これによって、 **「モナドは自己関手の圏における◯△□・・・」** というところまで言えるようになりました。

---

<img width="800" alt="category-p86.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/449fbbd2-303c-1635-1c0b-29182000bef9.png">

さて、このモナドですが、先ほどのタプルと関数型の例を使って、実際に作ってみましょう。
右随伴関手（関数）に左随伴関手（タプル）を合成するということは、 **「関数の中にタプルを入れる」** ことになるので、型としては `S -> (A, S)`。
実はこれ、 **状態モナド** のことです。
関数型プログラミングを知っている方なら、 **状態モナドが圏論と密接に絡んでくる** と知って、胸が熱くなるポイントではないかと思います。

---

<img width="800" alt="category-p87.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/6c7472f6-b1ab-bdf6-d0bf-0ebb4affa857.png">

ですが、私たちが知りたいのは、モナドよりもさらに先の世界です。
いや、むしろ **一周回って「逆の世界」** を考えてみましょう。
そう、モナド `U(F(C))` の逆 `F(U(D))` を考えてみます。

---

<img width="800" alt="category-p88.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/4ee994b7-5b5e-1572-35c9-89cb2a35ad70.png">

すると、先ほど **モナドで出てきた関数の向きがすべて逆** になります。
`unit` だったものは `counit` に、 `join` は `duplicate` と呼ばれる関数に変わります。
そして、 **モナドのMの文字もまた逆さになり、Wという記号** を使います。

---

<img width="800" alt="category-p89.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/f76506fb-8cf7-32a0-d66b-c6b65b2c46d6.png">

そう、この「Mの双対」とも言われる、ライバル的存在・・・

---

<img width="800" alt="category-p90.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/79b30954-9543-090d-6a33-48edf3bc5033.png">

これを **「Comonad」** といいます。
日本語では「余モナド」ともいいます。

---

<img width="800" alt="category-p91.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/b203d880-b88c-8c89-135f-870ac6c49860.png">

コモナドもまた、随伴から`F(U(D))` という形で作ることができます。

---

<img width="800" alt="category-p92.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/c94c7183-bfe8-3614-cd32-68ba73ad3d24.png">

実際にSwiftの例に落とし込んでみます。
すると、モナドのときとは逆で、今度は **「タプルの中に関数を入れる」** 形になります。
すると、このような `struct Store` 型が作れます。
これを **余状態余モナド** といいます。

---

<img width="800" alt="category-p93.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/4ca90ff7-6bb7-b0c4-a10d-8e9750dd83a8.png">

ただ、 余状態余モナド自体はあまり面白くないので、ここでさらに **余代数 (Coalgebra)** を考えてみます。
余代数というのは、とりあえず **S を追加で引数に取る** ものだと思ってください。
すると、なんということでしょう、**レンズ** が出来上がりました。
レンズは、皆さんご存知でしょうか？
簡単にいうと、すごいgetter/setterみたいなものです。

参考： [SwiftでLens(すごいgetter/setter)を実装してみた - Qiita](https://qiita.com/to4iki/items/f0cc28e1102cf53be85d)

---

<img width="800" alt="category-p94.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/6b5fb1fe-14f7-1c3d-73d4-1fbd828da654.png">

つまり、一言でいうと、こういうことです。
**「レンズは余状態余モナドの余代数だよ。」**
・・・すみません、これを言ってみたかっただけでした。

---

<img width="800" alt="category-p95.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/c1ec43bc-97da-d38c-7960-16cca918c8ab.png">

というわけで、まとめです。
今日の発表では、 **圏の定義** から始まり、 **関手** 、 **自然変換** 、 **米田の補題** 、 **随伴** を学んだと思ったら、いつの間にか **モナドとコモナド** が出てきて、 **状態モナドやレンズ** の話にまで発展しました。
後半は、関数型プログラミングを知っていないと、いまいちピンとこないと思うので、ひとまず関数型ポエムだと思って聞き流してください。
**初めて圏論を学ぶ人は、「関手と自然変換」まで理解できれば十分** だと思います。

---

<img width="800" alt="category-p96.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/65bcbb3d-3cc2-20f7-99c6-9349f46f5dfe.png">

もし、もっと深く圏論を学んでみたいという方は、さらに面白いテーマが控えていますので、ぜひこちらもチェックしてみてください。

---

<img width="800" alt="category-p97.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/7fd68863-6b01-0164-e336-9c5f6e172951.png">

#### 参考文献（初学者向け）

- [Bartosz Milewski's Programming Cafe | Category Theory, Haskell, Concurrency, C++](https://bartoszmilewski.com/)
    - 📺 [Bartosz Milewski - YouTube](https://www.youtube.com/user/DrBartosz/playlists)
- 📺 [TheCatsters - YouTube](https://www.youtube.com/user/TheCatsters/playlists)
- [Category theory for beginners](https://www.slideshare.net/kenbot/category-theory-for-beginners)
- [圏論勉強会 @ ワークスアプリケーションズ](http://nineties.github.io/category-seminar/)
- [プログラマーのための圏論（上） - bitterharvest’s diary](http://bitterharvest.hatenablog.com/entry/2016/11/24/203021)

参考： 発表後に、こちらの記事を書きました

- [圏論のオススメ勉強法（プログラマ向け） - Qiita](https://qiita.com/inamiy/items/922d4220bf407efa2dab)

---

<img width="800" alt="category-p98.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/920cb24f-934c-a247-bbcb-719d96455b0c.png">

#### 参考文献（中〜上級者向け）

- 📚 [圏論 原著第2版 | Steve Awodey](https://www.amazon.co.jp/%E5%9C%8F%E8%AB%96-%E5%8E%9F%E8%91%97%E7%AC%AC2%E7%89%88-%E3%82%B9%E3%83%86%E3%82%A3%E3%83%BC%E3%83%96-%E3%82%A2%E3%82%A6%E3%83%87%E3%82%A3/dp/432011115X)
- 📚 [ベーシック圏論 普遍性からの速習コース | Tom Leinster](https://www.amazon.co.jp/%E3%83%99%E3%83%BC%E3%82%B7%E3%83%83%E3%82%AF%E5%9C%8F%E8%AB%96-%E6%99%AE%E9%81%8D%E6%80%A7%E3%81%8B%E3%82%89%E3%81%AE%E9%80%9F%E7%BF%92%E3%82%B3%E3%83%BC%E3%82%B9-Tom-Leinster/dp/4621300709)
- 📚 [圏論の基礎 | Saunders MacLane](https://www.amazon.co.jp/%E5%9C%8F%E8%AB%96%E3%81%AE%E5%9F%BA%E7%A4%8E-S-%E3%83%9E%E3%83%83%E3%82%AF%E3%83%AC%E3%83%BC%E3%83%B3/dp/4621063243)
- [圏論 | 壱大整域](http://alg-d.com/math/kan_extension/)
- [檜山正幸のキマイラ飼育記](http://d.hatena.ne.jp/m-hiyama/)
- [nLab](https://ncatlab.org/)

---

<img width="800" alt="category-p99.png" src="https://qiita-image-store.s3.amazonaws.com/0/2249/4944d4f0-3c12-6535-9275-ef232837a31b.png">

というわけで、今日の発表を終わりにしたいと思います。
ご清聴ありがとうございました。