はじめに

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

ここからの数段落で納得してもらいたいのは、この本はあなたのために書かれたものであり、数学のうちでも特に抽象的な分野を学ぶために「あり余る自由時間」を費やすことに異論を唱える根拠は全くないということだ。

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

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

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

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

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

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

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

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

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

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

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

1 圏：合成の本質

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

1.1 関数としての射

すでに抽象的すぎて意味不明だろうか？ 投げ出さないでほしい。具体的な話をしよう。矢（射 (morphism) とも呼ばれる）を関数として考えよう。関数$f$が型$A$の引数を取って$B$を返すとする。また、別の関数$g$が$B$を取って$C$を返すとする。$f$の結果を$g$に渡せばそれらを合成できる。つまり$A$を取って$C$を返す新たな関数を定義したことになる。

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

lsof | grep Chrome

や、F#の前方合成演算子>>などの記法ならお馴染みだろう。どちらも左から右の向きだ。ところが、数学やHaskellの関数は右から左に合成する。$g \circ 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ではユニコード文字を使えるので、合成を次のようにも書ける：

g ∘ f

ユニコードの二重コロンと矢印さえ使える¹。

f ∷ A → B

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

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

関数の本体は常に式であり、関数内に宣言はない。関数の結果はその式だ――ここでは単に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つ、マジカルナンバー7プラスマイナス2は、我々は$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の2要素集合だ（Haskellでは具体的な型は大文字で始まることを思い出してほしい）。Char型はaやąのようなユニコード文字すべての集合だ。

集合は有限集合と無限集合のどちらでもよい。Stringは、Charのリストの同義語で、その型は無限集合の例だ。

xをIntegerとして宣言しよう：

x :: Integer

これは、整数集合の要素だと言っていることになる。HaskellのIntegerは無限集合であり、任意の精度の演算に使える。また、C++のintと同様の、機械語の型に対応する有限集合intもある。

いくつか微妙な点があるせいで、型と集合の区別は厄介なものになっている。循環定義を含む多相関数には問題があり、すべての集合の集合は存在できないという事実にも問題がある。だが、約束したとおり、私は数学にこだわるつもりはない。ありがたいことに、集合の圏が存在する。$\mathbf{Set}$と呼ばれるその圏をここでは扱う。$\mathbf{Set}$では、対象は集合であり、射（矢）は関数だ。

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

理想的な世界では、Haskellの型は集合であり、Haskellの関数は集合間の数学的関数であると言えば済んだだろう。だが、1つだけ小さな問題がある。数学関数はコードを実行せず、単に解を知っているだけなのだ。Haskellの関数は解を計算する必要がある。有限のステップ数で解が得られるなら、何ステップかかっても問題はない。ところが、計算のなかには再帰を伴うものもあり、ずっと停止しないことがあり得る。Haskellから非停止関数 (non-terminating function) を単に追放はできない。なぜなら、停止関数と非停止関数の区別は決定できないからだ。これは停止性問題 (halting problem) として有名だ。そのため計算機科学者たちは素晴らしいアイデアを考案した。それは捉え方によっては大きなハッキングとも言えるだろう。そのアイデアとは、ボトム (bottom) と呼ばれる、記号_|_またはユニコードの$\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は任意の型を表せる型変数なのを覚えておいてほしい。） この名前は偶然ではない³。Curry-Howard同型と呼ばれる論理の観点から、型と関数についてのより深い解釈が存在する。型Voidは虚偽を表し、関数absurdの型は「虚偽からは何でも導ける」というラテン語の格言 “ex falso sequitur quodlibet” に対応している。

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

int f44() { return 44; }

この関数は “nothing” を取ると思うかもしれないが、先ほど見たように、“nothing” を取る関数は決して呼び出されない。なぜなら、“nothing” を表す値がないからだ。この関数は何を取るのだろうか？ 概念的には、インスタンスが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) {}

型の類型学における次のものは2要素集合だ。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とほぼ同じ動作をする関数を返す。ただし、もとの関数を引数ごとに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型だけを対象とする圏の絵を描け。矢はこれらの型の間のすべての可能な関数に対応している。矢には関数名のラベルを付けよ。

2.8 参考文献

1. Nils Anders Danielsson, John Hughes, Patrik Jansson, Jeremy Gibbons, Fast and Loose Reasoning is Morally Correct. この論文は、ほとんどの文脈でボトムを無視することの正当性を説明している。

3 大きい圏から小さい圏まで

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

3.1 対象の不在

最も簡単な圏は、0個の対象、したがって0個の射を持つものだ。それ自体は非常に哀しい圏だが、他の圏の文脈、たとえば、すべての圏の圏（そう、1つ存在する）において重要になるだろう。空集合に意味があると思うなら、空の圏が無意味だとは思わないだろう？

3.2 シンプルなグラフ

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

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

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

3.3 順序

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

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

最後に、任意の2つの対象が何らかの方法で互いに関係しているという条件も課せる。そうすると、線形順序 (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つは複数の引数の関数として解釈し、右端の型を戻り値の矢印とする方法、もう1つは1つの引数（左端の引数）の関数として解釈し、関数を返す方法だ。後者の解釈は、m -> (m -> m)のように括弧（矢印が右結合であるため冗長）を追加することによって強調できる。この解釈については後で説明する。

Haskellでは、memptyとmappendのモノイダル特性（すなわち、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>
  T mempty = delete;

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

template<class M>
  concept bool Monoid = requires (M m) {
    { mempty<M> } -> M;
    { mappend(m, m); } -> M;
  };

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

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

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

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

template<>
std::string mempty<std::string> = {""};

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に由来する。すべてのモノイドは、適切な合成規則に従う射の集合を持つ単一の対象の圏として記述できる。

文字列の連結は興味深いケースだ。なぜなら、右アペンダーと左アペンダー（あるいはprependers）を定義する選択肢があるからだ。2つのモデルの合成テーブルは、互いに鏡像反転している。「foo」に「bar」を後置するのと「bar」に「foo」を前置するのが同じなのは容易に納得できるだろう。

すべての圏論的モノイド――対象が1つの圏――が二項演算付き集合 (set-with-binary-operator) のモノイドを一意に定義するのか、という疑問を持つかもしれない。単一対象の圏からは常に集合を抽出できる。その集合は射の集合であり、この例では加算器だ。言い換えれば、圏$\mathbf{M}$内の単一対象$m$についてhom集合$\mathbf{M}(m, m)$ が存在する。この集合における二項演算は簡単に定義できる。2つの集合要素のモノイダル積 (monoidal product) とは、それらに対応する射を合成したものに対応する要素だ。つまり、$f$と$g$に対応する$\mathbf{M}(m, m)$ の2つの要素を指定すると、その積は合成$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++の型：T2へのポインタを期待する関数にT1をコンパイルエラーを発生させずに渡せるならば、T1はT2のサブタイプである。

3. Boolが2つの値TrueとFalseの集合であることを考えると、演算子&& (AND) と|| (OR) にそれぞれ対応する2つの（集合論的）モノイドを形成することを示せ。

4. AND演算子を伴うBoolモノイドを圏として表せ。射と合成の規則を列挙せよ。

5. モジュロ3加算をモノイドの圏として表せ。

4 Kleisli圏

型と純粋関数を圏としてモデル化する方法を見てきた。また、圏論には副作用や非純粋関数をモデル化する方法があることにも触れた。その例として、実行内容をログに記録したりトレースしたりする関数を見てみよう。命令型言語では、次のように、何らかのグローバルな状態を変更することによって実装される場合が多い：

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を修正して、通常の戻り値の上にメッセージ文字列を背負わせるようにしたい。

これらの関数の戻り値を「装飾」(embellish) することにする。総称的な方法で、テンプレート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圏

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

たとえば、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番目の成分（文字列）と2番目の結果の2番目の成分（文字列）を連結する。

4. 最終結果の最初の成分と連結された文字列を組み合わせた新しいペアを返す。

この合成を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番目の成分は連結されており、連結も結合性を持つ。

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

4.2 HaskellにおけるWriter

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

type Writer a = (a, String)

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

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

a -> Writer b

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

(>=>) :: (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に対応する。これは文字関数toUpperを文字列sに適用する。ちなみに、補助関数wordsは標準のPreludeライブラリで定義されている。

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

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

4.3 Kleisli圏

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

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

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. 部分関数についてKleisli圏を構築せよ（合成と恒等射を定義せよ）。

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つだけ持つ対象だ。

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

以下にいくつかの例を示す。半順序集合 (partially ordered set) は、しばしばポセット (poset) と呼ばれ、最小要素が始対象となる。始対象を持たないポセットもある。たとえば、正と負のすべての整数の集合のように、射について等号付き大小関係を持つものだ。

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

absurd :: Void -> a

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

5.2 終対象

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

終対象は、圏内のどの対象からも1つの射しか来ない対象だ。

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

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だ。

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

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

5.4 同型

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

直観としては、同型の対象は同じように見える――同じ形をしている。これは、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$は恒等射と等しくなる。同様に、$f\circ g$は恒等射と等しくなければならない。$i_{2}$から$i_{2}$に戻る射は1つしかないからだ。これは、$f$と$g$が互いに逆でなければならないことを証明している。したがって、任意の2つの始対象は同型だ。

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

5.5 積

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

唯一言えるのは、積から各構成要素への射影 (projection) という関数が2つある、ということだ。Haskellでは、これら2つの関数はfstとsndと呼ばれ、それぞれペアの最初と2番目の要素を選択する。

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$と2つの射$p$と$q$で構成され、それぞれ$a$と$b$に接続される。

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つのタプル、すなわちトリプルだ。これを正当な候補にする2つの射を以下に示す（ここではトリプルに対してパターンマッチングを使っている）。

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'$で共通の係数だ。

ある種の直観を築くために、2つの正準射影 (canonical projection) fstとsndを持つペア(Int, Bool)が、前に提示した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はどちらもトリプルの第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つの型からなるタグ付き共用体だ。C++がサポートしている共用体はタグ付けされていない。つまり、プログラム内では共用体のどのメンバーが有効であるかを何らかの方法で追跡しなければならないということだ。タグ付き共用体を作成するには、タグ――列挙型――を定義して共用体と結びつける必要がある。たとえば、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で次のように定義されている：

Either a b = Left a | Right b

これはaとbの2つの型によってパラメーター化され、2つのコンストラクターを持つ。Leftは型aの値をとり、Rightは型bの値を取る。

積について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関数）がある一方で、戻ってくる射はないことに注意してほしい。単集合では、どの集合からも一意な射が来るうえに、（空集合を除く）すべての集合へ向かう外向きの射もある。これまで見てきたように、終対象から発するこれらの射は、他の集合の要素を選択するのに非常に重要な役割を果たしている（空集合には要素がないので、選択するものは何もない）。

単集合と積の関係は、余積とは全く違う。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}$で射として使う関数の特性だ。関数は（一般に）非対称だ。説明しよう。

関数は、その始域のすべての要素に対して定義する必要がある（プログラミングでは、全関数 (total function) と呼ぶ）。しかし、終域全体を網羅する必要はない。すでにその極端な例をいくつか見てきた。単集合からの関数――終域内の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; }

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

5.9 参考文献

1. The Catsters, Products and Coproducts video.

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

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

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

6.1 直積型

プログラム言語における2つの型の積の正統な実装はペアだ。Haskellではペアはプリミティブな型コンストラクターだ。C++では比較的複雑なテンプレートとして標準ライブラリで定義されている。

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

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

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

ペアの中にペアをネストすれば型をいくつでも積に結合できるが、もっと簡単な方法がある。ネストされたペアはタプルと等価なのだ。これは、ペアをネストする様々な方法が同型であるという事実からの帰結だ。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の値と単位の組み合わせは、何の情報も追加しない。型：

(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

同様に、(,,)を使ってトリプルを作成する、などもできる。

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

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)

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

startsWithSymbol e = symbol e `isPrefixOf` name e

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

6.3 直和型

集合の圏の積が直積型を生み出すのと同じように、余積は直和型を生み出す。Haskellにおける直和型の標準的な実装は次のようなものだ：

data Either a b = Left a | Right b

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

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++で同等のものであるunionや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++でunionが直和型として使われることはめったにない。含められるものに厳しい制限があるからだ。std::stringでさえ、コピー・コンストラクターを持っているので、unionに入れられない。

6.4 型の代数

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

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

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

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

加算と乗算をつなぐもう1つのものとして、分配法則がある：

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) と呼ばれることがある。しかし、そのことを除けば、リグを形成する自然数などに関する命題を型に関する命題に変換することで、多くのメリットが得られる。興味深い項目を含む変換表を以下に示す：

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

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か、トリプルa*a*aか、などなど……。まさにそれがリストだ。一連のaだ！

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

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

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

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

6.5 課題

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

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

   data Shape = Circle Float
                  | Rect Float Float

   Shapeに作用し面積を求めるareaのような関数を定義したい場合は、次の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$の下の像を$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つの方法で解釈できる。1つは、関数(a -> b)を1つの引数と捉えて、関数(Maybe a -> Maybe b)を返しているとする解釈だ。もう1つは、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
= { definition of fmap }
  Nothing
= { definition of id }
  id Nothing

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

  fmap id (Just x)
= { definition of fmap }
  Just (id x)
= { definition of id }
  Just x
= { definition of id }
  id (Just x)

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

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

まずはNothingのケース：

  fmap (g . f) Nothing
= { definition of fmap }
  Nothing
= { definition of fmap }
  fmap g Nothing
= { definition of fmap }
  fmap g (fmap f Nothing)

次はJustのケース：

  fmap (g . f) (Just x)
= { definition of fmap }
  Just ((g . f) x)
= { definition of composition }
  Just (g (f x))
= { definition of fmap }
  fmap g (Just (f x))
= { definition of fmap }
  fmap g (fmap f (Just x))
= { definition of composition }
  (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 List関手

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

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に変換することだ。（空でない）リストが頭部と尾部のConsとして定義されている場合、実際にはどうやるのだろうか？ fを頭部に適用し、リフト（fmap）されたfを尾部に適用すればよい。これは再帰的な定義だ。リフトされたfをリフトされたfを用いて定義しているからだ：

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

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

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

C++に慣れている場合は、最も汎用的なC++コンテナと見なせるstd::vectorの場合を考えてみてほしい。 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, ", "));

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

7.1.7 Reader関手

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

(->) a b

通常の関数と同様に、複数の引数を持つ型関数も部分適用できる。したがって、矢印に対して型引数を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と呼ばれる）は型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インスタンスからの実装を使い、内側のものに対してはlist関手の実装を使う必要があることを理解する。上記のコードを次のように書き換えられるのは、すぐには自明に思えないかもしれない：

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. List関手について関手の規則を証明せよ。適用するリストの尾部について規則が真であると仮定する（言い換えると、帰納法を使う）。

8 関手性

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

8.1 双関手

関手は$\mathbf{Cat}$（圏の圏）の射であるため、射――典型的には関数――に関する直観の多くは関手にも当てはまる。たとえば、2つの引数を取る関数と同じように、2つの引数を取る関手、すなわち双関手 (bifunctor) が存在しうる。対象について、双関手は対象のすべてのペアを写す。1つは圏$\mathbf{C}$から、もう1つは圏$\mathbf{D}$から、圏$\mathbf{E}$の対象に写す。これは単に、圏のカルテシアン積 (Cartesian product) $\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は双関手を表す。これは、どの型シグネチャーにおいても常に2つの型引数に適用されているのが分かる。最初の型シグネチャーは、2つの関数を同時に写すbimapを定義している。その結果はリフトされた関数(f a b -> f c d)であり、双関手の型コンストラクターが生成する型に対して作用する。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番目の関数を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は、aに作用するConst ()として表せる（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は無視する）。

新しいデータ型BiCompは、aおよびb内の双関手だが、bf自体がBifunctorであり、fuおよびguがFunctorである場合に限る。コンパイラーは、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が関手だと証明する必要はなかったと分かった。この事実は、2つの関手的プリミティブの和という構築方法から導かれたものだ。

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

{-# LANGUAGE DeriveFunctor #-}

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

data Maybe a = Nothing | Just a
  deriving Functor

すると、対応するfmapが自動的に実装される。

代数的データ構造の正則性 (regularity) により、Functorだけでなく、前に述べたEq型クラスを含む、いくつかの型クラスのインスタンスを派生させられる。コンパイラーに独自の型クラスのインスタンスを派生させるように教えるという選択肢もあるが、それはもう少し高度だ。もっとも、基本的な構成要素に対する動作と和と積とを提供し、残りの部分はコンパイラーに計算させるという考え方は変わらない。

8.4 C++での関手

C++プログラマーなら、関手の実装に関しては、明らかに自分でやることになる。しかし、C++でもある種の代数的データ構造は見つかるはずだ。そのようなデータ構造を総称テンプレートにすれば、fmapを素早く実装できるだろう。

データ木構造を見てみよう。Haskellでは再帰的な直和型として定義される：

data Tree a = Leaf a | Node (Tree a) (Tree a)
    deriving Functor

前にも述べたように、C++で直和型を実装する方法の1つは、クラス階層を使うことだ。オブジェクト指向言語では、fmapを基底クラスFunctorの仮想関数として実装し、それをすべてのサブクラスでオーバーライドするのが自然だ。残念ながらこれは不可能だ。なぜなら、fmapはテンプレートであり、それが作用する対象の型（thisポインタ）だけでなく、それに適用された関数の戻り型によってもパラメーター化されているからだ。C++では仮想関数はテンプレート化できない。fmapを総称フリー関数として実装し、パターンマッチングをdynamic_castに置き換えよう。

基底クラスでは、動的キャストをサポートするために少なくとも1つの仮想関数を定義する必要があるため、デストラクターを仮想関数にする（いずれにしても良い考えだ）：

template<class T>
struct Tree {
    virtual ~Tree() {};
};

Leafは、Identity関手を偽装したものだ：

template<class T>
struct Leaf : public Tree<T> {
    T _label;
    Leaf(T l) : _label(l) {}
};

Nodeは直積型だ：

template<class T>
struct Node : public Tree<T> {
    Tree<T> * _left;
    Tree<T> * _right;
    Node(Tree<T> * l, Tree<T> * r) : _left(l), _right(r) {}
};

fmapを実装するときには、Treeの型で動的ディスパッチを利用する。Leafの場合はIdentity版のfmapを適用し、Nodeの場合は2つのTree関手で構成された双関手のように扱う。C++プログラマーとしては、これらの用語を使ってコードを分析することに慣れていないかもしれないが、圏論的な考え方を実践するには適している。

template<class A, class B>
Tree<B> * fmap(std::function<B(A)> f, Tree<A> * t)
{
    Leaf<A> * pl = dynamic_cast <Leaf<A>*>(t);
    if (pl)
        return new Leaf<B>(f (pl->_label));
    Node<A> * pn = dynamic_cast<Node<A>*>(t);
    if (pn)
        return new Node<B>( fmap<A>(f, pn->_left)
                          , fmap<A>(f, pn->_right));
    return nullptr;
}