序文

しばらく前から、プログラマーを対象とした圏論に関する本を書こうと考えていた。計算機科学者ではなくプログラマー、科学者ではなくエンジニア向けだということに注目してほしい。正気の沙汰ではないし、本当に恐ろしい。科学と工学の間に大きなギャップがあるのは否定できないと思う。自分自身がその分断の両側で仕事をしてきたからだ。それでも、物事を説明したいという強い衝動をいつも感じていた。簡潔な説明の達人だったリチャード・ファインマン¹を心から尊敬している。自分がファインマンではないことは分かっているが、最善を尽くしたい。まずは、この序文――読者に圏論を学ぶ気を起こさせることを想定したもの――を公開することから始めようと思う。それによって議論を開始しフィードバックを募れることを願っている²。

ここからの数段落をかけて、この本はあなたのために書かれたものであり、数学のうちでも特に抽象的な分野を学ぶために「あり余る自由時間」を費やすことへのどんな反対意見も全く根も葉もないことを確信してもらえるように試みたい。

私の楽観論はいくつかの観察に基づいている。第一に、圏論は極めて有用なプログラミングのアイデアの宝庫だ。Haskellプログラマーたちは長い間この資源を利用していて、得られたアイデアは他の言語にゆっくりと浸透してきているが、進行が遅すぎる。もっとスピードを上げる必要がある。

第二に、いろいろな種類の数学があり、それぞれ興味を惹く人も異なる。微積分や代数にアレルギーがあったとしても、圏論を楽しめないとは限らない。私としては、圏論はプログラマーのマインドに特に合った数学であるとさえ主張したい。圏論では、個々の物事を扱うのではなく、構造を扱うからだ。圏論はプログラムを合成可能にするような構造を扱う。

合成は圏論の最も根本であり、圏そのものの定義の一部だ。そして私は、合成こそプログラミングの本質であると強く主張したい。我々は、偉大なエンジニアがサブルーチンのアイデアを思いつく遥か前から、ずっとものを合成してきた。かつて構造化プログラミングはプログラミングに革命をもたらした。コードのブロックを合成可能にしたからだ。続いてオブジェクト指向プログラミングが登場した。これはオブジェクトを合成することこそすべてだ。関数プログラミングは、関数や代数的データ構造を合成するだけでなく、並行性をも合成可能にする。これは他のプログラミングパラダイムでは事実上不可能だ。

第三に、私には秘密兵器の「肉切り包丁」がある。それを使って数学を捌いて、よりプログラマーの口に合うものにするつもりだ。プロの数学者としては、すべての仮定を確かめ、すべての命題を適切に述べ、すべての証明を厳密に構成するために細心の注意を払う必要がある。そのせいで数学の論文や書籍は門外漢には非常に読みにくくなっている。だが、私は物理学者としての教育を受けており、物理学は形式的でない推論を用いて驚くべき進歩を遂げた学問だ。かつて数学者たちはディラックのデルタ関数を嗤った。デルタ関数は偉大な物理学者であるP.A.M. ディラックが微分方程式を解く過程で作ったものだ。数学者たちは、ディラックの洞察を形式化した微積分学の全く新しい分野として超関数理論 (distribuiton theory) を発見したとき、嗤うのをやめた。

当然ながら、身振り手振りで議論するときには明らかに間違ったことを言ってしまう危険があるので、本書では非公式な議論の背景にしっかりした数学的理論があるように気を付けたい。私のベッドサイドには、読み古したソーンダーズ・マックレーンの『圏論の基礎』が置かれている。

この本はプログラマーのための圏論なので、すべての主要な概念を説明するのにコンピューターコードを使うことにしたい。お気付きかもしれないが、より普及している命令型言語よりも関数型言語の方が数学に近い。また、より強力な抽象化能力を提供する。そのため、自然な誘惑として「圏論の恩恵に浴するにはHaskellを学ばなければならない」と言いたくなるかもしれない。しかし、それは圏論が関数プログラミング以外の用途を持たないことを意味しており、全く誤っている。そこで、C++での例を数多く載せようと思う。確かに、いくつかの醜い構文を克服しなければならず、雑然とした背景に紛れてパターンが目立たなくなったり、高度な抽象化の代わりにコピー＆ペーストに頼らなければならない場面もあるだろう。だが、それがC++プログラマーというものだ。

しかし、Haskellに関しては逃れられない。Haskellプログラマーになる必要はないが、C++で実装しようとしているアイデアをスケッチしたり文書化したりするための言語としてHaskellが必要になる。私もそうやってHaskellを始めた。そして、簡潔な構文と強力な型システムが、C++のテンプレート、データ構造、アルゴリズムを理解し実装する上で大きな助けになると気付いた。もっとも、読者がすでにHaskellを知っているとは期待できないので、ゆっくり紹介しながら進行に応じてすべて説明していくつもりだ。

プログラマーとしての経験が豊富なら、次のように自問するかもしれない：長い間ずっと圏論や関数型の手法を気にすることなくコーディングしてきたが、何が変わったのだろう？　確かにそう思わずにいられないだろうが、関数型の新機能が続々と登場し、命令型言語に侵入していることに気付いてほしい。オブジェクト指向プログラミングの牙城であるJavaでさえ、ラムダを導入した。最近のC++は数年ごとの新しい標準という激動のペースで進化し、変化する世界に追いつこうとしている。これらはすべて、破壊的な変化、すなわち物理学者である我々が相転移と呼ぶものに備えるための動きだ。お湯を温め続けると、やがて沸騰しはじめる。我々はいま、その中のカエルの立場にいる。カエルはどんどん熱くなるお湯の中で泳ぎ続けるべきなのか、それとも何か別のものを探し始めるべきなのか、決めなければならない。

大きな変化を引き起こしている力のひとつがマルチコア革命だ。広く普及しているプログラミングパラダイムであるオブジェクト指向プログラミングは、並行・並列処理の領域では何のメリットもなく、その代わりに危険でバグを生じやすい設計を奨励している。オブジェクト指向の基本的前提であるデータ隠蔽は、データの共有や改変と組み合わされると、データ競合のレシピになる。ミューテックス³ とそれが保護するデータを組み合わせるというアイデアは素晴らしい。しかし、残念ながらロックは合成できないし、ロックを隠すことでデッドロックが発生しやすくなり、デバッグが難しくなる。

さらに、並行性が存在しないとしても、ソフトウェアシステムの複雑さが増すにつれて、命令型パラダイムのスケーラビリティは限界が試されている。簡単に言うと、副作用が手に負えなくなってきている。確かに、副作用のある関数は便利だし簡単に書ける。それらの作用は、原理的には、名前やコメントに示しておける。SetPasswordやWriteFileなどと命名された関数は、明らかに何らかの状態を変化させ副作用を発生させるが、我々はそれに対処するのには慣れている。副作用のある関数に副作用のある別の関数を合成し始めたときに初めて、物事は複雑になり始める。副作用が本質的に悪いわけではなく、隠れて見えないせいで大規模な管理が不可能になっているのだ。副作用はスケールせず、そして命令型プログラミングでは副作用こそすべてだ。

ハードウェアの変化とソフトウェアの複雑さが増すことで、プログラミングの基礎を再考する必要に迫られている。ヨーロッパの偉大なゴシック大聖堂の建設者と同じように、我々は材料と構造の限界まで技術を磨き続けてきた。フランスには未完成のゴシック建築のボーヴェ大聖堂⁴ があり、限界との深く人間的なこの闘いの証拠となっている。それまでの高さと軽さの記録をすべて破ることを目論んでいたが、相次ぐ崩壊に見舞われた。鉄筋や木製の支柱などの応急処置で崩壊を防いでいるが、明らかに多くのことがうまくいかなかった。現代の視点から見ると、材料科学、コンピューターモデリング、有限要素解析、そして汎用的な数学と物理学の助けなしに、これほど多くのゴシック構造が成功裏に完成したことは奇跡だ。将来の世代が、複雑なオペレーティングシステム、Webサーバー、インターネット基盤を構築する際に我々が示してきたプログラミングのスキルを賞賛するようになるのを願っている。率直に言って、彼らはそうすべきだ。我々はそれらすべてを非常に貧弱な理論的基盤に基づいて行ってきたのだから。前進するためには、これらの基盤を修復しなければならない。

1 圏：合成の本質

圏は、戸惑ってしまうほど単純な概念だ。圏 (category) は複数の対象 (object) とそれらをつなぐ射 (arrow, morphism) で構成される⁵。そのため、圏は図で簡単に表せる。対象は円または点として、射は矢印として描ける。（変化を付けるために、私は対象を子豚、射をロケット花火として描くことがある。） しかし、圏の本質は合成 (composition) にある。あるいは、お好みなら、合成の本質は圏だと言っても構わない。射は合成できるので、対象$A$から対象$B$への射があって、さらに対象$B$から対象$C$への別の射があるなら、それらを合成した$A$から$C$への射が必ずある。

1.1 関数としての射

すでに抽象的ナンセンスでいっぱいだろうか⁶？　絶望しないでほしい。具体的な話をしよう。射を関数として考えよう。関数$f$が型$A$の引数を取って$B$を返すとする。また、別の関数$g$が$B$を取って$C$を返すとする。$f$の結果を$g$に渡せばそれらを合成できる。つまり$A$を取って$C$を返す新たな関数を定義したことになる。

数学では、このような合成を関数同士の間に小さな丸を書いて$g \circ f$のように表す。合成の順序が右から左であることに注意してほしい。これが紛らわしいと感じる人もいるだろう。読者の中には、Unixのパイプ記法：

lsof | grep Chrome

や、F#の前方合成演算子>>を見慣れている人もいるかもしれない。どちらも左から右の向きだ。ところが、数学やHaskellの関数は右から左に合成する⁷。$g \circ f$を「$g$を$f$の後に（“g after f”）」合成する、と読めば理解しやすくなる。

もっとはっきりさせるために、C言語のコードを少々書こう。型Aの引数を取って型Bを返す関数f：

B f(A a);

と、別の関数：

C g(B b);

の合成は次のとおりだ：

C g_after_f(A a)
{
    return g(f(a));
}

ここで再び、右から左への合成g(f(a))が、今回はC言語で現れた。

C++の標準ライブラリには2つの関数を取って合成関数を返すテンプレートがある、と言えたら良かったのだが、そんなものはない。そこで、気分を変えるためにHaskellを少し試してみよう。ここにAからBへの関数の宣言がある：

f :: A -> B

同様に：

g :: B -> C

これらの合成は次のとおりだ：

g . f

Haskellの簡潔さを知ると、C++で単純明快な関数の概念を表現できないのには少し当惑させられる。実際、HaskellではUnicode文字を使えるので、合成を次のようにも書ける：

g ∘ f

Unicodeの二重コロンと矢印さえ使える⁸。

f ∷ A → B

ここで、第1回目のHaskellのレッスンだ：二重コロンは「……という型を持つ」を意味する。関数型 (function type) は2つの型の間に矢印を挿入することで作成される。2つの関数を合成するには、間にピリオド（あるいはUnicodeの丸）を置く。

1.2 合成の性質

どんな圏においても合成が満たすべき非常に重要な性質が2つある。

1. 合成は結合的 (associative) である。3つの射$f$, $g$, $h$があり、それらが合成できる（つまり端同士の対象が一致している）なら、合成するときに括弧は要らない。このことは数学の記法では次のように表される： $$h \circ (g \circ f) = (h \circ g) \circ f = h \circ g \circ f$$ （擬似的な）Haskellでは次のように書ける：

   f :: A -> B
   g :: B -> C
   h :: C -> D
   h . (g . f) == (h . g) . f == h . g . f

   （ここで「擬似的」と呼んだのは、関数に等しさが定義されていないからだ。）

   関数を扱うなら結合性は全く自明だが、その他の圏では自明ではないこともある。

2. どんな対象$A$にも、合成の単位元 (unit) となる射が1つずつ存在する。その射は対象から対象自身へとループを描く。合成の単位元となるというのは、$A$から始まるか$A$で終わるどんな射と合成しても、もとと同じ射になるという意味だ。対象Aについて単位元となる射は$\mathbf{id}_{A}$（$A$上の恒等射、identity）と呼ばれる。数学の表記法では、$f$が$A$から$B$へ向かうなら

   $$f \circ \mathbf{id}_{A} = f$$ かつ $$\mathbf{id}_{B} \circ f = f$$ となる。

関数を扱うとき、恒等射は引数をそのまま返す恒等関数として実装される。この実装はどの型でも同じであり、この関数は普遍的に多相 (universally polymorphic) であることを意味する。これはC++ではテンプレートとして定義できる：

template<class T> T id(T x) { return x; }

もちろん、C++ではそれほど単純ではない。何を渡すかだけでなく、どのように渡すか（値渡し・参照渡し・const参照渡し・ムーブなど）も考慮する必要があるからだ。

Haskellの恒等関数は、（Preludeと呼ばれる）標準ライブラリの一部だ。宣言と定義は以下のとおりだ：

id :: a -> a
id x = x

ご覧のとおり、Haskellの多相関数は朝飯前だ。宣言において、型を型変数に置き換えるだけでよい。トリックは次のとおりだ：具体的な型の名前は常に大文字で始まり、型変数の名前は小文字で始まる。ここでaはすべての型を表している。

Haskellの関数定義は、関数の名前とそれに続く仮引数 (formal parameter) ――ここではxただひとつ――で構成される。関数の本体は等号の後に続く。この簡潔さは、多くの初心者には衝撃的だが、すぐに完全に理にかなっていることが分かるだろう。関数定義と関数呼び出しは関数プログラミングの必需品なので、構文は最小限に抑えられている。引数リストを括弧で囲まないだけでなく、引数間のコンマさえない（これについては後ほど複数の引数の関数を定義するときに説明する）。

関数の本体は常に式 (expression) であり、関数内に文 (statement) はない。関数の結果はその式だ――ここでは単にxだ。

これでHaskellのレッスンの第2回は終了だ。

恒等条件は、（再び疑似Haskellで）次のように書ける。

f . id == f
id . f == f

誰が恒等関数――何もしない関数――をわざわざ気にするのか、と疑問に思うかもしれない。では、なぜ0という数をわざわざ気にするのだろうか？　0は無の象徴だ。古代ローマ人は0のない数値体系を使っていたが、優れた道路や水路を建設でき、その一部は今日まで残っている。

0や$\mathbf{id}$のような中立の値は、記号変数を扱うときに非常に便利だ。これこそが、ローマ人は代数があまり得意ではなく、0の概念に精通していたアラビア人やペルシア人は得意だった理由だ。そのため、恒等関数は、高階関数 (higher-order function) の引数あるいは戻り値として非常に便利になる。高階関数は関数の記号的操作を可能にする。それらは関数の代数だ。

要約すると、圏は対象と射で構成されている。射は合成でき、その合成は結合性を持つ。すべての対象には、合成の単位元として機能する恒等射がある。

1.3 合成はプログラミングの本質

関数プログラマーは、問題に独特の方法でアプローチする。彼らはまるで禅のような問いから始める。たとえば、対話型プログラムを設計するときは「対話とは何か？」と問うだろう。コンウェイのライフゲームを実行するときには、生命の意味について思索するだろう。そのような精神で「プログラミングとは何か？」と問いかけたい。最も基本的なレベルでは、プログラミングとはコンピューターに何をすべきかを指示することだ。「メモリーアドレスxの内容を取り、レジスタEAXの内容に加えよ」のように。しかし、アセンブリー言語でプログラムを作成する場合でも、コンピューターに与える命令はもっと意味のあるものを表現している。解こうとしているのは自明な問題ではないのだ（自明ならコンピューターの助けは不要だろう）。どうすれば問題を解けるだろうか？　大きな問題を小さな問題に分解すればよい。小さくした問題がまだ大きすぎる場合は、それらをさらに分解する。最後に、小さな問題すべてについて、解決するコードを書く。そうしてプログラミングの本質が現れる。すなわち、それらのコードを合成し、より大きな問題に対する解決策を創造する。分解は、断片をもとの状態に戻せなければ意味がない。

この階層的な分解と再合成のプロセスは、コンピューターによって強制されているわけではない。それは人間の精神の限界を反映しているのだ。脳は一度に少しの概念しか扱えない。心理学で最も引用された論文の1つ、The Magical Number Seven, Plus or Minus Two⁹は、我々は$7 \pm 2$の「チャンク」の情報しか保持できないと仮定した。人間の短期記憶に関する我々の理解の詳細は変化しているかもしれないが、限界があるのは確実に分かっている。要するに、我々はオブジェクトのスープやコードのスパゲッティを扱えないということだ。構造が必要なのは、よく構造化されたプログラムが見やすいからではなく、そうでなければ脳が効率的に処理できないからだ。あるコード断片について、エレガントだ、あるいは美しいと形容することがよくある。だが、本当に意味しているのは、人間の限界ある精神で処理するのが簡単だということだ。エレガントなコードは、ちょうど適切なサイズのチャンクを作成し、精神の消化器系がそれらを消化するのにちょうど適切な数だけ生成する。

では、プログラムの合成にとって適切なチャンクとは何だろうか。チャンクの表面積は体積よりも必ずゆっくりと増加する。（私がこのたとえを気に入っているのは、幾何学的な対象の表面積はその大きさの2乗に比例して増加する――体積が大きさの3乗に比例して増加するのよりも遅い――という直観による。）表面積は、チャンクを合成するために必要な情報だ。体積は、それらを実装するために必要な情報だ。そのこころは、ひとたびチャンクが実装されると、その実装の詳細を忘れて他のチャンクとの相互作用に集中できる、ということだ。オブジェクト指向プログラミングでは、表面はオブジェクトのクラス宣言、あるいはその抽象インターフェースだ。関数プログラミングでは、それは関数の宣言だ¹⁰。（ここでは少し単純化しているが、要点はこれだ。）

圏論は、対象の中を見ることを積極的に思いとどまらせるという意味で極端だ。圏論における対象は抽象的で漠然とした存在だ。対象について知り得るのは、他の対象たちとどのように関連しているか、つまり、どのように射で接続しているかだけだ。これは、インターネット検索エンジンが流入リンクと流出リンクを分析してウェブサイトを順位付けするやり方だ（不正行為がある場合は除く）。オブジェクト指向プログラミングでは、理想化されたオブジェクトを見られるのは抽象インターフェース（純粋な表面なので体積なし）を通してだけで、メソッドが射の役割を果たす。他のオブジェクトと合成する方法を理解するためにオブジェクトの実装を掘り下げなければならなくなった瞬間、このプログラミングパラダイムの利点は失われてしまう。

1.4 課題

1. 恒等関数を、好きな言語で（それがたまたまHaskellなら2番目に好きな言語で）できるだけうまく実装せよ。

2. 合成関数を好きな言語で実装せよ。このメソッドは2つの関数を引数として受け取り、その合成である関数を返す。

3. 合成関数が恒等関数と整合しているかテストするプログラムを作成せよ。

4. ワールドワイドウェブは、何らかの意味で圏だろうか？　リンクは射だろうか？

5. Facebookは人を対象とし友達関係を射とする圏だろうか？

6. 有向グラフが圏になるのはどのような場合だろうか？

2 型と関数

型と関数の圏はプログラミングにおいて重要な役割を果たす。そこで、型とは何か、なぜ型が必要なのかについて説明しよう。

2.1 型を必要とするのは誰か？

静的型付けと動的型付け、および強い型付けと弱い型付けの利点については、議論があるようだ。これらの選択肢を思考実験で説明しよう。コンピューターのキーボードを操作する何百万匹もの猿が喜んでランダムにキーを打ち、プログラムを作成したり、コンパイルしたり、実行したりする様子を想像してみてほしい。

機械語では、猿が生成するバイトの組み合わせはどれでも受け入れられて実行される。しかし、より高級な言語ではコンパイラーが語彙や文法上の誤りを検出できるという事実を我々は理解している。多くの猿はバナナなしで去るだろうが、残されたプログラムは役に立つ可能性が高いだろう。型検査も、無意味なプログラムに対するもう1つの防御壁となる。さらに、型の不一致は動的型付け言語では実行時に発見されるのに対し、強く型付けされ静的に型検査される言語ではコンパイル時に発見されるので、多くの不正なプログラムが実行される機会を得る前に排除される。

そこで、問題は次のようになる。猿を幸せにしたいのか、それとも正しいプログラムを作りたいのか？

タイピング猿の思考実験における通常の目標はシェークスピア全集を作ることだ。スペルチェッカーと文法チェッカーをループに含めれば、勝算は大幅に上昇するだろう。型検査器に類するものを含めれば、さらなる前進が見込める。ロミオは人間である、と宣言されていれば、彼は決して葉を発芽したり自身の強力な重力場に光子を閉じ込めたりはしない。

2.2 型は合成に関する

圏論は射を合成することに関する。しかし、2本の射なら何でも合成できるわけではない。ある射の終点 (target) となる対象は、次の射の始点 (source) となる対象と同じでなくてはならない。プログラミングでは、ある関数の結果を別の関数に渡す。後段の関数が前段の関数によって生成されたデータを正しく解釈できない場合、プログラムは機能しない。合成が機能するためには両端が適合しなければならない。言語の型システムが強力であればあるほど、この一致はよりよく記述され、機械的に検証される。

強力な静的型検査に対して私が耳にする唯一の重要な反対意見は、意味的に正しいプログラムを排除する可能性がある、というものだ。実際には、そうなることは極めてまれで、いずれにしても、どの言語にも、本当に必要な場合に型システムを迂回するための何らかのバックドアが用意されている。HaskellにさえunsafeCoerceがある。しかし、このような装備は思慮深く使うべきだ。フランツ・カフカの小説の主人公グレゴール・ザムザが、巨大なバグに変身したとき型システムを破壊し、どんな結末を迎えたかは誰もが知っている。

私がよく耳にするもう1つの意見は、型を扱うのはプログラマーにとって負担が大きすぎる、というものだ。私もC++でイテレーターの宣言をいくつか自分で書かなければならなかったら共感するだろう。もっとも、型推論 (type inference) と呼ばれる技術があり、コンパイラーはほとんどの型を文脈から推論できるようになっている。C++では、変数をautoで宣言してコンパイラーにその型を発見させられるようになった。

Haskellでは、稀な場合を除いて、型注釈は純粋にオプションだ。プログラマーはどのみち型注釈を使う傾向がある。なぜなら、コードの意味について多くを伝えられ、コンパイルエラーを理解しやすくできるからだ。Haskellでは、型を設計することからプロジェクトを始めるのが一般的な慣習だ。後々、型注釈は実装を駆動し、コンパイラーによって強制されるコメントになる。

強力な静的型付けはコードをテストしない言い訳としてよく使われる。Haskellのプログラマーが「コンパイルが通るなら正しいはずだ」と言っているのを耳にすることがあるだろう。しかし、型が正しいプログラムなら正しい出力を生成する、などという保証は当然ない。そのような無頓着な態度の結果、いくつかの研究では、Haskellのコード品質は予想ほど群を抜いて高くはなかった¹¹。商用の環境では、バグを修正する圧力はある品質レベルまでしか働かないようだ。そのレベルは、ソフトウェア開発の経済的状況とエンドユーザーの許容度に深く関係し、プログラミング言語や方法論にはほとんど関係しないのだろう。より良い基準は、スケジュールより遅れているプロジェクトや、大幅に機能が削減されたプロジェクトの数を調べることだろう。

単体テストによって強い型付けを置き換えられる、という意見に関しては、強く型付けされた言語で一般的に行われているリファクタリング手法として、関数の引数の型の変更について考えてみてほしい。強く型付けされた言語では、その関数の宣言を変更してから、すべてのビルドブレークを修正すれば十分だ。弱く型付けされた言語では、関数が異なるデータを要求するようになったという事実は呼び出し側に伝わらない。単体テストはミスマッチのいくつかを捉えるかもしれないが、テストはほとんどすべての場合において、確率論的なプロセスにすぎず、決定論的なプロセスではない。テストは証明の代わりにはならないのだ。

2.3 型とは何か？

型とは、最も単純な直観としては、値の集合だ。型BoolはTrueとFalseの二元集合だ（Haskellでは具体的な型は大文字で始まることを思い出してほしい）。Char型はaやąのようなUnicode文字すべてからなる集合だ。

集合は有限の場合も無限の場合もあり得る。String型は、Charのリストの同義語で、無限集合の例だ。

以下のようにxをIntegerとして宣言すること：

x :: Integer

は、xが整数の集合の要素だと言っていることになる。HaskellのIntegerは無限集合であり、任意精度の演算が可能だ。また、C++のintと同様の、マシンネイティブの型に対応する有限集合Intもある。

いくつか微妙な点があるせいで、こうした型と集合の同一視はトリッキーなものになっている。多相関数には循環定義の問題があり、すべての集合の集合が存在しないことも問題だ。だが、約束したとおり、私は数学にこだわるつもりはない。ありがたいことに、集合の圏が存在する。$\mathbf{Set}$と呼ばれるその圏をここでは扱う。$\mathbf{Set}$では、対象は集合であり、射は関数だ。

$\mathbf{Set}$は非常に特別な圏だ。対象の内部を実際に見られ、そうすることで多くの直観が得られるからだ。たとえば、空集合には要素がないと分かっている。単元集合という特別な集合たちが存在するのも分かっている。関数が1つの集合の要素を別の集合の要素に写すのも分かっている。関数は、2つの要素を1つに写すことはできるが、1つの要素を2つに写すことはできない。恒等関数が集合の各要素を自身に写すことなども分かっている。予定としては、これらすべての情報を徐々に忘れ、すべての概念を純粋に圏論の言葉、つまり対象と射によって表していく。

理想的な世界では、Haskellの型は集合であり、Haskellの関数は集合間の数学的関数であると言えば済んだだろう。だが、1つだけ小さな問題がある。数学関数はコードを実行せず、単に解を知っているだけなのだ。Haskellの関数は解を計算する必要がある。有限のステップ数で解が得られるなら、何ステップかかっても問題はない。ところが、計算のなかには再帰を伴うものもあり、ずっと停止しないことがあり得る。Haskellで停止しない関数をただ単に禁止はできない。なぜなら、停止する関数と停止しない関数の区別は決定不能だからだ。これは停止性問題 (halting problem) として有名だ。そのため計算機科学者たちは素晴らしいアイデアを考案した。それは捉え方によっては大きなハッキングとも言えるだろう。そのアイデアとは、ボトム (bottom) と呼ばれる、記号_|_またはUnicodeの$\bot$で¹²表される特別な値を用いてすべての型を拡張する、というものだ。この「値」は停止しない計算に対応する。したがって、次のように宣言される関数：

f :: Bool -> Bool

はTrueかFalseか_|_を返し、ボトムの場合は決して停止しないことを意味する。

興味深いことに、ひとたび型システムの一部としてボトムを受け入れたなら、すべての実行時エラーをボトムとして扱い、さらには関数からボトムを明示的に返せるようにするのが便利になる。後者は通常、undefinedという式を使って行われる：

f :: Bool -> Bool
f x = undefined

この定義が型検査を通るのは、undefinedが評価されるとボトムになるからだ。ボトムはBoolも含むすべての型のメンバーだ。さらに：

f :: Bool -> Bool
f = undefined

のように（xなしで）書くことさえできる。ボトムがBool -> Bool型のメンバーでもあるためだ。

取りうるすべての引数に対して有効な結果を返す関数が全域関数 (total function) と呼ばれるのに対し、ボトムを返す可能性のある関数は部分関数 (partial function) と呼ばれる。

ボトムがあるため、Haskellの型と関数の圏は、$\mathbf{Set}$ではなく$\mathbf{Hask}$と呼ばれる。理論的な観点から見ると、これは果てしない複雑さの原因となる。だから、この時点で一連の推論を肉切り包丁で捌いて終わらせよう。実用的な観点からは、停止しない関数とボトムを無視し、$\mathbf{Hask}$を正真正銘の$\mathbf{Set}$として扱うことは問題ない¹³。

2.4 なぜ数学モデルが必要なのか？

プログラマーであるあなたは、自分が使っているプログラミング言語の構文と文法に精通している。言語のそれらの側面は、通常、言語仕様の冒頭で形式的な表記法によって記述される。一方で、言語の意味、すなわちセマンティクスを記述するのははるかに困難だ。より多くのページを必要とし、十分に形式的であることはほとんどなく、完全であることもほとんどない。それゆえ、言語法律家たちの間では終わりのない議論が交わされ、言語標準の細かい解釈を目的とした書籍が家内工業的に出版されている。

言語のセマンティクスを記述するための形式手法ツールは存在するが、複雑なため、ほとんどの場合は簡略化された学術言語で使われ、実用される巨大なプログラミング言語ではあまり使われない¹⁴。そのようなツールのうち操作的意味論 (operational semantics) と呼ばれるものは、プログラム実行の仕方を記述する。それは形式化され理想化されたインタープリターを定義する。C++のような産業用言語のセマンティクスは通常、操作的挙動に関する非形式的な議論により「抽象機械」として述べられることが多い。

問題は、操作的意味論を使ってプログラムに関することを証明するのが非常に難しいことだ。プログラムの性質を示すには、基本的には理想化されたインタープリターを通して「実行」しなければならない¹⁵。

プログラマーが正しさを形式的に証明しないことは問題ではない。我々はいつも正しいプログラムを書いていると「思っている」。キーボードの前に座って、「さて、コードを数行打ち込んで、何が起こるか見てみよう」と言う人はいない。我々は、作成するコードが望ましい結果を生み出す特定のアクションを実行すると考えている。そうならない場合、たいていかなり驚くことになる。つまり、我々は自分が書いたプログラムについて推論していて、通常は頭の中でインタープリターを走らせることでそうしている。すべての変数を追跡するのは極めて難しい。コンピューターはプログラムを実行するのが得意だが、人間は不得意だ！　もし得意だったら、コンピューターは必要ないだろう。

しかし、別の選択肢もある。それは表示的意味論 (denotational semantics) と呼ばれ、数学に基づいている。表示的意味論では、すべてのプログラム要素に数学的解釈が与えられる。それを使えば、プログラムの性質を証明したいときは数学的定理を証明するだけでよい¹⁶。定理を証明するのは難しいと思うかもしれないが、実際には、人類は数千年にわたって数学的手法を構築してきたので、利用できる知識が豊富に蓄積されている。また、プロの数学者が証明する定理と比べると、プログラミングで遭遇する問題は、自明ではないにせよ、通常は極めて単純なものだ。

表示的意味論ととても相性が良い言語であるHaskellで階乗関数の定義を考えてみよう：

fact n = product [1..n]

式[1..n]は、1からnまでの整数のリストだ。関数productは、リストのすべての要素を乗算する。これは数学の教科書に載っている階乗の定義と同じだ。これをCと比較してほしい：

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

これ以上言う必要があるだろうか？

確かに、不当な批判だったのは真っ先に認めよう！　そもそも階乗関数には自明な数学的解釈がある。鋭い読者なら「キーボードから文字を読み取ったり、ネットワークを介してパケットを送信したりするための数学的モデルは何か？」と尋ねるだろう。長きに渡って、それはかなり複雑な説明につながる面倒な質問だった。有用なプログラムを書くために不可欠な多くの重要なタスクには、表示的意味論は最適でないように思われたが、操作的意味論では容易に解決できた。突破口は圏論からもたらされた。エウジニオ・モッジ (Eugenio Moggi) によって、計算作用をモナドに写せることが発見された。これは表示的意味論に新たな生命を与え、純粋関数プログラムをより使いやすくするだけでなく、従来のプログラミングに新たな光を当てる重要な観察となった。モナドについては後ほど、より多くの圏論的な道具立てを説明するときに述べる。

プログラミングに数学的モデルがあることの重要な利点の1つは、ソフトウェアの正しさを形式的に証明できることだ¹⁷。消費者向けのソフトウェアを書く際にはそれほど重要でないように思えるだろうが、失敗の代償が法外なものになったり人命が危険にさらされたりするようなプログラミングの領域もある。もっとも、医療システム用のWebアプリケーションを作成する場合でさえ、Haskell標準ライブラリの関数やアルゴリズムが正しさの証明を伴うというアイデアに価値を見出すだろう。

2.5 純粋関数と非純粋関数

C++やその他の命令型言語で関数と呼ぶものは、数学者が関数と呼ぶものとは異なる。数学関数は値から値への写像にすぎない。

数学関数はプログラミング言語で実装できる。そのような関数は、入力値が与えられると、出力値を計算する。数の2乗を生成する関数は、入力値をそれ自身で乗算するはずだ。この関数は呼び出すたびに同じことを行い、同じ入力で呼び出されるたびに同じ出力を生成することが保証されている。数の2乗は月の満ち欠けによって変化しない。

また、数の2乗を計算することで犬においしい餌を出すという副作用があってはならない。それを行う「関数」は数学関数として簡単にモデル化できない。

プログラミング言語では、同じ入力に対して常に同じ結果を生成し副作用のない関数は純粋関数 (pure function) と呼ばれる。Haskellのような純粋関数型言語では、すべての関数が純粋だ¹⁸。そのため、これらの言語に表示的意味論を与え、圏論でモデル化することが容易になる。他の言語の場合は、純粋なサブセットだけを使うように制限したり、副作用を切り分けて扱ったりすることは常に可能だ。モナドによって、純粋関数のみを使ってあらゆる種類の作用をモデル化する方法については、後ほど説明する。数学的関数だけという制約を課しても何も失われないのだ。

2.6 型の例

型が集合であることを理解すれば、ややエキゾチックな型を考えられる。たとえば、空集合に対応するのはどんな型だろう？　それは決してC++のvoidではないが、HaskellではVoidと呼ばれている。その型には値が存在しない。Voidを引数に取る関数は、定義はできるが呼び出せない。呼び出すにはVoid型の値を提供する必要があるが、それは存在しないからだ。この関数が返す内容に関しては、何ら制限はない。それは任意の型を返せる（ただし、呼び出せないため、返すことはない）。言い換えると、戻り値の型が多相な関数だ。Haskell使いたちはこう呼ぶ：

absurd :: Void -> a

（aは任意の型を表せる型変数なのを覚えておいてほしい。）この名前は偶然ではない¹⁹。型と関数を論理の言葉でより深く解釈したカリー・ハワード同型と呼ばれるものが存在する。型Voidは矛盾を表し、関数absurdの型は「矛盾からは何でも導ける」というラテン語の格言 “ex falso sequitur quodlibet” に対応している²⁰。

次は、単元集合に対応する型だ。これが持てる値は1つしかない。その値は「唯一存在する」。すぐには分からないかもしれないが、これがC++のvoidだ。この型を引数に取る関数と、この型を返す関数を考えてみてほしい。voidを取る関数は常に呼び出せる。それが純粋関数なら、常に同じ結果を返す。そのような関数の例を示そう：

int f44() { return 44; }

この関数は引数に取るものが「何もない」のだと思うかもしれないが、先ほど見たように、「何もない」を取る関数ならば決して呼び出せない。「何もない」を表す値がないからだ。この関数は何を取るのだろうか？　概念的には、インスタンスが1つしか存在しないダミー値を取る。そのため、その値に明示的に言及する必要はない。しかしHaskellでは、その値を表す記号として、空の括弧のペア()がある。こうして、奇妙な偶然（これは偶然なのか？）によって、voidに対する関数の呼び出しはC++とHaskellで同じように見える。また、Haskellは簡潔さを好むので、同じシンボル()が型、コンストラクター、そして単元集合に対応する唯一の値に使われる。この関数をHaskellで書くとこうなる：

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

最初の行は、f44が “unit” と発音される()型をInteger型に写すことを宣言している。2番目の行はf44を、unitの唯一のコンストラクター()に対してパターンマッチングを行い、44という数を返すことによって定義している。この関数を呼び出すにはunitの値()を与える：

f44 ()

unitのどの関数も、結果の型から1つの要素を選択するのと等価であることに注意してほしい（ここではIntegerである44を選択する）。実際、f44は数44の別の表現と見なせる。これは、集合の要素への明示的な言及の代わりに関数（射）についての議論に置き換える方法の例だ。unitからどんな型$A$へのどんな関数も、その集合$A$の要素と1対1で対応している。

void型を返す関数や、Haskellでunit型を返す関数はどうだろうか？　C++ではそのような関数が副作用を目的として使われるものの、数学的な意味での本当の関数ではないのは分かっている。unitを返す純粋関数は何もせず、引数を破棄する。

数学的には、集合$A$から単元集合への関数は$A$のすべての要素をその単元集合の単一の要素に写す。$A$ごとに、そのような関数が1つだけ存在する。Integerに対するこの関数は次のとおりだ：

fInt :: Integer -> ()
fInt x = ()

任意の整数を与えると、unitが返される。簡潔さの精神で、Haskellでは、破棄する引数をワイルドカードパターンであるアンダースコアで示せる。この方法なら引数に名前を付ける必要はない。よって、上記は次のように書き直せる：

fInt :: Integer -> ()
fInt _ = ()

この関数の実装は、渡された値に依存しないだけでなく、引数の型にも依存しないことに注目してほしい。

どの型に対しても同じ式で実装できる関数は、パラメトリック多相関数 (parametrically polymorphic function) と呼ばれる。そのような関数の族 (family) はすべて、具体的な型の代わりに型パラメーターを使う1つの等式によって実装できる。任意の型からunit型への多相関数を何と呼ぶべきだろう？　もちろんunitと呼ぶ：

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

C++では、この関数を次のように記述する：

template<class T>
void unit(T) {}

型の類型学における次のものは二元集合だ。C++ではboolと呼ばれ、Haskellでは予想どおりBoolと呼ばれる。違いは、C++のboolは組み込みの型であるのに対して、Haskellでは次のように定義できることだ：

data Bool = True | False

（この定義の読み方はBool is True or Falseだ。） 原理的には、C++でもBoolean型を列挙型として定義できるはずだ：

enum bool {
    true,
    false
};

しかし、C++のenumは密かに整数だ²¹。C++11の “enum class” を代わりに使うこともできたが、その場合は、bool::trueやbool::falseのように、クラス名で値を修飾する必要がある。そして、言うまでもなく、それを使うすべてのファイルに適切なヘッダを含める必要がある。

Boolを取る純粋関数は、結果の型から2つの値を選択するだけだ。1つはTrueに対応し、もう1つはFalseに対応する。

Boolを返す関数は述語 (predicate) と呼ばれる。たとえば、HaskellライブラリData.CharはisAlphaやisDigitのような述語でいっぱいだ。C++にはisalphaやisdigitなどを定義する同様のライブラリがあるが、これらはブール値ではなくintを返す。実際の述語はstd::ctypeで定義され、ctype::is(alpha, c)、ctype::is(digit, c)などの形式がある。

2.7 課題

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

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

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

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

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

   2. std::getchar()

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

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

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

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

3 圏のさまざま

様々な例を調べれば圏の真価が理解できる。圏にはさまざまな形やサイズがあり、予期しない場所によく現れる。ごくシンプルなものから始めよう。

3.1 対象がない場合

最も自明な圏は、対象が0個で、したがって射が0本のものだ。それ自体は非常に哀しい圏だが、他の圏との関連、たとえば、すべての圏の圏（そう、そういうものが存在する）において重要になるだろう。空集合に意味があると思うなら、空圏 (empty category) が無意味だとは思わないだろう？

3.2 有向グラフ

対象を射で接続するだけで圏を作成できる。任意の有向グラフから始めて、単に射を追加するだけで圏になるのは想像できるだろう。最初に、各ノードに恒等射を追加する。次に、一方の終点が他方の始点と一致するような2つの射（つまり、2つの合成可能な射）に対して、それらの合成として機能する新しい射を追加する。新しい射を追加するたびに、（恒等射を除く）他の射との合成も考慮する必要がある。たいていは射が無限に多くなるが、問題ない。

このプロセスを別の方法で見ると、グラフ内の各ノードを対象とし、合成可能なグラフの辺からなるすべてのチェイン²²を射とする圏を作成していることになる。（恒等射はチェインの長さが0の特殊な場合とも見なせる。）

このような圏は、与えられたグラフによって生成される自由圏 (free category) と呼ばれる。これは自由構成 (free construction) の例であり、任意の構造を、その規則（ここでは圏の規則）を満たせる最少の項目で拡張して完成させるプロセスだ。今後さらに多くの例について見ていく。

3.3 順序

さて、全く別のものを見てみよう！　射が対象間の関係、具体的には小なりイコール（$\leqslant$）であるような圏だ。これが本当に圏かどうか調べてみよう。恒等射はあるだろうか？　すべての対象はそれ自身以下だろうか：良し！　合成はあるだろうか？　$a \leqslant b$かつ$b \leqslant c$ならば$a \leqslant c$：良し！　合成は結合的か？　良し！　このような関係は前順序 (preorder) と呼ばれる。前順序は確かに圏だ。

$a \leqslant b$かつ$b \leqslant a$ならば$a$は$b$と等しくなければならないという追加の条件も満たす、より強い関係も考えられる。これを半順序 (partial order) と呼ぶ。

最後に、任意の2つの対象が$\leqslant$またはその逆で関係しているという条件も課せる。そうすると、線形順序 (linear order) または全順序 (total order) と呼ばれる関係が得られる。

これらの関係を満たす順序集合を圏として特徴づけよう。前順序は、任意の対象$a$から任意の対象$b$に向かう射が高々1つ存在する圏となる。そのような圏は別名「細い圏」(thin category) と呼ばれる。前順序圏は細い圏だ。

圏$\mathbf{C}$における対象$a$から対象$b$への射の集合はhom集合と呼ばれ²³、$\mathbf{C}(a, b)$ と書かれる（$\mathbf{Hom}_{\mathbf{C}}(a, b)$ とも書かれる）。したがって、前順序のhom集合はどれも空集合か単元集合になる。これはhom集合$\mathbf{C}(a, a)$、つまり$a$から$a$への射の集合にも当てはまる。その場合はどの前順序においても必ず単元集合になり、恒等射だけを含む。ただし、前順序では循環が起こりうる。半順序では循環は禁止されている。

整列（ソーティング）においては前順序・半順序・全順序を区別できることが非常に重要だ。クイックソート・バブルソート・マージソートなどの整列アルゴリズムは全順序に対してのみ正しく機能する。半順序にはトポロジカルソートが使える。

3.4 集合としてのモノイド

モノイドは非常にシンプルにもかかわらず驚くほど強力な概念だ。それは基礎的な計算の背景にある概念であり、加算と乗算は両方ともモノイドをなす。モノイドはプログラミングの世界では至るところにある。それは、文字列、リスト、畳み込み可能なデータ構造、並行プログラミングのfuture、関数型リアクティブプログラミングのイベントなどとして現れる。

伝統的に、モノイドは二項演算を持つ集合として定義される。この演算に要求されるのは、結合律を満たすことと、単位元のように振る舞う特別な要素が1つあることだけだ。

たとえば、0を含む自然数は加算についてモノイドをなす。結合律は次のことを意味する： $$(a + b) + c = a + (b + c)$$ （言い換えると、数を加算するときは括弧を無視できる。）

中立元²⁴は0だ。なぜなら： $$0 + a = a$$ かつ $$a + 0 = a$$ だからだ。2つ目の等式は冗長だ。加算は可換 $(a + b = b + a)$ だからだ。ただし、可換律はモノイドの定義の一部ではない。たとえば、文字列連接は可換ではないが、モノイドをなす。ちなみに、文字列連接の中立元は空文字列であり、文字列を変更せずに文字列の両側に付加できる。

Haskellではモノイドに対して型クラスを定義できる。その型クラスに属する型は、memptyと呼ばれる中立元とmappendと呼ばれる二項演算を持つ。

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

この2引数関数の型シグネチャーでのm -> m -> mという型は、最初は奇妙に見えるかもしれないが、カリー化を知った後には完全に理にかなったものだと思えるようになるだろう。複数の矢印を含むシグネチャーには、2つの基本的な解釈がある。複数の引数を取る関数とみなして右端の型を戻り値の型とする解釈と、1引数（左端の引数）の関数とみなして関数を返すという解釈だ。後者の解釈は、m -> (m -> m)のように括弧（矢印が右結合であるため冗長）を追加することによって強調できる。この解釈については後で説明する。

Haskellでは、memptyとmappendのモノイド性（monoidal properties、すなわち、memptyは中立で、mappendは結合律を満たすという事実）を表現する方法がないことに注意してほしい。それらを満たすことを確認するのはプログラマーの責任だ。

HaskellのクラスはC++のクラスほど押し付けがましくはない。新しい型を定義するときに事前にクラスを指定する必要はない。先延ばしして、与えられた型を後からあるクラスのインスタンスであると宣言してよい。例として、memptyとmappendの実装を提供することでStringをモノイドとして宣言しよう（実際には、これは標準のPreludeですでにやってくれている）：

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

ここで、Stringの値は単に文字のリストなので、リスト連接演算子(++)を再利用した。

Haskellの構文に関する注：中置演算子は括弧で囲うことで2つの引数を取る関数に変換できる。与えられた2つの文字列を連接するには、それらの間に++を挟んでもよい：

"Hello " ++ "world!"

あるいは、括弧付きの(++)に2つの文字列を引数として渡してもよい：

(++) "Hello " "world!"

関数の引数がコンマで区切られたり括弧で囲まれたりしていないことに注意してほしい。（これはおそらく、Haskellを学ぶときに慣れるのが一番難しい部分だろう。）

Haskellでは関数の等しさを次のように表現できることは、強調しておく価値がある：

mappend = (++)

概念的には、これは関数によって生成される値の等しさを次のように表現するのとは異なる：

mappend s1 s2 = (++) s1 s2

前者は、$\mathbf{Hask}$圏（または、終わりのない計算を指すボトムを無視するなら、$\mathbf{Set}$）の射の等しさに変換される。このような等式はより簡潔であるだけでなく、しばしば他の圏にも一般化できる。後者は外延的等価性 (extensional equivalence) と呼ばれ、どんな2つの入力文字列に対してもmappendと(++)の出力は同じであることを述べている。引数の値は点 (point) と呼ばれることが（「点$x$における$f$の値」という言い回しのように）あるため、これは点ごとの等しさ (point-wise equality) と呼ばれる。引数を指定しない関数の等しさはポイントフリー (point-free) と表現される。（ちなみに、ポイントフリーの式は関数合成を含むことが多く、これは点記号.で表されるため、初心者は少し混乱するかもしれない。）

C++でモノイドを宣言するのに最も近い方法は、C++20標準のコンセプト機能を使うことだ。

template<class T>
struct mempty;

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

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

最初の定義は、各特殊化で中立元を保持するための構造だ。

キーワードdeleteは、デフォルト値が定義されていないことを意味する。これはケースバイケースで指定する必要がある。同様に、mappendにもデフォルトはない。

Monoidというコンセプトは、与えられた型Mに対してmemptyとmappendの適切な定義が存在するかをテストする。

このMonoidコンセプトのインスタンス化は、適切な特殊化とオーバーロードを提供することで実現できる：

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

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

3.5 圏としてのモノイド

ここまではモノイドの「おなじみの」定義として、集合の要素に基づくものを見た。しかし、ご存知のように、圏論では集合とその要素から逃れようとし、代わりに対象と射について述べる。そこで、少し視点を変えて、二項演算子を適用すると集合の周りで何かを「移動」したり「シフト」したりすると考えてみよう。

たとえば、各自然数に5を加算する演算を考える。これは0を5、1を6 、2を7のように写す。これは関数で、自然数の集合上で定義されている。良い感じだ。関数と集合がある。一般に、任意の数$n$について、$n$を加算する関数が存在する。これは$n$の「加算器」だ。

加算器はどのように合成すればよいだろう？　5を加算する関数と7を加算する関数の合成は、12を加算する関数だ。これにより、加算器の合成を加算ルールと等価にできる。これまた良い感じだ。加算を関数合成に置き換えられる。

ちょっと待った。それだけではない。中立元0の加算器もある。0を加算しても何も写されないので、これは自然数の集合における恒等関数だ。

従来の加算の規則を与える代わりに、情報を失うことなく加算器を構成する規則を与えることもできる。加算器の合成は結合律を満たすことに注目してほしい。これは、関数の合成が結合律を満たし、恒等関数に対応する0加算器があるからだ。

鋭い読者なら、整数から加算器への写像がmappendの型シグネチャーをm -> (m -> m)と解釈した結果であることに気付いただろう。これはmappendがモノイド集合の要素を、その集合に作用する関数に写すことを表している。

さて、自然数の集合を扱っていることを忘れて、たくさんの射――加算器たちをひとかたまりにした、単一の対象だと考えてほしい。モノイドは単一対象の圏だ。実際、monoidという名前は、ギリシャ語で単一を意味するmonoに由来する。すべてのモノイドは、適切な合成規則に従う射の集合を持つ単一対象の圏として表せる。

文字列の連接は興味深いケースだ。なぜなら、右連接器（right appender）と左連接器（left appender、あるいはお好みなら前置器prepender）²⁵を定義する選択肢があるからだ。2つのモデルの合成表は互いに鏡像反転している。「foo」に「bar」を後置するのと「bar」に「foo」を前置するのが同じなのは簡単に納得できるだろう。

圏論的モノイド――単一対象の圏――はどれも二項演算を伴う集合としてのモノイドを一意に定義するのか、という疑問を持つかもしれない。単一対象の圏からは常に集合を抽出できることが分かる。その集合は射――この例では加算器――の集合だ。言い換えれば、圏$\mathbf{M}$内の単一対象$m$についてhom集合$\mathbf{M}(m, m)$ が得られるということだ。この集合における二項演算は簡単に定義できる。2つの集合要素のモノイド的な積は、それらに対応する射を合成したものに対応する要素だ。つまり、$\mathbf{M}(m, m)$ の2つの要素が与えられ、それらに対応する射が$f$と$g$だとすると、それらの積は合成$f \circ g$に対応する要素となる。この合成は常に存在する。なぜなら、射の始点と終点が同じ対象だからだ。また、圏の規則より、結合律も満たす。恒等射はこの積の中立元だ。このように、圏論的モノイドからは常に集合論的モノイドを復元できる。どこからどう見てもそれらは同一だ。

数学者が補足すべき箇所は、射は必ずしも集合を形成しないということだけだ。圏の世界には集合よりも大きなものがある。任意の2つの対象間の射が集合を形成する圏は、局所的に小さい、と呼ばれる。約束どおり、私はそのような些細なことはほとんど無視するが、念のため言及すべきだと考えた。

hom集合の要素は、合成律に従う射とも、ある集合内の点とも見なせる。圏論における多くの興味深い現象はこの事実に根ざしている。ここで、$\mathbf{M}$の射の合成は、集合$\mathbf{M}(m, m)$ でのモノイド的な積に変換される。

3.6 課題

1. 以下から自由圏を生成せよ：

   1. 1つのノードを持ち、辺のないグラフ
   2. 1つのノードと1つの（有向）辺を持つグラフ（ヒント：この辺は自身と合成できる）
   3. 2つのノードと、それらの間の（有向）辺を1つ持つグラフ
   4. 1つのノードと、アルファベットa, b, c $\ldots$ 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! ");
}

この関数は純粋で、副作用はなく、同じ引数で呼び出されるたびに同じペアを返し、必要ならメモ化できる。ただし、ログには累積的な性質があるので、特定の呼び出しにつながる可能性のあるすべての履歴をメモ化する必要があるだろう。別々のメモエントリーになるのは：

negate(true, "It was the best of times. ");

と

negate(true, "It was the worst of times. ");

などだ。

これもライブラリ関数のインターフェースとしてはあまり適していない。戻り値が文字列を含むことについては、呼び出し元は無視してよいので、大きな負担ではない。一方で、入力として文字列を渡す必要があるのについては、不便かもしれない。

同じことをもっと面倒なしにやる方法はないのだろうか？　関心事を分離する方法はあるだろうか？　この単純な例では、関数negateの主な目的は、あるブール値を別のブール値に変換することだ。ログ生成は二次的なものだ。確かに、ログに記録されるメッセージは関数固有だが、それらのメッセージを1つの連続したログに集約する作業は別の関心事だ。この関数には文字列を生成してほしいが、ログの生成とは分離したい。妥協案はこうだ：

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

このアイデアは、ログを関数呼び出しの間で集約する、というものだ。

どうすればこうできるか確認するために、もう少し現実的な例に切り替えよう。小文字を大文字に変換するような、文字列を取って文字列を返す関数があるとする：

string toUpper(string s) {
    string result;
    int (*toupperp)(int) = &toupper; // toupperはオーバーロードされている
    transform(begin(s), end(s), back_inserter(result), toupperp);
    return result;
}

さらに、文字列を空白区切りで分割して文字列のvectorにする別の関数があるとする。

vector<string> toWords(string s) {
    return words(s);
}

実際の作業は補助関数wordsで行われる。

vector<string> words(string s) {
    vector<string> result{""};
    for (auto i = begin(s); i != end(s); ++i)
    {
        if (isspace(*i))
            result.push_back("");
        else
            result.back() += *i;
    }
    return result;
}

関数toUpperとtoWordsを修正して、通常の戻り値の上にメッセージ文字列を背負わせるようにしたい。

これらの関数の戻り値を「装飾」していこう。総称的な方法で、テンプレートWriterを定義しよう。このテンプレートは、最初の成分が任意の型Aの値で、2番目の成分が文字列であるペアをカプセル化する：

template<class 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つの関数を合成することで、文字列を大文字にして単語に分割し、また同時にそれらのログを生成するという、別の装飾された関数にしたい。その方法は次のとおりだ。

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圏

いくつかの追加機能を背負わせるために関数群の戻り値の型を装飾するというアイデアは、非常に実りの多いものだと分かった。さらに多くの例をこれから見ることになるだろう。その出発点は、いつもの型と関数の圏だ。対象は型のままにしておくが、射は装飾された関数になるように再定義する。

たとえば、intからboolへの関数isEvenを装飾したいとする。それを装飾された関数で表される射に変換する。重要なのは、装飾された関数は次のようなペアを返すにもかかわらず、この射は相変わらず対象intとboolの間の射と見なされる、ということだ：

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

圏の規則によれば、この射は対象boolから何かに向かう別の射と合成できるはずだ。具体的には、先ほどのnegateと合成できるはずだ：

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

明らかに、入力と出力の不一致のせいで、これら2つの射は通常の関数合成と同じようには合成できない。それらの合成はもっとこんな風になるはずだ：

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);
}

こうして、我々が構築している新しい圏における2つの射の合成のレシピができる：

1. 最初の射に対応する装飾された関数を実行する。

2. その結果のペアから第一成分を取り出し、2番目の射に対応する装飾された関数に渡す。

3. 最初の結果の第二成分（文字列）と2番目の結果の第二成分（文字列）を連接する。

4. 2番目の結果の第一成分と連接された文字列を組み合わせた新しいペアを返す。

この合成をC++の高階関数として抽象化したい場合、いま考えている圏での3つの対象に対応する3つの型でパラメーター化されたテンプレートを使わなければならない。そのテンプレートでは、ルール上合成可能な2つの装飾された関数を受け取り、3番目の装飾された関数を返す必要がある：

template<class A, class B, class 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);
    };
}

ここで、前の例に戻り、この新しいテンプレートを使ってtoUpperとtoWordsの合成を実装できる：

Writer<vector<string>> process(string s) {
   return compose<string, string, vector<string>>(toUpper, toWords)(s);
}

composeテンプレートへの型の受け渡しにはまだ多くのノイズがある。これは、戻り値型推論を持つ総称ラムダ関数をサポートするC++14準拠のコンパイラーがあれば回避できる。（このコードはEric Nieblerによる。）

auto const compose = [](auto m1, auto m2) {
    return [m1, m2](auto x) {
        auto p1 = m1(x);
        auto p2 = m2(p1.first);
        return make_pair(p2.first, p1.second + p2.second);
    };
};

この新しい定義では、processの実装は次のように簡略化される：

Writer<vector<string>> process(string s){
   return compose(toUpper, toWords)(s);
}

しかし、まだ完成ではない。この新しい圏における合成を定義したが、恒等射は何だろう？　それらは通常の恒等関数ではない！　それらは、型Aから型Aに戻る射でなければならず、つまり、それらは次の形の装飾された関数であることを意味する：

Writer<A> identity(A);

それらは合成に関する単位元として振る舞う必要がある。合成の定義を見ると、恒等射は引数を変更せずに渡し、ログには空文字列だけを与える必要があるのが分かる：

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

ここで定義した圏が本当に正当な圏であることは簡単に納得できる。特に、ここでの合成が結合性を持つのは自明だ。各ペアの最初の成分で何が起こっているかを見ると、それは単なる通常の関数合成であり、結合的だ。2番目の成分は連接されており、連接も結合的だ。

鋭い読者なら、この構成を文字列モノイドだけでなく、どんなモノイドにも容易に一般化できると気付くだろう。composeの中ではmappendを、identityの中ではmemptyを（+と""の代わりに）使おう。ログ生成を文字列だけに限定する理由はない。優れたライブラリ作成者は、ライブラリを機能させられる最小限の制約を見抜けなくてはならない。ここで、ログ生成ライブラリの唯一の要件は、ログがモノイド性を持つことだ。

4.2 HaskellにおけるWriter

Haskellでは同じことを少し簡潔にやれて、コンパイラーからも多くの支援を受けられる。Writer型を定義することから始めよう：

type Writer a = (a, String)

ここでは単にC++のtypedef（またはusing）に相当する型エイリアスを定義している。型Writerは型変数aによってパラメーター化され、aとStringのペアと等価だ。ペアの構文は最小限だ。2つの項目を括弧で囲み、コンマで区切るだけだ。

射は任意の型からWriter型への関数だ：

a -> Writer b

合成を中置演算子として宣言する。この風変わりな演算子は「魚」と呼ばれることもある：

(>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)

この関数は、それら自体も関数である2つの引数を取り、1つの関数を返す。最初の引数の型は(a -> Writer b)、2番目の引数は(b -> Writer c)、結果は(a -> Writer c)となる。

この中置演算子の定義は次のとおりだ²⁷。2つの引数m1とm2は魚型シンボルの両側に現れる：

m1 >=> m2 = \x ->
    let (y, s1) = m1 x
        (z, s2) = m2 y
    in (z, s1 ++ s2)

結果は、1つの引数xを取るラムダ関数だ。ラムダはバックスラッシュで書かれる――ギリシャ文字の$\lambda$を片脚にしたものと考えてほしい。

let式では補助変数を宣言できる。ここでm1を呼び出した結果は変数のペア(y, s1)にパターンマッチングされ、最初のパターンからの引数yでm2を呼び出した結果は(z, s2)にマッチングされる。

Haskellでは、C++でアクセッサーが使われるのとは違って、ペアをパターンマッチするのが一般的だ。それ以外は、2つの実装はほぼ直接的に対応している。

let式全体の値はin節で指定される。ここでは、最初の要素がzで、2番目の要素が2つの文字列の連接s1 ++ s2であるペアだ。

この圏の恒等射も定義し、returnと呼ぶことにする²⁸。そう呼ぶ理由は後で明らかになる。

return :: a -> Writer a
return x = (x, "")

完全を期すために、装飾された関数upCaseとtoWordsのHaskell版を用意しよう：

upCase :: String -> Writer String
upCase s = (map toUpper s, "upCase ")

toWords :: String -> Writer [String]
toWords s = (words s, "toWords ")

関数mapはC++のtransformに対応する。式map toUpperは文字関数toUpperを文字列sに適用する。補助関数wordsは標準のPreludeライブラリで定義されている。

最後に、2つの関数の合成はfish演算子の助けを借りて達成される：

process :: String -> Writer [String]
process = upCase >=> toWords

4.3 クライスリ圏

この圏は私がこの場で発明したのではないことに、もう気付いているかもしれない。これはいわゆるクライスリ圏の一例で、モナドに基づく圏だ。モナドについてはまだ議論する準備ができていないが、モナドで何ができるのかを少しあなたに伝えたかったのだ。我々の限定された目的に関しては、クライスリ圏は、背後にあるプログラム言語の型を対象として持っている²⁹。型$A$から型$B$への射は、$A$を取る関数であり、特定の装飾によって$B$から派生した型を返す。個々のクライスリ圏は、そのような射を合成する個別の方法や、その合成に関する恒等射を定義している。（不正確な用語である「装飾」は、圏論における自己関手という概念に対応していることが後で分かるだろう。）

この章でクライスリ圏の基礎として使ったモナドはwriterモナドと呼ばれ、関数の実行をログに記録したりトレースしたりするために使われる。また、純粋な計算に副作用を埋め込むための、より汎用的なメカニズムの例でもある。これまで見てきたように、プログラミング言語の型と関数は、（いつもどおりボトムは無視して）集合の圏でモデル化できる。ここでは、そのモデルをわずかに異なる圏へと拡張した。すなわち、装飾された関数によって射が表現され、それらを合成した関数がひとつの関数の出力を別の関数の入力に渡す以上のことを行う圏だ。このクライスリ圏ではもうひとつ使える自由度がある。合成そのものだ。それはまさに、命令型言語においては副作用を用いて従来は実装されてきたようなプログラムに、簡潔な表示的意味を与えられるようにする自由度だと分かる。

4.4 課題

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

template<class 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の実装だ：

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を実装せよ。

5 積と余積

古代ギリシアの劇作家のエウリーピデースは「人間は、喜んで交際している仲間たちと異なるところがない」と言った³⁰。我々は人間関係によって定義される。これほど圏論に当てはまる言葉はない。圏の中の特定の対象を選び出すには、他の対象（およびそれ自身）との関係性のパターンを記述するしかない。それらの関係性は射によって定義される。

圏論では、普遍的構成 (universal construction) と呼ばれる、対象をその関係性によって定義するための構成法がよく現れる。そのための方法の1つとしては、対象と射から構成された特定の形のパターンを選び、圏に出現するそのパターンをすべて探すことが挙げられる。そのパターンが十分に一般的で、圏が大きい場合、該当するものが山ほど出てくるだろう。秘訣は、該当したものに対するある種の順位付けを確立し、最適と考えられるものを選択することだ。

このプロセスはウェブ検索のやり方を思い起こさせる。クエリはパターンのようなものだ。非常に一般的なクエリなら、再現率 (recall) が高く、すなわちヒットする数が多い。関連性があるものもあれば、そうでないものもあるだろう。無関係なヒットを削除するには、クエリを絞り込む。これにより精度 (precision) が向上する。最終的に、検索エンジンは検索結果を順位付けして、うまくいけば、あなたが興味のある結果がリストの一番上に表示される。

5.1 始対象

最も単純な形は単一の対象だ。明らかに、この形の実例は、特定の圏にある対象と同じ数だけ存在する。それでは候補が多すぎる。ある種の順位付けを確立し、この階層のトップにある対象を見つける必要がある。我々が自由に使える唯一の手段は射だ。射を矢印として捉えるなら、矢印の全体的な総フローが、圏の一方の端から他方の端へと存在しうる。これは半順序などの順序付けられた圏に当てはまる。$a$から$b$へ向かう矢印（射）が存在するなら、対象$a$は対象$b$よりも「始め」だとして、対象の優先順位の概念を一般化できる。次に、唯一の始対象を、他のすべての対象に向かう射を持つものとして定義する。もちろん、そのような対象が存在する保証はない。だが、それについては大丈夫だ。より大きな問題は、そのような対象が多すぎるかもしれないことだ。再現率は高いが、精度を欠いている。解決策は、順序圏からヒントを得ることだ。それらの圏では、任意の2つの対象の間に高々1つの射しかない。そのため、別の対象以下となる方法は1つしかない。これは始対象の次のような定義につながる：

始対象 (the initial object) とは、圏内の任意の対象に対し、そこへ向かう射をちょうど1つだけ持つ対象である。

それでも、始対象が（存在するにしても）一意だとは保証されない。しかし、それは次善のものを保証する。同型を除いて一意 (uniqueness up to isomorphism) という性質だ。同型は圏論では非常に重要なので、すぐに説明する。差し当たっては、同型を除いて一意という性質が始対象の定義における “the” の使用を正当化するのを認めることにしよう。

以下にいくつかの例を示す。半順序集合（partially ordered set、しばしばposetとも）では最小元が始対象となる。始対象を持たない半順序集合もある。たとえば、すべての整数の集合（正の数も負の数も含む）で、小なりイコール関係を射とするものだ。

集合と関数の圏では、始対象は空集合だ。空集合はHaskellの型Voidに対応し（C++には対応する型は存在しない）、Voidから他の型への一意な多相関数はabsurdと呼ばれていたのを思い出してほしい。

absurd :: Void -> a

Voidを型の圏における始対象にしているのは、この射の族なのだ。

5.2 終対象

引き続き単一対象パターンを扱うが、対象の順位付け方法を変更しよう。$b$から$a$への射がある場合、対象$a$は対象$b$よりも「終わりの側」と言える（方向が逆になっていることに注意してほしい）。探したいのは、圏のどの対象よりも終わりの側となる対象だ。再び、一意性を主張することになる：

終対象 (the terminal object) とは、圏内のどの対象からもちょうど1つの射しか来ない対象である。

繰り返しになるが、終対象は同型を除いて一意だ。これについてはすぐ後で説明する。まずは、いくつかの例を見てみよう。半順序集合では、終対象があれば、それが最大元だ。集合の圏では、終対象は単元集合だ。単元集合についてはすでに説明した。単元集合は、C++ではvoid型に対応し、Haskellではunit型()に対応する。この型が持つ唯一の値は、C++では暗黙的だが、Haskellでは明示的に()で表される。また、任意の型からunit型へのちょうど1つの純粋関数が存在することも確認した：

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

これで、終対象のすべての条件が満たされた。

この例では、射の一意性という条件が決定的に重要であることに注意してほしい。なぜなら、すべての集合から入ってくる射を持つ他の集合（実際には、空集合を除くすべての集合）が存在するからだ。たとえば、すべての型に対して定義されたブール値関数（述語）がある：

yes :: a -> Bool
yes _ = True

しかし、Boolは終対象ではない。すべての型に対して、少なくとももう1つのBool値関数がある（Voidに対してはどちらの関数もabsurdと等しくなるので除く）：

no :: a -> Bool
no _ = False

一意性を主張することで、終対象の定義を1つの型だけに絞り込むのにちょうど良い精度が得られる。

5.3 双対性

始対象と終対象の定義の対称性には注目せずにいられないだろう。両者の唯一の違いは、射の方向だった。どの圏$\mathbf{C}$に対しても、すべての射を逆にするだけで反対圏 (opposite category) $\mathbf{C}^\mathit{op}$を定義できると分かる³¹。 反対圏は、同時に合成を再定義しさえすれば、圏としての要件をすべて自動的に満たす。もとの射$f \Colon a \to b$と$g \Colon b \to c$が$h=g \circ f$によって$h \Colon a \to c$へと合成される場合、逆の射$f^\mathit{op} \Colon b \to a$と$g^\mathit{op} \Colon c \to b$は$h^\mathit{op} = f^\mathit{op} \circ g^\mathit{op}$によって$h^\mathit{op} \Colon c \to a$へと合成される³²。 そして、恒等射を逆にすることは、（駄洒落に注意！）no-opだ。

双対性は圏の非常に重要な特性だ。圏論を扱うすべての数学者の生産性を倍増させるからだ。思いつくすべての構成にはその反対があり、そして、証明するすべての定理について無料でもう1つ付いてくる。反対圏の構成にはしばしば「余」(co) が前置され、積と余積、モナドとコモナド、錐と余錐、極限と余極限などがある。ただし、射を2回反転させればもとの状態に戻るので、ココモナドはない。

そのため、終対象は反対圏の始対象だと言える。

5.4 同型

プログラマーである我々は、等しさを定義することが簡単な作業ではないことをよく知っている。2つのオブジェクトが等しいとはどういう意味だろう？　メモリー内の同じ場所を占有する必要があるだろうか（ポインターの等しさ）。あるいは、すべての要素の値が同じであれば十分だろうか？　2つの複素数の一方を実部と虚部で表し、もう一方を絶対値と偏角で表すしたとき、それらは等しいだろうか？　数学者たちが等しさの意味を解明済みだろう、と思うかもしれないが、そうではない。数学においても、等しさには複数の競合する定義があるという、同じ問題がある。命題として表される等しさ (propositional equality)、内包的な 等しさ (intensional equality)、外延的な等しさ (extensional equality)、ホモトピー型理論における道 (path) としての等しさがある。そして同型 (isomorphism) のより弱い概念、さらには等価性 (equivalence) のより弱い概念もある。

直観としては、同型の対象は同じように見える。つまり、同じ形をしている。これは、1対1写像により、ある対象のどの一部も別の対象のどこか一部に対応することを意味する。我々の道具で調べうる限り、2つの対象はお互いの完全なコピーだ。数学的には、対象$a$から対象$b$への写像があり、対象$b$から対象$a$への写像があり、それらが互いの逆であることを意味する。圏論では、写像を射に置き換える。同型射は可逆な射、つまり一方が他方の逆になっているような射のペアだ。

逆であるということは合成と恒等射によって理解できる。射$g$が射$f$の逆であるのは、それらの合成が恒等射となる場合だ。それら2つの射は、合成する方法が2つあるので、実際には2つの等式で表される：

f . g = id
g . f = id

始（終）対象が同型を除いて一意だと言ったとき、2つの始（終）対象は同型だということを意味していた。これは簡単に理解できる。2つの始対象$i_{1}$と$i_{2}$があるとしよう。$i_{1}$が始対象であるため、$i_{1}$から$i_{2}$への一意な射$f$が存在する。同様に、$i_{2}$が始対象であるため、$i_{2}$から$i_{1}$への一意な射$g$が存在する。これらの2つの射を合成すると何になるだろう？

合成$g \circ f$は、$i_{1}$から$i_{1}$への射でなければならない。しかし、$i_{1}$は始対象なので、$i_{1}$から$i_{1}$へ向かう射は1つだけだ。圏の中なので、$i_{1}$から$i_{1}$への恒等射があるのは分かっている。候補は1つだけなので、$g \circ f$はそれでなければならない。したがって、$g \circ f$は恒等射と等しくなる。同様に、$f \circ g$は恒等射と等しくなければならない。$i_{2}$から$i_{2}$に戻る射は1つしかないからだ。これは、$f$と$g$が互いの逆でなければならないことを証明している。したがって、任意の2つの始対象は同型だ。

この証明では、始対象からそれ自体への射の一意性を用いたことに注意してほしい。そうしなければ「同型を除いて」の部分は証明できない。しかし、なぜ$f$と$g$の一意性が必要なのだろうか。始対象は同型を除いて一意なだけでなく、一意な同型を除いて一意だからだ。原則として、2つの対象間には複数の同型が存在する可能性があるが、ここではそうではない。この「一意な同型を除いて一意という性質」は、すべての普遍的構成の重要な特性だ。

5.5 積

次の普遍的構成は積 (product) に関するものだ。2つの集合のデカルト積 (Cartesian product) が何なのかは知っている。ペアからなる集合だ。しかし、集合の積とそれを構成する集合を結びつけるパターンは何だろう？　それが分かれば、他の圏にも一般化できるはずだ。

唯一言えるのは、積から各構成要素への射影 (projection) という関数が2つある、ということだ。Haskellでは、これら2つの関数はfstとsndと呼ばれ、それぞれペアの第一要素と第二要素を抜き出す：

fst :: (a, b) -> a
fst (x, y) = x

snd :: (a, b) -> b
snd (x, y) = y

ここで、関数は引数に対するパターンマッチングによって定義されている。パターン(x, y)は任意のペアにマッチし、要素を変数xとyに抽出する。

これらの定義はワイルドカードを使ってさらに単純化できる：

fst (x, _) = x
snd (_, y) = y

C++では、たとえば次のようなテンプレート関数が使われるだろう：

template<class A, class B>
A fst(pair<A, B> const & p) {
    return p.first;
}

この非常に限られているように一見思える知識をもって、2つの集合（$a$と$b$）の積の構成につながる、集合の圏における対象と射のパターンを定義してみよう。このパターンは対象$c$と、それぞれ$a$と$b$に接続される2つの射$p$と$q$とで構成される：

p :: c -> a
q :: c -> b

このパターンに一致するすべての$c$が積の候補となる。それは大量にあるかもしれない。

たとえば、構成要素として、2つのHaskellの型IntとBoolを選択してみて、それらの積の候補を挙げてみよう。

1番目の候補はIntだ。IntはIntとBoolの積の候補となるだろうか？　そう、候補となる――その射影はこうなる：

p :: Int -> Int
p x = x

q :: Int -> Bool
q _ = True

これはかなり酷いが、基準を満たしている。

2番目の候補は(Int, Int, Bool)だ。要素が3つの組、すなわち3つ組だ。これを正当な候補にする2つの射を以下に示す（ここでは3つ組に対してパターンマッチングを使っている）：

p :: (Int, Int, Bool) -> Int
p (x, _, _) = x

q :: (Int, Int, Bool) -> Bool
q (_, _, b) = b

1番目の候補は狭すぎ、積のIntの次元だけをカバーしている。一方で、2番目の候補は大きすぎ、Intの次元が重複してしまっている。

しかし、この普遍的構成の別の部分である順位付けについてはまだ調べていない。そこで、パターンの2つの例を比較できるようにしたい。つまり、対象の1つの候補$c$とその2つの射影$p$および$q$を、別の対象の候補$c'$とその2つの射影$p'$および$q'$と比較したい。$c'$から$c$への射$m$がある場合に、$c$は$c'$よりも「優れている」と言いたいのだが、それではあまりにも弱い。それに加えて、$c$の射影たちが$c'$の射影たちよりも「優れている」、すなわち「より普遍的」であってほしい。つまり、射影$p'$と$q'$は、$p$と$q$から$m$を使って再構成できるということだ：

p' = p . m
q' = q . m

別の観点でこれらの等式を見ると、$m$は$p'$と$q'$を分解 (factorize) している。これらの等式が自然数について成り立ち、ドットが乗算であると仮定すると、$m$は$p'$と$q'$に共通な因数だ。

ある種の直観を築くために、ペア型(Int, Bool)およびその正統な射影fstとsndが、前に提示した2つの候補より本当に優れていることを示そう。

1番目の候補に対する写像mは次のようになる：

m :: Int -> (Int, Bool)
m x = (x, True)

実際、2つの射影pとqは次のように再構成できる：

p x = fst (m x) = x
q x = snd (m x) = True

2番目の例のmも同様に一意に定まる：

m (x, _, b) = (x, b)

(Int, Bool)が2つの候補のどちらよりも優れていることを示せた。その逆がなぜ真ではないのかを見てみよう。pとqからfstとsndを再構築するのに役立つm'を見つけられるだろうか？

fst = p . m'
snd = q . m'

1番目の例では、qは常にTrueを返す。しかし、第2要素がFalseであるペアが存在するのは分かっている。したがって、qからはsndを再構築できない。

2番目の例は別物だ。pまたはqを経た後でも十分な情報が保持される。しかし、fstとsndを分解する方法が複数ある。pとqはどちらも3つ組の第2要素を無視するので、m'はそこに何でも入れられる。たとえば：

m' (x, b) = (x, x, b)

あるいは：

m' (x, b) = (x, 42, b)

などを定義できる。

以上すべてをまとめると、2つの射影pとqを持つ任意の型cについて、それらの射影を分解する一意なmがcからデカルト積(a, b)へと存在する。実際には、pとqを組み合わせてペアにしているだけだ：

m :: c -> (a, b)
m x = (p x, q x)

これによってデカルト積(a, b)がベストマッチとなり、すなわち、この普遍的構成が集合の圏で機能することを意味する。この構成は任意の2つの集合の積を選ぶ。

さて、集合のことは忘れて、同じ普遍的構成を使って任意の圏にある2つの対象の積を定義しよう。そのような積が必ず存在するわけではないが、存在する場合は、一意な同型を除いて一意だ。

2つの対象$a$と$b$の積とは、2つの射影を伴う対象$c$であり、別の任意の対象$c'$が伴う2つの射影について、それらを分解する$c'$から$c$への一意な射$m$が存在するものを言う。

2つの候補から分解関数mを生成する（高階）関数は、factorizerと呼ばれることもある。この例では、次の関数になる：

factorizer :: (c -> a) -> (c -> b) -> (c -> (a, b))
factorizer p q = \x -> (p x, q x)

5.6 余積

圏論のすべての構成と同じく、積にも双対があり、余積 (coproduct) と呼ばれる。積のパターンの射を逆にすると、2つの入射 (injection) iとjを伴う対象cになる³³。すなわち、$a$と$b$から$c$への射だ。

i :: a -> c
j :: b -> c

順位付けも逆転している：対象$c$は、もし$c$から$c'$への射$m$が単射を分解するなら、$i'$と$j'$の単射を伴う対象$c'$よりも「優れて」いる。

i' = m . i
j' = m . j

「最も優れた」対象は、そこから他のどのパターンへも一意な射を持つもので、余積と呼ばれ、存在する場合は、一意な同型を除いて一意だ。

2つの対象$a$と$b$の余積とは、2つの単射を伴う対象$c$であり、別の任意の対象$c'$が伴う2つの単射について、それらを分解する$c$から$c'$への一意な射$m$が存在するものを言う。

集合の圏では、余積は2つの集合の非交和 (disjoint union) だ。$a$と$b$の非交和の要素は、$a$の要素か$b$の要素のどちらかだ。2つの集合が重なる場合、非交和には共通部分のコピーが2つ含まれる。非交和の要素は起源を示す識別子でタグ付けされていると見なせる。

プログラマーにとっては、型の観点から余積を理解する方が簡単だ。それは2つの型からなるタグ付き和 (tagged union) だ。C++がサポートしている共用体 (union) はタグ付けされていない。つまり、プログラム内では共用体のどのメンバーが有効であるかを何らかの方法で追跡しなければならないということだ。タグ付き共用体を作成するには、タグ――列挙型――を定義して共用体と結びつける必要がある。たとえば、intとchar const*のタグ付き共用体は次のように実装できる：

struct Contact {
    enum { isPhone, isEmail } tag;
    union { int phoneNum; char const * emailAddr; };
};

これに対する2つの入射は、コンストラクターとしても、関数としても実装できる。たとえば、最初の単射を関数PhoneNumとして実装するとこうなる：

Contact PhoneNum(int n) {
    Contact c;
    c.tag = isPhone;
    c.phoneNum = n;
    return c;
}

これはContactに整数を注入 (inject) する。

タグ付き共用体はvariantとも呼ばれ、boostライブラリに非常に汎用的なboost::variantという実装がある³⁴。

Haskellでは、データ構成子を縦棒で区切ることで、任意のデータ型をタグ付き和にまとめられる。Contactの例だと次のような宣言になる：

data Contact = PhoneNum Int | EmailAddr String

ここで、PhoneNumとEmailAddrは、構成子（入射）としても、パターンマッチングのタグとしても機能する（これについては後で詳しく説明する）。たとえば、電話番号を使って連絡先を構成する方法はこうなる：

helpdesk :: Contact
helpdesk = PhoneNum 2222222

正統な実装では、積がプリミティブなペアとしてHaskellに組み込まれているのに対し、余積はEitherと呼ばれるデータ型であり、標準のPreludeで次のように定義されている：

data Either a b = Left a | Right b

これはaとbの2つの型によってパラメーター化され、2つの構成子を持つ。すなわち、型aの値を取るLeftと、型bの値を取るRightだ。

積についてfactorizerを定義したのと同様に、余積についても定義できる。余積の型の候補cと2つの入射の候補iとjについて、Eitherに対するfactorizerは次の分解関数を生成する：

factorizer :: (a -> c) -> (b -> c) -> Either a b -> c
factorizer i j (Left a)  = i a
factorizer i j (Right b) = j b

5.7 非対称性

これまでに2組の双対の定義を見てきた。終対象の定義は、始対象の定義から射の方向を逆にすることで得られ、余積の定義は積の定義から得られる。しかし、集合の圏では、始対象と終対象は大きく異なり、余積と積は大きく異なる。後述するように、積は乗算のように振る舞い、終対象は1の役割を果たし、余積は和のように振る舞い、始対象は0の役割を果たす。特に、有限集合の場合、積のサイズは個々の集合のサイズの積であり、余積のサイズはサイズの合計だ。

これは集合の圏が射の反転に関して対称でないことを示している。

空集合については、どの集合に対しても一意な射（absurd関数）がある一方で、戻ってくる射はないことに注意してほしい^{[訳注：ただし、空集合自身から戻ってくる恒等射（これもabsurd関数）は存在する。]。単元集合では、どの集合からも一意な射が来るうえに、（空集合を除く）すべての集合へ向かう外向きの射もある。これまで見てきたように、終対象から発するこれらの射}[訳注：終対象の定義では終対象へ向かう射についてしか述べていないので、終対象から他の対象へ向かう射が存在するのは何の問題もない。]は、他の集合の要素を選択するのに非常に重要な役割を果たしている（空集合には要素がないので、選択するものは何もない）。

単元集合と積の関係は、余積とは全く違う。unit型()で表される単元集合を、積パターンのもう1つの――非常に劣った――候補として使うことを考えてみてほしい。それを2つの射影pとq、すなわち単元集合から各構成要素の集合への関数として実装してみよう。それらは具体的な要素をそれぞれの集合から選択する。積は普遍的なので、ここでの候補の単元集合から積への（一意な）射mも存在する。この射は積の集合から要素を選択する。つまり、具体的なペアを選択する。さらに、次の2つの射影を分解する：

p = fst . m
q = snd . m

単元集合の唯一の要素である値()に作用させると、これら2つの式は次のようになる：

p () = fst (m ())
q () = snd (m ())

m ()はmによって選択された積の要素なので、これらの式は、第1の集合からpによって選択された要素p ()が、mによって選択されたペアの第1要素であることを示す。同様に、q ()は第2要素に等しい。これは、積の要素は構成要素の集合からの要素のペアであるという理解と完全に一致している。

余積にはそのような単純な解釈はない。単元集合を余積での候補として要素を抽出しようと試みることもできるが、2つの射影がそこから出てくるのではなく、2つの入射がそこに入ることになる。それらはその起源について何も教えてくれないだろう（実際、入力パラメーターが無視されるのを見てきた）。また、余積から単元集合への一意な射についても同様だろう。集合の圏は、始対象の向きから見たときと終対象から見たときとでは全く違って見える。

これは集合の固有の特性ではなく、$\mathbf{Set}$で射として使う関数の特性だ。関数は（一般に）非対称だ。説明しよう。

関数は、その始域 (domain) のすべての要素に対して定義する必要がある（プログラミングでは全関数 (total function) と呼ぶ）。しかし、終域 (codomain) 全体を網羅する必要はない。すでにその極端な例をいくつか見てきた。単元集合からの関数たち――終域内の1つの要素だけを選択する関数たちのことだ。（実際に、空集合からの関数は本当に極端だ。） 始域のサイズが終域のサイズよりもずっと小さい場合、我々はよく、始域を終域に埋め込むような関数を思い浮かべる。たとえば、単元集合からの関数は、その1つの要素を終域に埋め込むものだと考えられる。私はそれらを埋め込み (embedding) 関数と呼んでいるが、数学者は反対のものに名前を付ける方を好む。つまり、終域をきっちり満たす関数を全射 (surjective) または上への (onto) 関数と呼ぶ。

非対称性のもう1つの原因は、関数が始域の複数の要素を終域の1つの要素に写せることだ。そういった関数はそれらの要素を潰す (collapse) ことができる。極端な例としては、集合全体を単元集合に写す関数が挙げられる。これまでに、まさにそれを行う多相unit関数を見てきた。合成すると、より酷く潰すことにしかならない。潰す関数2つの合成は、個々の関数よりもさらに潰すことになる。数学者は潰さない関数を単射 (injective) または1対1 (one-to-one) という名前で呼ぶ。

当然、埋め込みも潰しもしない関数もある。それらは全単射 (bijection) と呼ばれ、可逆なので真に対称だ。集合の圏では、同型は全単射と同じだ。

5.8 課題

1. 終対象が一意な同型を除いて一意であることを示せ。

2. 半順序集合において2つの対象の積は何か？　ヒント：積の普遍的構成を使う。

3. 半順序集合において2つの対象の余積は何か？

4. HaskellのEitherに相当するものを、（Haskell以外の）好きな言語で総称型として実装せよ。

5. Eitherが、次の2つの単射を伴うintよりも「優れた」余積であることを示せ。

   int i(int n) { return n; }
   int j(bool b) { return b? 0: 1; }

   ヒント：関数

   int m(Either const & e);

   を、iとjを分解するように定義する。

6. 前の問題の続き：iとjという2つの単射を伴うintがEitherよりも「優れている」ことはあり得ないと主張するにはどうすればよいか？

7. さらに続き：次の単射についてはどうか？

   int i(int n) {
       if (n < 0) return n;
       return n + 2;
   }
   int j(bool b) { return b? 0: 1; }

#. intとboolの余積の候補として、Eitherへの射を複数許容するという理由でEitherより劣るものを挙げよ。

5.9 参考文献

1. CatstersのProducts and Coproducts³⁵の動画

6 シンプルな代数的データ型

型を組み合わせる2つの基本的な方法として、積と余積を使う方法を見たところだ。日常のプログラミングにおける多くのデータ構造は、実はこの2つのメカニズムだけを使って構築できる。この事実は重要かつ有用な帰結をもたらす。データ構造の性質の多くは合成可能だということだ。たとえば、基本型の値が等しいかどうか比較する方法を知っていて、それらの比較を積と余積に相当する型に一般化する方法を知っていれば、自動的に複合型の等値演算子を導出できる。Haskellでは、等しさの検査、大小比較、文字列への変換、文字列からの変換などを、複合型の大きな部分集合に対して自動的に導出できる。

次に、直積型 (product type)³⁶ と直和型 (sum type) がプログラミングに現れる様子を詳しく見てみよう。

6.1 直積型

2つの型の直積（直積型）のプログラム言語における正統な実装はペアだ。Haskellではペアはプリミティブな型構成子 (type constructor) だ。C++では比較的複雑なテンプレートとして標準ライブラリで定義されている。

ペアは厳密には可換ではない。(Int, Bool)型のペアは、同じ情報を保持していても、ペア(Bool, Int)型のペアには置き換えられない。しかし、それらは同型を除いて可換だ。同型写像はswap関数（それ自身の逆関数）によって与えられる：

swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)

これら2つのペア型は、単に同じデータを格納するために異なるフォーマットを使っていると見なせる。ビッグエンディアンとリトルエンディアンのようなものだ。

ペアの中にペアをネストすれば任意の個数の型の直積を作れるが、もっと簡単な方法がある。ネストされたペアは組 (tuple) と等価なのだ。これは、ペアをネストする様々な方法が同型であるという事実からの帰結だ。3つの型a、b、cを順に積にする場合、次の2つの方法がある：

((a, b), c)

あるいは

(a, (b, c))

これらは型が異なる。つまり、一方の型の引数を期待する関数に他方の型の値を渡すことはできない。しかし、これらの要素は1対1で対応している。そのため、一方を他方に写す関数が存在し：

alpha :: ((a, b), c) -> (a, (b, c))
alpha ((x, y), z) = (x, (y, z))

そして、その関数は逆関数を持つ：

alpha_inv :: (a, (b, c)) -> ((a, b), c)
alpha_inv  (x, (y, z)) = ((x, y), z)

したがって、この関数は同型写像だ。データは同じで再パッケージ化するための方法が違うにすぎない。

直積型の生成は、型上の二項演算として解釈できる。この観点から見ると、上記の同型は、モノイドで見た結合律 (associativity law) に非常によく似ている： $$(a * b) * c = a * (b * c)$$ ただし、モノイドの場合は積を合成する2つの方法が等しかったのに対して、ここでは「同型を除いて」等価であるにすぎない。

同型を認めて、厳密な等しさに固執しないならば、さらに進んで、1が乗算の単位元であるのと同じようにunit型()が積の単位元であるのを示せる。実際、ある型aの値とunit型の値を組み合わせても何の情報も追加されない。型：

(a, ())

はaと同型だ。対応する同型写像はこのようになる：

rho :: (a, ()) -> a
rho (x, ()) = x

rho_inv :: a -> (a, ())
rho_inv x = (x, ())

これらの観察は、$\mathbf{Set}$（集合の圏）はモノイダル圏 (monoidal category) である、と述べることによって形式化できる。それは、対象を（ここではデカルト積で）乗算できるという意味で、モノイドでもある圏だ。モノイダル圏についてさらに説明しよう。完全な定義は将来的に示す。

Haskellには直積型を定義するもっと一般的な方法がある。特に、すぐ後で説明するとおり、直和型と組み合わされたときにはっきりする。その方法は複数の引数を持つ名前付き構成子を使うというものだ。たとえば、ペアは次のようにも定義できる：

data Pair a b = P a b

ここで、Pair a bは他の2つの型aとbによってパラメーター化された型の名前であり、Pはデータ構成子の名前だ。ペア型を定義するには型構成子Pairに2つの型を渡す。適切な型の2つの値を構成子Pに渡すことで、ペア値を構成する。たとえば、値stmtをStringとBoolのペアとして定義したとする：

stmt :: Pair String Bool
stmt = P "This statements is" False

最初の行は型シグネチャーだ³⁷。そこでは、型構成子Pairが、そのPairの総称定義のaとbをそれぞれStringとBoolで置き換えた形で使われている。2行目では、具体的な文字列と具体的なブール値をデータ構成子Pに渡すことで、実際の値を定義している。型構成子は型を構成するために使われ、データ構成子は値を構成するために使われる。

Haskellでは型構成子とデータ構成子の名前空間が分離されているため、次のように両方に同じ名前が使われていることがよくある：

data Pair a b = Pair a b

さらに目を細めれば、組み込みのペア型をこの種の宣言のバリエーションとして見ることもできる。組み込みのペア型においては、Pairという名前が(,)という二項演算子で置き換わっている。実際、(,)を他の名前付き構成子と同じように扱い、前置記法を使ってペアを作成できる：

stmt = (,) "This statement is" False

同様に、(,,)を使って3つ組を作成する、などもできる。

総称ペアや組を使う代わりに、次のように特定の名前を付けた直積型を定義してもよい：

data Stmt = Stmt String Bool

これは単にStringとBoolの積だが、独自の名前と構成子が与えられている。このスタイルの宣言の利点は、内容は同じでも意味と機能が異なる互いに置き換えられない型を多数定義できることだ。

組や複数の引数を持つ構成子を使ってプログラミングすると、ぐちゃぐちゃになり間違いが生じやすくなる。どの成分が何を表しているかを追うのが大変になるからだ。成分に名前を付ける方が望ましい場合はよくある。名前付きフィールドを持つ直積型は、Haskellではrecord³⁸、Cではstructと呼ばれる。

6.2 レコード

簡単な例を見てみよう。化学元素を記述するために、2つの文字列（名前と元素記号）と整数（原子番号）を組み合わせて1つのデータ構造にしたい。組(String, String, Int)を使い、どの成分が何を表しているかを覚えておくという方法がある。そして、成分はパターンマッチングによって、（HeはHeliumの接頭辞だというように）元素記号が元素名の接頭辞かをチェックする次の関数のように抽出することにしよう：

startsWithSymbol :: (String, String, Int) -> Bool
startsWithSymbol (name, symbol, _) = isPrefixOf symbol name

このコードは間違いが生じやすく、読むのもメンテナンスするのも困難だ。レコードを定義する方がはるかに良い。

data Element = Element { name         :: String
                       , symbol       :: String
                       , atomicNumber :: Int }

これら2つの表現は同型だ。そのことは、互いに逆になっている2つの変換関数から分かる。

tupleToElem :: (String, String, Int) -> Element
tupleToElem (n, s, a) = Element { name = n
                                , symbol = s
                                , atomicNumber = a }

elemToTuple :: Element -> (String, String, Int)
elemToTuple e = (name e, symbol e, atomicNumber e)

レコードのフィールド名は、それらのフィールドにアクセスするための関数としても機能することに注意してほしい。たとえば、atomicNumberはeからatomicNumberフィールドを取得する。つまり、atomicNumberは次のような型の関数として使われる：

atomicNumber :: Element -> Int

Elementについてのレコード構文によって、関数startsWithSymbolはより読みやすくなる：

startsWithSymbol :: Element -> Bool
startsWithSymbol e = isPrefixOf (symbol e) (name e)

関数isPrefixOfをバッククォーテーションで囲んで中置演算子に変換するというHaskellの小技を使えば、まるで英文のように読めるようにさえできる：

startsWithSymbol e = symbol e `isPrefixOf` name e

中置演算子は関数呼び出しよりも優先順位が低いため、この場合は括弧を省略できる。

6.3 直和型

集合の圏の積が直積型のもととなるのと同じように、余積は直和型のもととなる。Haskellにおける直和型の正統な実装は次のようなものだ：

data Either a b = Left a | Right b

また、ペアと同様に、Eitherは（同型を除いて）可換であり、ネストでき、ネストの順序は（同型を除いて）無関係だ。したがって、たとえば、3つ組に相当する和：

data OneOfThree a b c = Sinistral a | Medial b | Dextral c

などを定義できる。

$\mathbf{Set}$は余積に関する（対称）モノイダル圏でもあることが分かる。二項演算の役割を演じるのは非交和であり、単位元の役割を演じるのは始対象だ。型に関しては、モノイダル演算子としてEitherがあり、その中立元として住人³⁹がいない型 (uninhabited type) であるVoidがある。 Eitherは加算、Voidは0と見なせる。実際、直和型にVoidを足しても内容は変わらない。例として：

Either a Void

はaと同型だ。これは、この型のRight版を構成する方法がないためだ。型Voidに値は存在しない。 Either a Voidの唯一の要素は、Left構成子を使って構築されたものであり、単純に型aの値をカプセル化したものだ。したがって、記号的に表すと、$a + 0 = a$となる。

直和型がHaskellではごく普通に使われるのに対し、C++で同等のものである共用体やvariantはあまり使われない。その理由はいくつかある。

まず、最も単純な直和型は単なる列挙であり、C++ではenumを使って実装できる。Haskellの直和型：

data Color = Red | Green | Blue

にC++で相当するものは：

enum { Red, Green, Blue };

だ。もっとシンプルな直和型：

data Bool = True | False

は、C++ではプリミティブboolだ。

値の有無を表す単純な直和型は、C++では、特殊なトリックや「不可能な」値（空文字列・負の数・ヌルポインターなど）を使ってさまざまに実装される。この種のオプション性は、意図的な場合、HaskellではMaybe型を使って表現される：

data Maybe a = Nothing | Just a

Maybe型は2つの型の直和だ。このことは構成子の2つの部分を個々の型に分けると分かる。1つ目は次のようになる：

data NothingType = Nothing

これはNothingという名前の1つの値を持つ列挙だ。言い換えると、これは単元集合であり、unit型()と等価だ。2つ目の部分：

data JustType a = Just a

は、型aを単にカプセル化したものだ。Maybeを次のように書いてもよかっただろう：

type Maybe a = Either () a

より複雑な直和型は、C++ではポインターを使って模擬することが多い。ポインターはヌルとなるか、あるいは特定の型の値を指し示す。たとえば、Haskellで（再帰的な）直和型として定義できるリスト型：

List a = Nil | Cons a (List a)

をC++に変換するには、ヌルポインターのトリックを使って空のリストを実装する：

template<class A>
class List {
    Node<A> * _head;
public:
    List() : _head(nullptr) {}  // Nil
    List(A a, List<A> l)        // Cons
      : _head(new Node<A>(a, l))
    {}
};

Haskellでの2つの構成子NilとConsが、よく似た引数（Nilは空、Consは値1つとリスト1つ）でオーバーロードされた2つのList構成子へと変換されたことに注目してほしい。このListクラスには、直和型の2つの成分を区別するためのタグは必要ない。その代わり、_headに特別なnullptr値を使ってNilを表現する。

だが、HaskellとC++の型の主な違いは、Haskellではデータ構造が不変であることだ。ある特定の構成子を使ってオブジェクトを作成する場合、オブジェクトはどの構成子が使われ、どの引数が渡されたかを永久に記憶する。したがって、Just "energy"として作成されたMaybeオブジェクトがNothingに変わることはない。同様に、空のリストは永久に空であり、3つの要素のリストは常に同じ3つの要素を持つことになる。

この不変性こそが構成を可逆的にする。オブジェクトがあれば、いつでも構成で使われた部品に分解できる。この分解はパターンマッチングで行われ、構成子をパターンとして再利用する。構成子の引数がある場合は、変数（またはその他のパターン）に置き換えられる。

Listデータ型には2つの構成子があるため、どんなListを分解するときもそれらの構成子に対応する2つのパターンを使う。1つは空であるNilリストにマッチし、もう1つはConsで構成されたリストにマッチする。たとえば、複数のListに対する単純な関数の定義は次のとおりだ。

maybeTail :: List a -> Maybe (List a)
maybeTail Nil = Nothing
maybeTail (Cons _ t) = Just t

maybeTailの定義の最初の部分は、Nil構成子をパターンとして使い、Nothingを返す。2番目の部分では、Cons構成子をパターンとして使っている。構成子の最初の引数には興味がないため、ワイルドカードに置き換わっている。Consの2番目の引数は、変数tに束縛される（厳密に言えば一度式に束縛されたら決して変化しないものの、変数と呼ぶことにする）。戻り値はJust tだ。こうして、Listの作成方法に応じて、節の1つに一致するようになった⁴⁰。作成にConsが使われるときは、作成時に渡した2つの引数が取得される（最初の引数は破棄される）。

さらに複雑な直和型は、C++では多相クラス階層を使って実装されている。共通の祖先を持つクラスたちは、1つのバリアント型として理解でき、その中では仮想関数テーブルが隠しタグとして機能する。Haskellでは構成子に対するパターンマッチングおよびパターンごとに特化したコードで行っていることを、C++では仮想関数テーブルのポインターに基づいて仮想関数呼び出しをディスパッチすることで実現している。

C++で共用体が直和型として使われることはめったにない。含められるものに厳しい制限があるからだ。std::stringでさえ、コピーコンストラクターを持っているので、共用体に入れられない。

6.4 型の代数

直積型と直和型を別々に用いても有用なデータ構造をいろいろ定義できるが、真の強みはこの2つを組み合わせることで得られる。合成の力が再び発揮される時がきた。

これまでに分かったことをまとめておこう。型システムの下にある2つの可換モノイド構造を見た。中立元としてVoidを持つ直和型と、中立元として()というunit型を持つ直積型だ。それらを加法や乗法から類推したい。この類推では、Voidは0に対応し、()は1に対応する。

この類推をどこまで拡張できるか見てみよう。例として、0を掛けると0になるだろうか？　言い換えれば、1つの成分がVoidである直積型は、Voidと同型だろうか？　たとえば、IntとVoidのペアを作成できるだろうか？

ペアを作成するには2つの値が必要だ。整数なら簡単だが、型Voidには値がない。したがって、型(a, Void)は、すべての型aについて住人がいない――値を持たない――のでVoidと等価になる。言い換えれば、$a \times 0 = 0$ということだ。

また別の、加算と乗算をつなぐものとして、分配則 (distributive property) がある：

a * (b + c) = a * b + a * c

これは直積型と直和型にも当てはまるだろうか？　そう、当てはまる――いつものように同型を除いて。左辺は次の型に相当する：

(a, Either b c)

また、右辺は次の型に相当する：

Either (a, b) (a, c)

これらをある向きで変換する関数は次のとおりだ：

prodToSum :: (a, Either b c) -> Either (a, b) (a, c)
prodToSum (x, e) =
    case e of
      Left  y -> Left  (x, y)
      Right z -> Right (x, z)

また、その逆向きの変換は次のとおりだ：

sumToProd :: Either (a, b) (a, c) -> (a, Either b c)
sumToProd e =
    case e of
      Left  (x, y) -> (x, Left  y)
      Right (x, z) -> (x, Right z)

case of式は、関数の内部でパターンマッチングを行うために使われる。各パターンの後には矢印と、パターンが一致したときに評価される式が続く。たとえば、次の値を引数としてprodToSumを呼び出すとする。

prod1 :: (Int, Either String Float)
prod1 = (2, Left "Hi!")

case e of内のeはLeft "Hi!"と等しくなる。これはパターンLeft yとマッチし、yに"Hi!"を代入する。xはすでに2とマッチしているので、case of式の結果と関数全体は、期待どおりLeft (2, "Hi!")となる。

この2つの関数が互いの逆関数であることの証明は省くが、よく考えれば分かるだろう。これらは2つのデータ構造の内容を単に再パックしている。データは同じで、フォーマットが異なるだけだ。

数学者たちは、このような絡み合った2つのモノイドに半環 (semiring) という名前をつけている。これは完全な環 (ring) ではない。型の減算は定義できないからだ。そのため、半環は「n (negative) がない環 (ring)」をかけてリグ (rig) と呼ばれることがある。しかし、そのことを除けば、リグを形成する自然数などに関する命題を型に関する命題に変換することによる多くのメリットが得られる。興味深い項目を含む変換表を以下に示す：

リスト型は、非常に興味深いことに、方程式の解として定義される。定義しようとしている型は等式の両辺に現れる：

data List a = Nil | Cons a (List a)

いつもの置換を行い、さらにList aをxに置き換えると、次の式が得られる：

x = 1 + a * x

型の減算や除算はできないので、これは従来の代数的方法では解けない。しかし、置換の連続なら試せる。つまり、ひたすら右辺のxを(1 + a*x)に置き換えては分配則を使う。これによって次の列が得られる：

x = 1 + a*x
x = 1 + a*(1 + a*x) = 1 + a + a*a*x
x = 1 + a + a*a*(1 + a*x) = 1 + a + a*a + a*a*a*x
...
x = 1 + a + a*a + a*a*a + a*a*a*a...

最終的には積（組）の和が無限に続くことになった。これは次のように解釈できる。リストは空集合1か、単元集合aか、ペアa*aか、3つ組a*a*aか、などなど……。まさにそれがリストだ。つまり、aの列だ！

リストについては語るべきことがまだまだある。関手や不動点について学んだ後で、リストやその他の再帰的なデータ構造について再び説明する。

記号変数を使って方程式を解く――これぞ代数だ！　それゆえ、これらの型は代数的データ型と呼ばれる。

最後に、型の代数の非常に重要な解釈について述べなければならない。aとbの2つの型の直積には、型aおよび型bの両方の値が含まれている必要があることに注意してほしい。これは、（訳注：2つの型の直積が居住されているためには）両方の型が居住されている (inhabited) 必要があることを意味する⁴¹。一方、2つの型の直和には、型a または型bのいずれかの値が含まれるので、（訳注：2つの型の直和が居住されているためには）どちらかが居住されていれば十分だ。論理積 (logical and) と論理和 (logical or) も半環を形成し、型理論の言葉に写せる：

この類推はさらに深く、論理と型理論を結ぶカリー・ハワード同型の基礎となっている。それについては関数型について説明するときに再び取り上げる。

6.5 課題

1. Maybe aとEither () aの間の同型を示せ。

2. 円と長方形の直和型をHaskellで定義する。

   data Shape = Circle Float
              | Rect Float Float

   面積を求めるための関数areaのようなShapeに作用する関数を定義したい場合は、これら2つの構成子に関するパターンマッチングにより行う：

   area :: Shape -> Float
   area (Circle r) = pi * r * r
   area (Rect d h) = d * h

   C++またはJavaでShapeをインタフェースとして実装し、CircleとRectという2つのクラスを作成せよ。areaは仮想関数として実装せよ。

3. 先ほどの例を続ける。Shapeの周の長さを求める新しい関数circは簡単に追加できる。Shapeの定義に触れる必要はない。

   circ :: Shape -> Float
   circ (Circle r) = 2.0 * pi * r
   circ (Rect d h) = 2.0 * (d + h)

   C++またはJavaの実装にcircを追加せよ。もとのコードのどの部分に触れる必要があったか？

4. さらに続ける。新しい図形として正方形SquareをShapeに追加し、必要なすべてを更新する。HaskellならびにC++およびJavaでは、コードのどこに触れる必要があったか⁴²？（Haskellプログラマーでないとしても、変更箇所はごく自明なはずだ。）

5. 型について$a + a = 2 \times a$が（同型を除いて）成り立つことを示せ。前掲の変換表によれば、$2$はBoolに対応する。

7 関手

壊れたレコードのように聞こえるかもしれないが、関手についてこう述べておきたい：関手は非常に単純だが強力な概念だ。圏論はこのような単純だが強力な概念であふれている。関手は圏の間の写像だ。2つの圏$\mathbf{C}$と$\mathbf{D}$について、関手$F$は$\mathbf{C}$の対象を$\mathbf{D}$の対象に写す。これは対象についての関数だ。$a$が$\mathbf{C}$内の対象である場合に、$\mathbf{D}$内の像を$F a$と（括弧なしで）書くことにする。しかし、圏は単に対象の集まりではない――対象とそれらを接続する射からなる。関手は射も写す――射についての関数だ。ただし、射を行きあたりばったりに写すわけではない――接続を維持して写す。 つまり、$\mathbf{C}$内の射$f$が対象$a$を対象$b$に接続する場合： $$f \Colon a \to b$$ $\mathbf{D}$内の$f$の像$F f$は、$a$の像を$b$の像に接続する： $$F f \Colon F a \to F b$$ （これは数学的記法とHaskellの記法を組み合わせたものであり、ここでは理にかなっているだろう。対象や射に関数を適用するときは括弧を使わないことにする。）

ご覧のとおり、関手は圏の構造を保存している。一方の圏で接続されているものは、もう一方の圏でも接続されている。しかし、圏の構造にはそれ以上の何かがある。それは射の合成だ。$h$が$f$と$g$の合成： $$h = g \circ f$$ である場合、$F$による$h$の像が$f$と$g$の像の合成になるようにしたい： $$F h = F g \circ F f$$

最後に、$\mathbf{C}$内のすべての恒等射が$\mathbf{D}$内の恒等射に写されるようにしたい： $$F \mathbf{id}_{a} = \mathbf{id}_{F a}$$ ここで、$\mathbf{id}_{a}$は対象$a$における恒等射を、$\mathbf{id}_{F a}$は$F a$における恒等射を表す。

これらの条件によって、関手は通常の関数よりもはるかに制約が厳しくなることに注意してほしい。関手は圏の構造を保存しなければならない。圏を、射のネットワークによって織りなされた対象の集まりと見なすなら、関手がこの織物に裂け目を入れることは許されない。対象を潰してまとめたり、複数の射を1つにくっつけたりすることはあるが、何かを引き裂くことは決してない。この引き裂きなしという制約は、微積分学において知られる連続性条件に似ている。この意味では、関手は「連続的」である（もっとも、関手にはさらに制約が厳しい連続性の概念が存在する）。関数と同じように、関手にも潰すものと埋め込むものがある。埋め込みの傾向がより顕著なのは、もとの圏が行き先の圏よりずっと小さいときだ。極端な場合、始域は、自明な単元圏 (singleton category) であり得る。すなわち、ただ1つの対象とただ1つの射（恒等射）を持つ圏だ。単元圏から他の圏への関手は、単にその圏内の対象を選択するだけだ。これは、単元集合からの射は終域内の要素を選択する、という特性と完全に類似している。最も潰す関手は定関手$\Delta_c$と呼ばれる。それはもとの圏内のすべての対象を、行き先の圏内で選択された1つの対象$c$に写す。また、もとの圏のすべての射を恒等射$\mathbf{id}_{c}$に写す。まるでブラックホールのように働き、すべてを1つの特異点に圧縮する。この関手については極限と余極限について議論するときに詳しく見よう。

7.1 プログラミングにおける関手

地に足をつけてプログラミングについて話をしよう。我々には型と関数の圏がある。この圏をそれ自体に写す関手について話そう。そのような関手は自己関手 (endofunctor) と呼ばれる。型の圏での自己関手とは何だろうか？　まず、それは型を型に写す。そのような写像の例はすでに見たが、おそらくそれとは気付かなかったのだろう。別の型によってパラメーター化されているような型の定義のことだ。いくつか例を見てみよう。

7.1.1 Maybe関手

Maybeの定義は型aから型Maybe aへの写像だ：

data Maybe a = Nothing | Just a

ここで重要な注意点がある。Maybe自体は型ではなく、型構成子だ。型に変換するには、IntやBoolのような型引数を与える必要がある。引数のないMaybeは、型上の関数を表す。だが、Maybeは関手に変えられるだろうか？ （これ以降、私がプログラミングの文脈で関手と言うとき、ほとんどの場合は自己関手を意味する。） 関手は、対象（ここでは型）を写すだけでなく、射（ここでは関数）も写す。aからbへの任意の関数：

f :: a -> b

についてMaybe aからMaybe bへの関数を生成したい。そのような関数を定義するには、Maybeの2つの構成子それぞれに対応する2つの場合を考慮する必要がある。Nothingの場合は単純で、Nothingを返すだけでよい。そして引数がJustの場合は、関数fをその中身に適用すればよい。したがって、Maybeの下でのfの像は次の関数だ：

f' :: Maybe a -> Maybe b
f' Nothing = Nothing
f' (Just x) = Just (f x)

（ところで、Haskellでは変数名でアポストロフィーを使えるため、いまのような場合にとても便利だ。） Haskellでは、関手における射の写像の部分はfmapと呼ばれる高階関数として実装されている。Maybeの場合、そのシグネチャーは次のとおりだ：

fmap :: (a -> b) -> (Maybe a -> Maybe b)

fmapは関数をリフトするという言い方がよく使われる。リフトされた関数はMaybe値に対して作用する。いつものように、カリー化のため、このシグネチャーには次の2通りの解釈がある。ひとつは、fmapは1引数関数であり、それ自体が関数である(a -> b)型の引数を取って、(Maybe a -> Maybe b)型の関数を返すという解釈だ。もうひとつは、2つの引数を取り、Maybe bを返すという解釈だ：

fmap :: (a -> b) -> Maybe a -> Maybe b

これまでの議論に基づいて、Maybeに対してfmapを実装する方法は次のとおりだ：

fmap _ Nothing = Nothing
fmap f (Just x) = Just (f x)

型構成子Maybeに関数fmapを合わせたものが関手をなすことを示すには、fmapが恒等射と合成を保存することを証明する必要がある。これらは「関手律」と呼ばれているが、単に圏の構造の保存を保証するだけのものだ。

7.1.2 等式による推論

関手律を証明するために、Haskellでの一般的な証明テクニックである等式による推論 (equational reasoning) を使う。これは、Haskellの関数が等式、つまり左辺が右辺に等しいものである、として定義されているという事実を利用している。左辺と右辺はいつでも入れ替えられる。ただし、名前の競合を避けるために変数名を変更する必要はあるかもしれない。これは、関数をインライン化するか、あるいは逆に式を関数にリファクタリングすることと考えてほしい。例として恒等関数を考えてみよう：

id x = x

たとえば、ある式の中にid yがあるなら、yに置き換えられる（インライン化）。さらに、（たとえばid (y + 2)のように）式にidが適用されているなら、(y + 2)のように式そのものに置き換えられる。そして、この置換は両方向に機能する。つまり、任意の式eをid eで置き換えられる（リファクタリング）。関数がパターンマッチングによって定義されている場合は、各サブ定義を独立して使える。たとえば、上記のfmapの定義では、fmap f NothingをNothingに置き換えることも、その逆を行うこともできる。これが実際にどのように機能するか見てみよう。まずは恒等射の保存から始めよう：

fmap id = id

NothingとJustの2つの場合を考慮する必要がある。1つ目の場合は次のようになる（Haskell疑似コードを使って左辺を右辺に変換している）：

  fmap id Nothing
= { fmapの定義 }
  Nothing
= { idの定義 }
  id Nothing

最後のステップでidの定義を逆向きに使ったことに注目してほしい。式Nothingをid Nothingに置き換えた。実際には、このような証明は、真ん中の同じ式に辿り着くまで「ロウソクを両端から燃やす」ことで成される。今回については真ん中に残るのはNothingだ。2つ目の場合も簡単だ：

  fmap id (Just x)
= { fmapの定義 }
  Just (id x)
= { idの定義 }
  Just x
= { idの定義 }
  id (Just x)

では、fmapが合成を保存することを示そう：

fmap (g . f) = fmap g . fmap f

まずはNothingのケース：

  fmap (g . f) Nothing
= { fmapの定義 }
  Nothing
= { fmapの定義 }
  fmap g Nothing
= { fmapの定義 }
  fmap g (fmap f Nothing)

次はJustのケース：

  fmap (g . f) (Just x)
= { fmapの定義 }
  Just ((g . f) x)
= { 合成の定義 }
  Just (g (f x))
= { fmapの定義 }
  fmap g (Just (f x))
= { fmapの定義 }
  fmap g (fmap f (Just x))
= { 合成の定義 }
  (fmap g . fmap f) (Just x)

等式による推論はC++スタイルの副作用のある「関数」では使えないことは、強調しておく価値がある。次のコードを考えてみよう：

int square(int x) {
    return x * x;
}

int counter() {
    static int c = 0;
    return c++;
}

double y = square(counter());

等式による推論を使うと、squareをインライン展開して次のようにできる：

double y = counter() * counter();

明らかにこれは有効な変換ではなく、同じ結果は生成されない。それにもかかわらず、マクロとしてsquareを実装すると、C++コンパイラーは等式による推論を使おうとし、悲惨な結果になる。

7.1.3 Optional

関手はHaskellで簡単に表現できるが、総称プログラミングや高階関数をサポートする言語ならどれでも定義できる。MaybeのC++版であるテンプレート型optionalについて考えてみよう。以下に実装の概略を示す（実際の実装ははるかに複雑で、C++に特有の引数のさまざまな渡し方やコピーセマンティクスやリソース管理の問題を扱わなくてはならない）。

template<class T>
class optional {
    bool _isValid; // the tag
    T    _v;
public:
    optional()    : _isValid(false) {}         // Nothing
    optional(T x) : _isValid(true) , _v(x) {}  // Just
    bool isValid() const { return _isValid; }
    T val() const { return _v; }
};

このテンプレートは、関手の定義の一部である型の写像を提供する。これは任意の型Tを新しい型optional<T>に写す。関数に対するその関手の作用を定義しよう：

template<class A, class B>
std::function<optional<B>(optional<A>)>
fmap(std::function<B(A)> f)
{
    return [f](optional<A> opt) {
        if (!opt.isValid())
            return optional<B>{};
        else
            return optional<B>{ f(opt.val()) };
    };
}

これは高階関数で、引数として関数を受け取り、関数を返す。非カリー化版はこうなる：

template<class A, class B>
optional<B> fmap(std::function<B(A)> f, optional<A> opt) {
    if (!opt.isValid())
        return optional<B>{};
    else
        return optional<B>{ f(opt.val()) };
}

fmapをoptionalのテンプレートメソッドにするという選択肢もある。このように選択肢に迷うことになるため、C++で関手パターンを抽象化するのは問題となる。関手は継承元となるインターフェースにすべきだろうか？（残念ながら、テンプレート仮想関数は作れない。） フリーテンプレート関数は、カリー化版と非カリー化版のどちらにすべきだろうか？　不足した型情報を、C++コンパイラーは正しく推論してくれるだろうか、それとも明示的に指定しなければならないだろうか？　入力関数fがintからboolへの関数である状況を考えてみよう。コンパイラーにgの型が分かるだろうか：

auto g = fmap(f);

特に将来、複数の関手がfmapをオーバーロードするようになった場合は？ （近いうちにさらに多くの関手について見てみよう。）

7.1.4 型クラス

では、Haskellは関手の抽象化にどのように対処するのだろうか？　それには型クラスの機構を使う。型クラスは、共通のインターフェースをサポートする型の族を定義する。たとえば、等しさの検査をサポートする対象についてのクラスは次のように定義される：

class Eq a where
    (==) :: a -> a -> Bool

この定義は、型aの引数を2つ取りBoolを返す演算子(==)がサポートされる場合、型aはクラスEqであることを示している。特定の型がEqであることをHaskellに伝えたい場合は、その型をこのクラスのインスタンスであると宣言し、(==)の実装を提供する必要がある。たとえば、2次元空間における点を表す型Point（2つのFloatの直積型）が定義されているとする：

data Point = Pt Float Float

点の等しさは次のように定義できる：

instance Eq Point where
    (Pt x y) == (Pt x' y') = x == x' && y == y'

ここでは演算子(==)（いま定義しようとしているもの）を2つのパターン(Pt x y)と(Pt x'y Pt x y)の間に中置した。関数の本体は、単一の等号の後に続く。いったんPointがEqのインスタンスであると宣言されると、点同士の等しさを直接比較できるようになる。C++やJavaとは異なり、Pointを定義するときにEqクラス（またはインターフェース）を指定する必要はなく、クライアントコード内で後から指定できることに注目してほしい。また、型クラスは関数（および演算子）をオーバーロードするためのHaskellにおける唯一の機構でもある。型クラスはfmapを異なる関数（や演算子）についてオーバーロードするために必要となる。ただし、1つ複雑な点がある。関手は型として定義されるのではなく、型の写像、つまり型構成子として定義される。必要な型クラスは、Eqの場合のような型の族ではなく、型構成子の族だ。幸い、Haskellの型クラスは型だけでなく型構成子に対しても使える。以下にFunctorクラスの定義を示す。

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

これは、指定された型シグネチャーを持つ関数fmapが存在する場合、fはFunctorだと規定している。小文字のfは型変数であり、型変数aやbと似ている。しかし、コンパイラーはそれが型ではなく型構成子を表していることを、その使われ方から推論できる。つまり、f aやf bのように他の型に作用していることから推論できる。したがって、Functorのインスタンスを宣言するときは型構成子を考える必要がある。例としてMaybeの場合を示す：

instance Functor Maybe where
    fmap _ Nothing = Nothing
    fmap f (Just x) = Just (f x)

ちなみに、Functorクラスや、Maybeを含む多くの単純なデータ型のインスタンス定義は、標準のPreludeライブラリの一部となっている。

7.1.5 C++での関手

C++でも同じアプローチを試せるだろうか？　型構成子は、optionalのようなテンプレートクラスに対応しているので、同様にfmapをテンプレート・テンプレート引数 (template template parameter) でパラメーター化しよう。構文は次のとおりだ：

template<template<class> F, class A, class B>
F<B> fmap(std::function<B(A)>, F<A>);

このテンプレートをさまざまな関手に特殊化できるようにしたい。残念ながら、C++ではテンプレート関数の部分的な特殊化は禁止されている。そのため、次のような記述はできない：

template<class A, class B>
optional<B> fmap<optional>(std::function<B(A)> f, optional<A> opt)

代わりに関数のオーバーロードに頼る必要がある。結局、もとのカリー化されていないfmapの定義に戻る：

template<class A, class B>
optional<B> fmap(std::function<B(A)> f, optional<A> opt)
{
    if (!opt.isValid())
        return optional<B>{};
    else
        return optional<B>{ f(opt.val()) };
}

この定義は機能するが、どのオーバーロードが使われるかをfmapの2番目の引数が選択しているからにすぎない。より汎用的なfmapの定義を完全に無視している。

7.1.6 リスト関手

プログラミングにおける関手の役割についてある程度の直観を育むには、もっといろいろな例を見る必要がある。別の型によってパラメーター化される型はどれも関手の候補だ。総称コンテナーも格納する要素の型によってパラメーター化されているる。では、ごく単純なコンテナーであるリストを見てみよう：

data List a = Nil | Cons a (List a)

型構成子Listがある。これは、任意の型aから型List aへの写像だ。Listが関手だと示すには、関数のリフトを定義する必要がある。つまり、関数a -> bについて関数List a -> List bを定義する：

fmap :: (a -> b) -> (List a -> List b)

List aに作用する関数は、リストの2つのコンストラクターに対応する2つの場合を考慮する必要がある。Nilの場合は自明で、単にNilを返す。空のリストに対してできることはあまりない。Consの場合は、再帰を伴うため、ややトリッキーだ。そこで、少し前に戻って、何をしようとしているのか考えてみよう。aのリストと、aをbに変換する関数fがあり、bのリストを生成したい。自明なのは、fを使ってリストの各要素をaからbに変換することだ。（空でない）リストが先頭要素headと先頭を除いた残りのリストtailのConsとして定義されている場合、実際にはどうやるのだろうか？　fをheadに適用し、リフト（fmap）されたfをtailに適用すればよい。これは再帰的な定義だ。リフトされたfをリフトされたfを用いて定義しているからだ：

fmap f (Cons x t) = Cons (f x) (fmap f t)

右辺のfmap fが、それに対して定義しようとしているリスト（訳注：Cons x t）よりも短いリストに適用されていることに注意してほしい。fmap fはそのリストのtailに適用されている。再帰的に処理されるにつれてリストが短くなるため、最終的には空リスト、つまりNilに到達することになる。しかし、先ほど決めたとおり、fmap fがNilに作用するとNilを返すため、再帰は停止する。最終的な結果を得るために、Consコンストラクターを使って、新しいheadの(f x)と新しいtailの(fmap f t)を結合する。すべてをまとめると、リスト関手のインスタンス宣言はこうなる：

instance Functor List where
    fmap _ Nil = Nil
    fmap f (Cons x t) = Cons (f x) (fmap f t)

C++の方が慣れているなら、std::vectorの場合を考えてみてほしい。それは最も汎用的なC++コンテナーと見なせるかもしれない。fmapのstd::vector用の実装は単にstd::transformの単純なカプセル化だ：

template<class A, class B>
std::vector<B> fmap(std::function<B(A)> f, std::vector<A> v)
{
    std::vector<B> w;
    std::transform( std::begin(v)
                  , std::end(v)
                  , std::back_inserter(w)
                  , f);
    return w;
}

これを使えば、たとえば次のように数列の要素を2乗できる⁴³：

std::vector<int> v{ 1, 2, 3, 4 };
auto w = fmap([](int i) { return i*i; }, v);
std::copy( std::begin(w)
         , std::end(w)
         , std::ostream_iterator(std::cout, ", "));

ほとんどのC++コンテナーは関手だと言える。それらはstd::transformに渡せるイテレーターを実装していて、std::transformはfmapのより原始的な従兄弟だからだ。残念ながら、関手の単純さは、イテレーターや一時変数（上記のfmapの実装を参照）でいつも煩雑になるため失われてしまう。新しく提案されたC++のrangeライブラリによってrangeの関手的な性質がより顕著になったのは喜ばしい。

7.1.7 Reader関手

さて、直観が育ってきただろう。たとえば、関手をある種のコンテナーと見なせるようになった。では、一見非常に異なる例をお見せしよう。型aからの、aを返す関数の型への写像を考えてみよう。関数型についてはあまり詳しく述べていない（完全に圏論的な扱いはこれからだ）が、プログラマーならある程度理解している。Haskellでは、関数型はアロー型構成子(->)を使って構成され、引数の型と結果の型の2つの型を取る。すでに中置記法a -> bで見たことがあるが、括弧で括れば前置記法でも同様に使える：

(->) a b

通常の関数と同様に、複数の引数を取る型関数も部分適用できる。したがって、矢印に対して型引数を1つだけ与えた後もなお、もう1つの型引数が期待される。それが：

(->) a

が型構成子である理由だ。完全な型a -> bを生成するには、もう1つの型bが必要だ。今のところは、aによってパラメーター化された型構成子の族の全体を定義していると言える。これが関手の族でもあるかどうか見てみよう。2つの型パラメーターを扱うのは混乱を招くかもしれないので、名前を変更しておこう。前の関手の型定義に従って、引数の型をr 、結果の型をaと呼ぼう。そうすると、この型構成子は任意の型aを取り、それを型r -> aに写す。これが関手であることを示すために、関数a -> bを、r -> aを受け取ってr -> bを返す関数にリフトしたい。これらの型はaとbのそれぞれに型構成子(->) rを作用させて作られたものだ。この場合におけるfmapの型シグネチャーは次のとおりだ：

fmap :: (a -> b) -> (r -> a) -> (r -> b)

ここでパズルを解かなくてはならない：関数f :: a -> bと関数g :: r -> aが与えられるとき、関数r -> bを作成せよ。2つの関数を合成する方法は1つしかなく、その結果はまさに必要なものだ。fmapの実装は次のようになる：

instance Functor ((->) r) where
    fmap f g = f . g

うまくいった！　簡潔な表記が好みなら、さらに短く定義できる。そのためには、合成を前置記法で書き直せることと：

fmap f g = (.) f g

そのときの引数を省略できることに着目し、2つの関数の間の等式を得る：

fmap = (.)

型構成子 (->) rと上記のfmapの実装の組み合わせは、reader関手と呼ばれる。

7.2 コンテナーとしての関手

汎用コンテナーを定義できるか、オブジェクトをそれが含む値の型によってパラメーター化して定義できるプログラミング言語において、関手の例をいくつか見た。Reader関手は異端に思える。我々は関数をデータとは見なさないからだ。しかし、純粋関数はメモ化でき、関数の実行はテーブル参照に変えられるのをすでに見た。テーブルはデータだ。逆に、Haskellは遅延評価を採用しているため、リストのような従来のコンテナーは、実際には関数として実装されうる。たとえば、次のように簡潔に定義できる自然数の無限リストを考えてみよう：

nats :: [Integer]
nats = [1..]

最初の行では、一対の角括弧はHaskellの組み込みリスト用の型構成子だ。2行目では、リストを作成するために角括弧が使われている。明らかに、このような無限リストはメモリーに格納できない。コンパイラーはこれを、必要に応じてIntegerを生成する関数として実装する。Haskellは効果的に、データとコードの区別を曖昧にしている。リストは関数と見なせて、関数は引数を結果に写すテーブルと見なせる。後者は、関数の領域が有限かつ大きすぎない場合なら現実的だ。しかし、strlenをテーブル参照として実装するのは現実的でない。無限に多くの異なる文字列が存在するからだ。プログラマーとして、我々は無限大は好きではないが、圏論では朝食に無限大を食べるのを学ぶことになる。すべての文字列の集合であっても、過去・現在・未来の宇宙のすべての可能な状態の集まりであっても、対処できる！　そこで、関手オブジェクト（自己関手によって生成された型のオブジェクト）はパラメーター化される型の値を含むと考えたい。それらの値が物理的にそこに存在しない場合でもだ。関手の一例はC++のstd::futureで、ある時点で値を含みうるが、必ず含む保証はない。また、その値にアクセスしたいとき、別スレッドの実行終了を待つためにブロックされることがある。別の例としてはHaskellのIOオブジェクトがあり、ユーザー入力を含んだり、画面に「Hello World!」と表示されているような未来版の宇宙を含んだりできる。この解釈によれば、関手オブジェクトとは、パラメーター化された型の値を含みうるものだ。あるいは、これらの値を生成するためのレシピも含みうる。値にアクセスできるかは全く気にしない――それは完全にオプショナルであり、関手の守備範囲外だ。関心があるのは、これらの値を関数を使って操作できるかだけだ。値にアクセスできるなら、操作の結果を確認できるはずだ。アクセスできないなら、操作が正しく合成され、恒等関数による操作が何も変更しないことに注意するだけでよい。関手オブジェクト内の値へのアクセスを全く気にしていないことを明示するために、引数aを完全に無視する型構成子を例に挙げよう：

data Const c a = Const c

Const型構成子はcとaの2つの型を取る。アローコンストラクターで行ったように、部分適用で関手を作成しよう。Const型のデータ構成子（これもConstと呼ばれる）は型cの値を1つだけ取る。これはaには依存しない。この型構成子のfmapの型は次のようになる：

fmap :: (a -> b) -> Const c a -> Const c b

この関手は型引数を無視するので、fmapの実装はその関数引数を無視してよい――その関数は作用するものがない：

instance Functor (Const c) where
    fmap _ (Const v) = Const v

これはC++ではもう少し明確かもしれない（この言葉を口にするとは思わなかった！）。コンパイル時に決まる型引数と実行時に決まる値がよりはっきり区別されるからだ。

template<class C, class A>
struct Const {
    Const(C v) : _v(v) {}
    C _v;
};

fmapのC++実装も、関数の引数を無視し、Constの引数を値は変更せず実質的に再キャストする：

template<class C, class A, class B>
Const<C, B> fmap(std::function<B(A)> f, Const<C, A> c) {
    return Const<C, B>{c._v};
}

その奇妙さにもかかわらず、Const関手は多くの構成で重要な役割を果たしている。圏論では、これは先に述べた$\Delta_c$関手の特殊なケースであり、ブラックホールの自己関手版だ。今後もっと詳しく知ることになるだろう。

7.3 関手の合成

圏の間の関手が合成できることは、集合の間の関数が合成できるのと同様だと考えれば納得するのは難しくない。2つの関手の合成は、対象に作用するときは、それぞれの対象の写像の合成にすぎず、射に作用するときも同様だ。2つの関手を飛び越えたあと、恒等射は恒等射となり、射の合成は射の合成となる。ただそれだけだ。特に、自己関手を合成するのは簡単だ。関数maybeTailを覚えているだろうか？　ここではHaskellの組み込みのリスト実装を使って書き直そう：

maybeTail :: [a] -> Maybe [a]
maybeTail [] = Nothing
maybeTail (x:xs) = Just xs

（Nilと呼んでいた空リストコンストラクターは、空の角括弧のペア[]に置き換えられる。Consコンストラクターは、中置演算子:（コロン）に置き換えられる。） maybeTailの結果は、Maybeと[]という2つの関手の合成がaに作用するような型だ。これらの関数はそれぞれ独自版のfmapを備えているが、もし何らかの関数fを合成の内容、つまりMaybeリストに適用したい場合はどうなるだろう？　2層の関手を突破しなければならない。fmapを使えば外側のMaybeは突破できる。しかし、fはリストに対しては動かないので、Maybe内にfを単に送ることはできない。内側のリストを操作するには(fmap f)を送る必要がある。たとえば、整数のMaybeリストの要素を2乗するにはどうするか見てみよう：

square x = x * x

mis :: Maybe [Int]
mis = Just [1, 2, 3]

mis2 = fmap (fmap square) mis

コンパイラーは、型を分析した後、外側のfmapに対してはMaybeインスタンスからの実装を使い、内側のものに対してはリスト関手の実装を使う必要があることを理解する。上記のコードを次のように書き換えられるのは、すぐには自明に思えないかもしれない：

mis2 = (fmap . fmap) square mis

だが、fmapは引数が1つだけの関数と見なせることを思い出してほしい：

fmap :: (a -> b) -> (f a -> f b)

この例では、(fmap . fmap)内の2番目のfmapは引数として次のものを取る：

square :: Int -> Int

そして、次の型の関数を返す：

[Int] -> [Int]

最初のfmapがこの関数を受け取り、次の型の関数を返す：

Maybe [Int] -> Maybe [Int]

最後に、この関数はmisに適用される。したがって、2つの関手を合成すると、対応する2つのfmapを合成したfmapを持つ関手になる。圏論に話を戻すと、関手の合成が結合性を持つのはごく自明だ（対象の写像が結合性を持ち、射の写像も結合性を持つ）。また、すべての圏には自明な恒等関手がある。すなわち、どの対象もその対象自身へ写し、どの射もその射自身へ写すような関手だ。つまり、関手はある圏の射と全く同じ性質を持っている。しかし、それはどのような圏だろうか？　対象が圏であり射が関手である圏でなければならない。すなわち、圏の圏だ。ところが、すべての圏の圏はそれ自体を含まなければならず、すべての集合の集合を不可能にしたのと同じ種類の矛盾にぶつかることになる。しかし、$\mathbf{Cat}$と呼ばれる、すべての小さい圏の圏がある（$\mathbf{Cat}$自体は大きい圏なので、それ自体のメンバーにはなれない）。小さい圏とは、対象が集合よりも大きな何かではなく集合をなすような圏のことだ。圏論では、非可算無限集合であっても「小さい」と見なされることに注意してほしい。これらに言及しようと思ったのは、同じ構造が抽象化の多くのレベルで繰り返されているのを認識できることが、非常に驚くべきことだからだ。関手が圏を形成することについても後で説明する。

7.4 課題

1. 次のように定義することで、Maybe型構成子を関手に変換できるか？

   fmap _ _ = Nothing

   これは両方の引数を無視する。（ヒント：関手律をチェックする。）

2. Reader関手について関手律を証明せよ。ヒント：本当に単純だ。

3. 2番目に好きな言語でReader関手を実装せよ（1番目はHaskell、それ一択だ）。

4. リスト関手について関手律を証明せよ。その際は、fmap fを適用するリストのtailについて規則が真であると仮定せよ（言い換えると、帰納法を使用せよ）。

8 関手性

関手とは何かを学び、いくつかの例を見てきたのに続いて、小さい関手からより大きい関手を作る方法を見てみよう。特に興味深いのは、（圏内の対象間の写像に対応する）どの型構成子を、（射の間の写像を含む）関手に拡張できるのかという点だ。

8.1 双関手

関手は$\mathbf{Cat}$（圏の圏）の射であるため、射――典型的には関数――に関する直観の多くは関手にも当てはまる。たとえば、2つの引数を取る関数があるのと同じように、2つの引数を取る関手、すなわち双関手 (bifunctor) もある。対象については、1つは圏$\mathbf{C}$から、もう1つは圏$\mathbf{D}$からの対象からなるペアを、双関手はすべて圏$\mathbf{E}$の対象へと写す。これは単に、圏のデカルト積⁴⁴$\mathbf{C} \times{} \mathbf{D}$から$\mathbf{E}$への写像だと言っているだけであることに注意してほしい。

実に直截的だ。しかし、関手性によると、双関手は射も写さなければならない。ただし、今回は$\mathbf{C}$の射と$\mathbf{D}$の射のペアを$\mathbf{E}$の射に写す必要がある。

ここでも、射のペアは積圏$\mathbf{C} \times{} \mathbf{D}$内の1つの射に相当する。圏のデカルト積における射は、ある対象のペアから別の対象のペアへ向かう射のペアと定義される⁴⁵。これらの射のペアは、自明な方法で合成できる： $$(f, g) \circ (f', g') = (f \circ f', g \circ g')$$ 合成は結合的であり、恒等射のペア $(\mathbf{id}, \mathbf{id})$ を恒等射として持つ。圏のデカルト積は確かに圏だ。

双関手についてもっと簡単に考えたいなら、両方の引数を取る関手だと見なせばよい。そうすれば、関手律――結合性と恒等射の保存――を関手から双関手へ翻訳するのではなく、引数ごとに個別にチェックすれば十分だろう。ただし、一般には、個別の関手性は結合した関手性の証明としては不十分だ。結合した関手性が成り立たない（訳注：ような積を持つ）圏は前モノイダル圏 (premonoidal category) と呼ばれる。

Haskellで双関手を定義しよう。この場合の3つの圏はすべて同じで、Haskellの型の圏だ。双関手は2つの型引数を取る型構成子だ。型クラスBifunctorの定義をライブラリControl.Bifunctorから採ると、次のとおりだ：

class Bifunctor f where
    bimap :: (a -> c) -> (b -> d) -> f a b -> f c d
    bimap g h = first g . second h
    first :: (a -> c) -> f a b -> f c b
    first g = bimap g id
    second :: (b -> d) -> f a b -> f a d
    second = bimap id

型変数fは双関手を表す。どの型シグネチャーにおいてもfは常に2つの型引数に適用されている。最初の型シグネチャーは、bimapが2つの関数を同時に写すものであることを規定⁴⁶している。その結果はリフトされた関数(f a b -> f c d)であり、双関手の型構成子fが生成する型に対して作用する。 bimapにはfirstとsecondによるデフォルト実装がある（前述のとおり、これは常に機能するわけではなく、2つの写像が可換でない場合⁴⁷にはfirst g . second hとsecond h . first gは同じではない）。

他の2つの型シグネチャーfirstとsecondは、2つのfmapであり、それぞれ最初と2番目の引数についてfの関手性を示す⁴⁸。

型クラス定義は、この両方のデフォルト実装をbimapに基づいて提供する。

Bifunctorのインスタンスを宣言するときには、bimapを実装してデフォルトのfirstとsecondを受け入れるか、firstとsecondの両方を実装してデフォルトのbimapを受け入れるか、どちらかを選べる（もちろん3つすべてを実装してもよいが、それらが相互に正しく関連付けられているのを確認するのはプログラマーの責任になる）。

8.2 積と余積の双関手

双関手の重要な例として、圏論的な積、つまり普遍的構成によって定義される2つの対象の積がある。対象の任意のペアに対して積が存在する場合、これらの対象から積への写像は双関手的だ。これは一般に真であり、特にHaskellについてもそうだ。最も単純な直積型である、ペア型の型構成子に対するBifunctorインスタンスはこうなる：

instance Bifunctor (,) where
    bimap f g (x, y) = (f x, g y)

選択の余地はあまりない。bimapでは単に、最初の関数をペアの第一成分に適用し、2番目の関数を第二成分に適用するだけだ。その型から、このコードが何をするかは一目瞭然だ：

bimap :: (a -> c) -> (b -> d) -> (a, b) -> (c, d)

ここでの双関手の作用は、たとえば次のような型のペアを作ることだ：

(,) a b = (a, b)

双対性より、余積も、圏内の対象のすべてのペアに対して定義されているなら双関手だ。Haskellにおいては、型構成子EitherがBifunctorのインスタンスであることが良い例だ：

instance Bifunctor Either where
    bimap f _ (Left x)  = Left (f x)
    bimap _ g (Right y) = Right (g y)

このコードも何をするか一目瞭然だ。

モノイダル圏について述べたときのことを覚えているだろうか？　モノイダル圏は、対象に作用する二項演算子と単位対象とを定義する。$\mathbf{Set}$について、デカルト積に関して単元集合を単位元とするモノイダル圏だと述べた。また、非交和に関しても空集合を単位元とするモノイダル圏だ。しかし、モノイダル圏の要件の1つとして、二項演算子が双関手でなければならないことは述べていなかった。これは非常に重要な要件だ。射によって定義される圏の構造とモノイド的な積とを両立させたいからだ。我々はいま、モノイダル圏の完全な定義に一歩近づいている（そこに到達するまでには、まだ自然性について学ぶ必要がある）。

8.3 関手的代数的データ型

これまでに、パラメーター化されたデータ型が関手であるような例、つまりそれについてfmapを定義できるような型をいくつか見てきた。複雑なデータ型は単純なデータ型から構成される。特に、代数的データ型 (ADT) は、和と積を使って作成される。和と積が関手的なのは先ほど見た。関手が合成可能であることもすでに知っている。したがって、ADTの基本的な構成要素が関手的であると示せれば、パラメーター化されたADTも関手的だと分かる。

では、パラメーター化された代数的データ型の構成要素は何だろうか？　まず、MaybeにおけるNothingやListにおけるNilのように、関手の型パラメーターに依存しない要素がある。それらはConst関手と等価だ。Const関手は型パラメーターを無視することを思い出してほしい（いま述べているのは2番目の型パラメーターのことで、最初のパラメーターはそのままにされる）。

次に、MaybeにおけるJustのように、単に型パラメーター自体をそのままカプセル化する要素がある。これらは恒等関手と等価だ。以前、恒等関手について$\mathbf{Cat}$の恒等射として言及したが、Haskellでの定義は説明しなかった。それをここに示す：

data Identity a = Identity a

instance Functor Identity where
    fmap f (Identity x) = Identity (f x)

Identityは、型aの（不変な）値を常に1つだけ格納する、最も単純なコンテナーと見なせる。

代数的データ構造の他のすべては、これら2つのプリミティブから積と和を使って構成される。

この新しい知識に基づいて、Maybe型構成子を改めて見てみよう。

data Maybe a = Nothing | Just a

これは2つの型の和だ。和が関手的なのは知っている。1つ目の部分であるNothingは、Const ()のaに対する作用として表せる（Constの最初の型パラメーターはunit型に設定されている――後でConstのさらに興味深い使い方を説明する）。2つ目の部分は、恒等関手の別名だ。Maybeは、同型を除いて、次のようにも定義できる：

type Maybe a = Either (Const () a) (Identity a)

したがって、Maybeは双関手Eitherを2つの関手Const ()とIdentityに合成したものだ。（Constは実際には双関手だが、ここでは常に部分適用で使う。）

関手の合成が関手であることはすでに見た。同じことが双関手にも当てはまるのは簡単に納得できる。必要なのは、2つの関手との双関手の合成が、射にどのように作用するかを理解することだけだ。2つの射が与えられたとき、まず片方の関手で片方の射を、もう1つの関手でもう1つの射をそれぞれ単にリフトする。次に、そのようにして得られるリフトされた射のペアを、双関手でリフトする。

この合成はHaskellで表現できる。双関手bf（2つの型を引数に取る双関手コンストラクターである型変数）と、2つの関手fuとgu（それぞれ1つの型変数を取る型構成子）と、2つの通常の型aとbとによってパラメーター化されるデータ型を定義しよう。fuをaに適用し、guをbに適用し、それからbfを結果の2つの型に適用する：

newtype BiComp bf fu gu a b = BiComp (bf (fu a) (gu b))

これが対象、つまり型の合成だ。Haskellで型構成子を型に適用する方法が、関数を引数に適用するのと同じであることに注目してほしい⁴⁹。それらは同じ構文だ。

少し迷ったなら、BiCompを、Either、Const ()、Identity、a、bの順に適用してみてほしい。Maybe bのベアボーン版を復元できるだろう（aは無視される）。

bf自体がBifunctorでありfuおよびguがFunctorである場合については、新しいデータ型BiCompはaおよびbについて双関手だ。そのため、BiComp bf fu guをBifunctorのインスタンスにするためには、bfに対するbimapの定義と、fuとguに対するfmapの定義とが存在することをコンパイラーが認識している必要がある。Haskellでは、これはインスタンス宣言の前提条件として表現される。つまり、以下においてクラス制約のセットとして二重矢印の前に書かれた部分だ：

instance (Bifunctor bf, Functor fu, Functor gu) =>
  Bifunctor (BiComp bf fu gu) where
    bimap f1 f2 (BiComp x) = BiComp (bimap (fmap f1) (fmap f2) x)

BiCompに対するbimapの実装は、bfに対するbimapと、fuおよびguに対する2つのfmapによって与えられる。コンパイラーは、BiCompが使われるたびに、すべての型を自動的に推測し、適切なオーバーロード関数を選択する。

bimapの定義内のxは次のような型だ：

bf (fu a) (gu b)

これについて述べると長くなる。外側のbimapは外側のbfの層を貫通しており、2つのfmapはそれぞれfuとguの下まで掘り下げている。f1とf2の型が次の場合：

f1 :: a -> a'
f2 :: b -> b'

最終結果の型はbf (fu a') (gu b')となる：

bimap ::(fu a -> fu a') -> (gu b -> gu b')
  -> bf (fu a) (gu b) -> bf (fu a') (gu b')

ジグソーパズルが好きな人なら、この種の型操作で何時間も楽しめるだろう。

Maybeが関手だと証明する必要はなかったと分かった。この事実は、Maybeが2つの関手的プリミティブの和として構築できることから導かれたものだ。

鋭い読者ならこう尋ねるだろう：代数的データ型に対するFunctorインスタンスをそれほど機械的に導出できるのなら、コンパイラーによって自動化して実行できないのか？　実際、可能であり、行われている。ただし、特定のHaskell拡張を、ソースファイルの先頭に次の行を含めることで有効にする必要がある：

{-# LANGUAGE DeriveFunctor #-}

そして、データ構造にderiving Functorを追加する：

data Maybe a = Nothing | Just a
  deriving Functor