1. 圏論とプログラミング、プロダクト

プログラマのための圏論の基礎
- Categories for the Working Programmer -
池渕未来
作成 2013/09/03

章内目次 : はじめに プロダクト Haskell から

はじめに

圏論とは何でしょうか。私が初めて「圏論」という言葉を見たときは、字面からその意味が想像しづらく、「圏」という言葉に少し近寄りがたい雰囲気を感じた記憶があります。その後インターネットで検索してみたり、タイトルに「圏論」の文字列がある数学書の最初のほうを読んでみたりしたのですが、その頃の私は数学もろくに知らない高校生だったので何がなんだかよく分かりませんでした。こんな風に、圏論は言葉だけよく聞くけど何のことだか分からない、という人も多いのではないでしょうか。

標準的な圏論の教科書を開いてみると、まず最初に圏の定義が書いてあります。「いきなり定義を言われたって分からない!」と思うかもしれません。しかし多くの数学書は辞書のように使うためか、読み手に苦労して考えさせ、一人前の数学者を育てるために作られているので仕方がありません。

そこで、本記事は圏論を学びたいプログラマを対象に絞って説明していきます。かと言って数学的厳密性は損わないようにするので、じっくりゆっくり圏論を学んで行きましょう。

圏論とはどんなものか

圏論とは? という問いに一言で答えるとすると、二通りの考え方があります。一つ目としてまず、一部の研究者は「圏論とは理論だ」と考えています。圏論は理論というと当たり前みたいですが、実は圏の理論を掘り進める研究者や、圏の理論の奥深いところにある結果を使う研究者は数学者の中でも少数なのです。二つ目として、多くの研究者は「圏論とは言葉だ」と考えています。これは、何かモノの定義が与えられているとき、圏論の考え方を使うとそのモノを別のある特定の言葉で書き直せる、ということです。これは「圏論はモノに別の見方を与える」とも言い換えられます。数学者であっても多くは後者の「言葉」としての圏論の使い方をしています。

「モノに別の見方を与える」ことはプログラミングにおいても有用です。モノを色々な視点から見ていくと、二つの異なったモノが似て見えてくることがあります。もしそうなれば片方のモノの問題がもう片方のモノの問題に帰着され、たとえばアルゴリズムにおいてはアルゴリズムを考える手助けになります。また、視点を変える技術を身につけることで、モノの本質を見出しやすくなります。

これについて、アルゴリズム設計の観点から Jon Kleinberg, Eva Tardos 著の "Algorithm Design" の序文から以下を引用します。

アルゴリズム設計は、「問題の中の数学的にきれいな核を見出す作業」と「問題の構造に基づく、適切なアルゴリズム設計の技法を明確にする作業」の二つの基本的な要素から成る。(著者訳)

"Algorithm Design" は圏論については触れていませんが、ここで挙げられた「数学的にきれいな核を見出す作業」には圏論の考え方が活かされるでしょう。

抽象的に書かれても理解しづらいかもしれませんから、次節 では二つの異なったモノが一つに見える例を実際に扱っていきます。

圏論がどんなものかについての解説として、東京大学の蓮尾一郎先生による短くて分かりやすい記事もあります:圏論は数学をするための「高級言語」

プロダクト

ここからは「異なったものが一つに見える」例として、「自然数の ${\rm max}$ 関数」と「集合の直積」について考えていきます。

まず、自然数に対する ${\rm max}$ を見てみます。${\rm max}$ は、二つの自然数 $n, m$ を受け取って $n, m$ のうち大きい方を返します。定義を書くと以下になります。 \[ {\rm max}(n,m) = \begin{cases} m & (n \le m)\\ n &(n > m) \end{cases} \]

次に集合の直積について確認します。集合 $A$ と集合 $B$ の直積とは、$A$ の要素と $B$ の要素の組の集まりです。これは普通 $A \times B$ と書きます。たとえば、 \[ A = \{1, 3, 4\},\, B = \{\text{'a'}, \text{'k'}\} \] のとき \[ A \times B = \{(1, \text{'a'}), (1, \text{'k'}),(3, \text{'a'}), (3, \text{'k'}), (4, \text{'a'}), (4, \text{'k'})\} \] となります。プログラムの言葉だとタプル型(無名構造体)ですね。

${\rm max}$ と直積は定義を見ると違うように見えるかもしれませんが、${\rm max}$と他の自然数、直積と他の集合との「関係」を見るように視点を変えてみましょう。この視点の変え方が、圏論のアイデアとなってくるのです。

それでは、${\rm max}(n, m)$ と他の自然数、たとえば $n, m$ の関係を見てみましょう。「関係」と言うとたくさんあり過ぎてしまうので、今は「大小関係」を考えることにしてみます。すると、以下のような関係が言えます。 \[ n, \,m \le {\rm max}(n,\,m) \] $\le$、$\ge$ をその向きに合わせてそれぞれ左矢印($\leftarrow$)、右矢印($\rightarrow$)に書き直すと以下のように図で表せます。 \begin{xy} \xymatrix{ n & \text{max}(n,m) \ar[l]_{(\le)} \ar[r]^{(\ge)} &m } \end{xy}

直積 $A \times B$ と $A,\,B$ との関係についてはどうでしょうか。${\rm max}$ のときは自然数とその間の大小関係について議論しましたが、今度は自然数ではなく集合についての議論です。集合 $X,\,Y$ の間の「関係」と言ったら「$X,\,Y$ の間にある関数が存在するという関係」を指すことにします。すると、以下のような図が書けます。 \begin{xy} \xymatrix{ A & A \times B \ar[l]_\varphi \ar[r]^\psi & B } \end{xy} $X \xrightarrow{f} Y$ は「$f$ は集合 $X$ から集合 $Y$ への関数である」を意味します。$f:X \rightarrow Y$ と書いても同じことです。プログラムの言葉では $f$ の型が $X \rightarrow Y$ だと言えますね。$\varphi,\,\psi$ として、たとえば $\varphi(a,b) = a,\,\psi(a, b) = b$ で定義される関数が挙げられます。Haskell や OCaml だと fst, snd に対応します。本記事ではこの関数を fst、snd とは書かず $\pi_1,\,\pi_2$ と書きます。

max と直積の性質が同じ形の有向グラフで表されました。max のときはノードに自然数、エッジに大小関係が対応し、直積のときはノードに集合、エッジに関数が対応しています。これでちょっと ${\rm max}$ と直積が似て見えてきましたね。

もっと精密に - ${\rm max}$ 編

上で ${\rm max}$ と直積に共通点が見えましたが、これだけではなんだか物足りません。まず ${\rm max}$ のほうを見てみると、$n \le x \ge m$ をみたす $x$ は ${\rm max}(n, m)$ 以外にもいくらでもあるのですから、ちょっと範囲が広すぎてしまいます。そこで、$n,m$ 以外にも他の自然数と ${\rm max}$ の関係を考えてみればどうでしょう。今は ${\rm max}(n,m)$ 以外で $n \le x \ge m$ をみたす自然数 $x$ が問題だったので、

$n \le x \ge m$ をみたす自然数 $x$ と ${\rm max}(n,m)$ との関係は?

を考えてみます。$n=2,\,m=3$ と具体的な値を代入してみると、${\rm max}(2, 3) = 3$ であり、$x$ としては $ 3, 4, 5, \cdots$ が取れます。これからすぐ分かるように、上をみたすどんな $x$ に対しても \[ {\rm max}(n, m) \le x \] が成立っています。これを一つの有向グラフで表すと、 \begin{xy} \xymatrix{ & x \ar[ld] \ar[d] \ar[rd] & \\ n & \text{max}(n,m) \ar[l] \ar[r] & m } \end{xy} と書けます。言葉で正確に書くと、

  1. $n \le {\rm max}(n, m) \ge m$
  2. $n \le x \ge m$ をみたすどんな $x$ に対しても ${\rm max}(n, m) \le x$

の二つが成り立っていることになります。1.) だけ考えると ${\rm max}(n,m)$ 以外でも成り立ってしまいましたが、2.) も合わせればそんなことは起こりません。実際、$n=2,\,m=3$ とした図を考えてみると、 \begin{xy} \xymatrix{ & x \ar[ld] \ar[d] \ar[rd] & \\ 2 & 3 \ar[l] \ar[r] & 3 } \end{xy} となります。${\rm max}(2,3) = 3$ の代わりに $4$ を上の図に入れてみると \begin{xy} \xymatrix{ & x \ar[ld] \ar[d] \ar[rd] & \\ 2 & 4 \ar[l] \ar[r] & 3 } \end{xy} となりますが、$x = 3$ を代入すると下向きの矢印は $ 4 \le 3$ を主張することになり、これは明かに矛盾していますね。一般の場合の証明は難しくないので書きませんが、このように 1.), 2.) をみたすような自然数は ${\rm max}(n,m)$ のみになるのです。

この事実によって、1.), 2.) は ${\rm max}$ のある性質を取り出したというより、${\rm max}$ そのものを指していると言えます。数式による定義から、図による自然数の間の関係へと「視点を変えた」のです。

もっと精密に - 直積編

直積についても同様のことを考えます。つまり、集合 $X$ について $X \xrightarrow{f} A$、$X \xrightarrow{g} B$ という二つの関数が存在するとき、$X$ と $A\times B$ の関係を考えてみます。直積の場合は「関数が存在する」という関係を考えていたので、ここでも $X$ と $A\times B$ の間に関数が存在するかどうかを調べましょう。存在することを言うには実際に関数を作ってみれば OK です。そこで、仮定で述べた $f, g$ を使えば、$h(x) = (f(x), g(x))$ と定義することによって関数 \[ X \xrightarrow{h} A \times B \] の存在が言えます。これも一つの図で表すと、 \begin{xy} \xymatrix{ & X \ar[ld]_f \ar[d]_h \ar[rd]^g & \\ A & A\times B \ar[l]^\varphi \ar[r]_\psi & B } \end{xy} と書けます。言葉で書くと、

  1. $A \times B \xrightarrow{\varphi} A,\, A\times B \xrightarrow{\psi}$ なる $\varphi,\,\psi$ が存在
  2. $X \xrightarrow{f} A,\, X \xrightarrow{g} B$ なるどんな $f,\,g$ に対しても $X \xrightarrow{h} A \times B$ が存在

なんと、${\rm max}$ のときの図とまったく同じ形になりました。

……とここで話を終わらせてはいけません。${\rm max}$ のときは条件 1.), 2.) で ${\rm max}$ を特徴付けられていましたが、実は直積の場合 $A\times B$ とは似ても似つかぬ集合でも 1.), 2.) はみたされてしまうのです。

$A = \{1,3,4\},\,B=\{\text{'a'},\text{'k'}\}$、$A\times B$ の代わりを $\{0\}$ とすれば $\{0\}$ は 1.), 2.) をみたす

(1.): $\{0\} \xrightarrow{\varphi} A,\, \{0\} \xrightarrow{\psi} B$ という関数を作れば存在が示されるので、たとえば $\varphi(x) = 1,\, \psi(x) = \text{'a'}$ と定義すれば良い。

(2.): $h(x) = 0$ と定義すれば良い。

こういうわけで 1.), 2.) は直積の別の見方を与えるには不十分だったようです。上の例から察せるかもしれませんが、直積の場合の 1.), 2.) は「関数の存在」についての条件でしたが、ほとんどの集合の間には一つ以上関数が存在するので、条件としては弱すぎたのです。

そこで、「関数の存在」の条件だけではなく「関数の性質」についての二つの条件を加えてみます。

可換性(commutativity)は直積の図 \begin{xy} \xymatrix{ & X \ar[ld]_f \ar[d]_h \ar[rd]^g & \\ A & A\times B \ar[l]^\varphi \ar[r]_\psi & B } \end{xy} の中の二つの小さい三角形について、どちらの経路を通っても同じ関数を表すことを示しています。

普遍性(universality)は、$h$ が可換性をみたしているとき、

もし関数 $X\xrightarrow{h'} A\times B$ も可換性、すなわち $f = \varphi \circ h',\, g = \psi \circ h'$ をみたすならば、$h = h'$

とも言い直せます。関数 $h$ が唯一つだけ存在するとき、有向グラフ内では $h$ のところのエッジを破線で表すことがよくあります。 \begin{xy} \xymatrix{ & X \ar[ld]_f \ar@{.>}[d]_h \ar[rd]^g & \\ A & A\times B \ar[l]^\varphi \ar[r]_\psi & B } \end{xy}

まず直積 $A\times B$ は $\varphi = \pi_1$、$\psi = \pi_2$ と代入すると可換性と普遍性をみたすことを確かめましょう。直積の場合、$h(x) = (f(x),\,g(x))$ と $X \xrightarrow{h} A \times B$ が定義されていたので、可換性は \[ (\pi_1 \circ h)(x) = \pi_1 (f(x),\,g(x)) = f(x)\\ (\pi_2 \circ h)(x) = \pi_2 (f(x),\,g(x)) = g(x) \] から分かります。普遍性については、もし $h'$ が可換性をみたすならば、 \[ (\pi_1 \circ h')(x) = f(x)\\ (\pi_2 \circ h')(x) = g(x) \] となりますが、これにより $h'(x) = (f(x),\,g(x))$ が成り立ち、$h'$ は $h$ と等しいと分かり、普遍性が成立します。

先程の例題の $\{0\}$ は可換性をみたさないことを見てみます。

$A = \{1,3,4\},\,B=\{\text{'a'},\text{'k'}\}$、$A\times B$ の代わりを $\{0\}$ としたとき、$\{0\}$ は可換性をみたさない。ただし $\varphi(x) = 1$、$\psi(x) = \text{'a'}$。

$X = A\times B,\,f = \pi_1,\,g = \pi_2$ と置く(注意:ここでは $\varphi,\,\psi$ ではなく $f,\,g$ に $\pi_1,\,\pi_2$ を代入しているので気を付けてください)。 \begin{xy} \xymatrix{ & A\times B \ar[ld]_f \ar[d]_h \ar[rd]^g & \\ A & \{0\} \ar[l]^\varphi \ar[r]_\psi & B } \end{xy} ここで $f,\, \varphi \circ h$ にそれぞれ $(3, \text{'a'})$ を引数に渡すと \[ f(3,\text{'a'}) = \pi_1(3,\text{'a'}) = 3\\ (\varphi \circ h)(3,\text{'a'}) = \varphi(h(3,\text{'a'})) = 1 \] となり、$f \neq \varphi \circ h$ が言える。よって $\{0\}$ は可換性をみたさない。

一般に、1.), 2.) と可換性・普遍性をみたすような集合は必ず $A \times B$ と同じ形をしていることが示せますが、ここでは示さず次の章で解説します。

注意:「同じ形」という語を使いましたが、これは「$A\times B$ とまったく等しい」ということではありません。正確には「同型」という用語を使うのですが、これについては次の章で説明します。

このように、 1.), 2.)、可換性および普遍性は直積の別の視点からの見え方なのです。

${\rm max}$ の場合の可換性・普遍性は?

${\rm max}$ の場合は可換性・普遍性はどうなっているのでしょう。直積の場合の条件に可換性・普遍性を付け加えたのに、${\rm max}$ の場合にそれらを付け加えた結果もし議論がおかしなことになったら困ります。

可換性・普遍性の条件をもう一度書いてみると、以下の有向グラフ \begin{xy} \xymatrix{ & X \ar[ld]_f \ar[d]_h \ar[rd]^g & \\ A & A\times B \ar[l]^\varphi \ar[r]_\psi & B } \end{xy} のように関数が与えられているとき、

という条件でした。可換性には $\varphi \circ h$ などと関数の合成が出てくるので、大小関係についても合成を定義する必要があります。大小関係の合成は、以下のように考えるのが自然でしょう。 \[ (a \le b) \circ (b \le c) = a \le c \] 可換性の条件を、関数ではなく大小関係について書いてみると、 \[ n \le x = (n \le {\rm max}(n,m)) \circ ({\rm max}(n,m) \le x)\\ m \le x = (m \le {\rm max}(n,m)) \circ ({\rm max}(n,m) \le x) \] となります。これは定義から明かに成り立っていますね。

普遍性の方は「${\rm max}(n,m) \le x$ という関係は唯一つ存在する」と言い換えられます。けれども ${\rm max}(n,m) \le x$ が「唯一つ」存在するなどと個数を指定するのはなんだか違和感があります。普通は ${\rm max}(n,m) \le x$ の個数なんて考えません。しかしそれでは議論ができないので、関係の個数を新しく定めてやりましょう。${\rm max}(n,m) \le x$ などの関係は、同じものが二つや三つあっても仕方がないので

関係 $P$ の個数は、$P$ が成り立っていれば $1$、成り立っていなければ $0$

とするのが自然でしょう。こうすると、普遍性は「${\rm max}(n,m) \le x$ が成り立つ」と言い換えられます。これは 2.) の条件から既に成立しているので、普遍性は条件として付け足す必要はありません。

つまり、可換性・普遍性を条件に加えても ${\rm max}$ の場合は仮定せずとも最初から成り立っているので不都合が起きることはないのです。

注意:これまで「$a \le b$ という関係」という言葉を使ってきましたが、$a \le b$ は厳密な数学用語としては「関係」ではなく「式(formula)」です。個数を定めた枠内の「関係 $P$」についても同じです。

式は集合で構成された数学的対象ではないので、本当は $(a \le b) \circ (b \le c) = a \le c$ などと定義したりはできません。この問題が気にかかる方は、ここでは「$a \le b$ が成り立っているときに "$a \le b$" という文字列を考えている」などのように解釈しておいて下さい。

まとめ、そして圏

長々と議論してきた結果、${\rm max}$ も直積も同じ図で表現でき、 1.), 2.)、可換性および普遍性が成り立つことが分かりました。これが、「違ったものが一つに見える」ということの例なのです。

1.), 2.) や可換性・普遍性を述べるのに有向グラフを使いました。${\rm max}$ の場合はノードに自然数、エッジに大小関係を、直積の場合はノードに集合、エッジに関数を対応させていましたね。これを表にしてみます。

ノード エッジ
${\rm max}$ 自然数 大小関係
直積 集合 関数

これまでの議論は、${\rm max}$ や直積はノードとエッジが何を指すかという枠組みを取り替えただけで、あとはまったく同じだと示したとも言い替えられます。

圏論の入門だというのにこれまで圏という言葉は出しませんでしたが、実はみなさんはもう既に圏の概念に触れています。先程、${\rm max}$ や直積はノードとエッジが何を指すかという枠組みを取り替えただけだと述べましたが、この「枠組み」を表現するのが圏なのです。

もう少し具体的に書くと、圏とは「ノードに対応させたいモノ」の集まりと「エッジに対応させたいモノ」の集まりの組です。以下に定義を書きます。

圏とは二つの集まり $N : A, B,\cdots$ と $E : f, g, \cdots$ の組で以下をみたすものである:

  1. $E$ の要素 $f$ は始点 $A$、終点 $B$ を持つ。ここで $A,\,B$ は $N$ の要素である。$f$ を始点と終点を合わせて $A \xrightarrow{f} B$ とも書く。
  2. $A \xrightarrow{f} B$、$B \xrightarrow{g} C$ について、それらの合成 $A \xrightarrow{g\circ f} C$ が定まっている。
  3. $A \xrightarrow{f} B,\, B \xrightarrow{g} C,\, C \xrightarrow{h} D$ について、結合法則 $h \circ (g \circ f) = (h \circ g) \circ f$ が成り立つ。
  4. 任意の $A$ について $A \xrightarrow{{\rm id}_A} A$ が存在し、${\rm id}_A \circ f = f,\,g \circ {\rm id}_A = g$ が成り立つ。

$N$ の要素のことを対象(object)、$E$ の要素のことを射(morphism, arrow, map)、${\rm id}_A$ のことを恒等射と呼ぶ。

また、圏 $\mathcal{C}$ に対して対象の集まり $N$ を ${\rm Ob}(\mathcal{C})$ と書き、対象 $A,\,B$ の間の射 $A \rightarrow B$ の集まりを ${\rm Hom}_\mathcal{C}(A,B)$ と書く。

上の定義は、有向グラフで言うとノードに対応させたいモノの集まりが $N$ で、エッジに対応させたいモノの集まりが $E$ になります。四つの条件は、射の性質について述べています。それぞれを言葉で書くと

  1. エッジの始点と終点の存在
  2. エッジの合成の存在
  3. 合成の結合法則
  4. 恒等的なエッジ(恒等射)の存在

と言えます。これら、とくに 2.) や 4.) の合成、恒等射が何なのかを ${\rm max}$ や直積の例で見てみましょう。

まず ${\rm max}$ のときは、ノードを自然数、エッジを大小関係とする有向グラフを考えましたね。これは $N$ として自然数全体、$E$ として自然数の間の大小関係を取った圏を与えます。この圏を $\mathcal{O}{\it rd}_\mathbb{N}$ と書くとすると、自然数 $n,\,m$ に対して \[ {\rm Hom}_{\mathcal{O}{\it rd}_\mathbb{N}}(n,m) = \begin{cases} \{m \le n\} & (m \le n \text{ のとき})\\ \{ \} & (\text{そうでないとき}) \end{cases} \] となります。2.) の合成は \[ (n \le m) \circ (m \le k) = n \le k \] と与えていました。4.) の恒等射は \[ a \le a \] が対応しています。

次に直積のときは、ノードが集合、エッジが関数でしたから $N$ として集合全体、$E$ として集合の間の関数全体を取った圏を与えます。この圏は一般に ${\it \mathcal{S}et}$ と書かれ、集合の圏と呼ばれます。${\rm Hom}_{\mathcal{S}{\it et}}(A, B)$ は $A$ から $B$ への関数全体になります。集合の圏において合成は \[ (f \circ g)(x) = f(g(x)) \] で与えられ、恒等射は \[ {\rm id}(x) = x \] という関数が対応しています。

${\rm max}$ や直積は、圏の言葉で言うとプロダクト(product)として以下のように定義されます。

圏 $\mathcal{C}$ の対象 $A,\,B,\,P$ について、$P$ が $A,\,B$ のプロダクトであるとは、

\[ f = \varphi \circ h,\,g = \psi \circ h \] をみたす $X \xrightarrow{h} P$ が唯一つ存在するときに言う。 \begin{xy} \xymatrix{ & X \ar[ld]_f \ar@{.>}[d]_h \ar[rd]^g & \\ A & A\times B \ar[l]^\varphi \ar[r]_\psi & B } \end{xy}

$A,\,B$ のプロダクトを一般に $A\times B$ と書く。

1.), 2.)、可換性、普遍性の言い換えになっています。${\rm max}$ と直積は、圏の言葉ではどちらも同じプロダクトとして見れるのです。

ハート

いくつか用語を導入します。まず、プロダクトを定義するのに有向グラフを使いましたね。このような有向グラフのことを「可換図式」と呼びます。

次に、$X \xrightarrow{f} A,\, X \xrightarrow{g} B$ に対して唯一つ存在する $X \xrightarrow{h} A \times B$ にも名前があります。この $h$ は $f$ と $g$ を組合せるような作用をすることから、$f$ と $g$ の mediating と呼びます。$h$ を $\langle f,g\rangle$ と書くこともあります。

また、プロダクトは通常「圏論的直積」または単に「直積」と呼ばれますが、本記事内では混同を避けるためにプロダクトと呼ぶことにします。

Haskell から

この節では関数型言語 Haskell をある程度知っている方向けに書きます。前節では直積のところで $X \xrightarrow{f} A,\, X \xrightarrow{g} B$ に対して $X \xrightarrow{h} A \times B$ という関数を考えました。実はこの関数は Haskell の Control.Arrow モジュールで (&&&) という名前で実装されています。

ghci で (&&&) の型を見てみましょう。

Prelude> :m Control.Arrow
Prelude Control.Arrow> :t (&&&)
(&&&) :: Arrow a => a b c -> a b c' -> a b (c, c')

Arrow という型クラスが登場しています。Arrow にあまり慣れていない方は、ここでは Arrow の主なインスタンスである (->) のみを考えるので (&&&) の型は

(&&&) :: (b -> c) -> (b -> c') -> b -> (c, c')

と解釈しておいて下さい。この型に合わせて可換図式を書くと \begin{xy} \xymatrix{ & b \ar[ld]_f \ar@{.>}[d]|{f\&\&\&g} \ar[rd]^g & \\ c & (c,c') \ar[l]^{\rm fst} \ar[r]_{\rm snd} & c' } \end{xy} となり、mediating である $h$ が f &&& g そのものになっています。インスタンス (->) では (&&&) は以下のような振る舞いをします。

(f &&& g) x = (f x, g x)

ここで、point free style について確認します。point free style は、引数を取らずに関数を定義するというプログラミングスタイルを指します。たとえばリスト xs の長さを二倍する関数 f は

f xs = 2 * length xs

と書けますが、これを point free style に直すと

f = (2 *) . length

と書けます。point free style においてはリストや数値ではなく関数が基本であると言えます。

直積 $A \times B$ の定義を思い出してみてください。$A \times B$ とは、$A$ の要素 $a$ と $B$ の要素 $b$ の組 $(a,b)$ の集合でした。この定義では集合から要素を取って新しい集合を作っていますが、圏の言葉ではそんなことはせず、すべて射(ここでは関数のこと)の性質で直積を記述しています。このように圏論においては射が中心の議論が基本的です。この考え方は関数が基本の point free style に通じていますね。以下で例を挙げてみます。

関数 f x = (x^2, x^3) を point free style に直せ。

色々な回答があるかもしれませんが、ここでは次のように考えてみます。

関数 f は関数 (^2), (^3) を組合せてできている

関数の組合せといえば、mediating です。Arrow では f と g の mediating は f &&& g でしたから、例題の答えは

f = (^2) &&& (^3)

となります。

これを応用すると、たとえば f x = x^2 + x^3 を次のように point free style に直せます。

f = uncurry (+) . (^2) &&& (^3)

Arrow には他にも (***) という関数があります。

(***) :: (b -> c) -> (b' -> c') ->  (b, b') -> (c, c')

この型に合わせて可換図式を書くと \begin{xy} \xymatrix{ b \ar[d]_f & (b, b') \ar[l]_{\rm fst} \ar[d]_{f***g} \ar[r]^{\rm snd} & b' \ar[d]_g \\ c & (c,c') \ar[l]_{\rm fst} \ar[r]^{\rm snd} & c' } \end{xy} となります。これは $f$ と ${\rm fst}$ 、$g$ と ${\rm snd}$ を合成してそれぞれ一つの関数だと思うと次のように書き直せます。 \begin{xy} \xymatrix{ & (b, b') \ar[ld]_{f \circ {\rm fst}} \ar[d]_{f***g} \ar[rd]^{g \circ {\rm snd}} & \\ c & (c, c') \ar[l]_{\rm fst} \ar[r]^{\rm snd} & c'} \end{xy} ここから、f *** g = (f . fst) &&& (g . snd) が分かります。(***) も (&&&) の仲間なのです。値を渡してやると、f *** g は

(f *** g) (x, y) = (f x, g x)

という振る舞いをします。f *** g は f と g を平行につなげる、という言い方もできます。

(***) を使う関数の例を紹介しましょう。

文字列と整数の組 (str, n) を受け取り (str, n + 1) を返す関数 g (str, n) = (str, n + 1) を point free style に直せ。

与えられた関数 g は組 (str, n) の str のほうはそのまま返し、n のほうは +1 という関数を施しています。ここから、(***) を使うと

g = id *** (+1)

となります。これは map などの高階関数と組み合わせると、コードがきれいになります。

map (id *** (+1)) xs

もし (***) を使わずに素朴な書き方をすると

map (\(str, n) -> (str, n + 1)) xs

のようになり、(***) を使ったほうがすっきりして見えますね。

ハート

前の節では ${\rm max}$ と直積が、どちらも同じプロダクトとして見れると述べました。そこで、${\rm max}$ についての関数も直積についての関数と同じ実装ができないか、もっと言うとプロダクトという型クラスを作れば ${\rm max}$ と直積がそのインスタンスにできるのでは? という疑問が湧き上がります。これは残念ながら Haskell では型システムの制限で ${\rm max}$ と直積を包むような型クラスは書けないのですが、高階型の使える言語 Coq では実装できます。以下に実装したコードへのリンクを貼るので、Coq の知識があって興味のある方は読んでみてください。

product.v