このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

［参照用 記事］

圏論的コンストラクタと圏論的オペレータ： 関手性・自然性の呪縛からの脱却

雑記／備忘

圏論で関手と自然変換が重要なのは言うまでもありません。しかし、これらに拘り過ぎるのもマズイのではないか、と思います。プログラミングにおける型構成子や総称関数は、関手・自然変換に対応しないことがままあります。トレースや不動点オペレータは、関手・自然変換ではないけど重要な圏論的構成素です。非関手的対応、非自然な変換も積極的に使いましょう。

内容：

圏論的コンストラクタと圏論的オペレータとは何か

最近、CADG（Categorical Abstract Differential Geometry）をまた調べています。CADGは十分な一般性を持つアブストラクト・ナンセンス（いい意味で）であり、複雑で多様な構成を必要とします。こういう状況では、関手でも自然変換でもないようなシロモノが色々と登場します。

先月、関手でも自然変換でもないようなモノを使う枠組みとして圏論的モダリティを紹介しました。モダリティを構成する素材として、非全域関手と非自然変換を説明しましたが、少し別な観点からこの記事で、非全域・非自然なモノを解説します。

CとDが圏のとき、|C|→|D|、または |C|→Mor(D) の形の写像を圏論的コンストラクタ（categorical constructor）と呼びましょう。典型的な例は、プログラミングにおける型構成子（type constructor）です。例えばリスト型構成子は、型Xに対して、Xのリスト型List(X)（プログラミングではList<X>と書くことが多い）を対応させます。型引数を持つ総称関数は、|C|→Mor(D) のタイプの圏論的コンストラクタになります。例えば、id<X> は、型（圏の対象）Xに“Xの恒等関数”を対応させる圏論的コンストラクタとみなせます。

Cが幾つかの圏の直積圏のときを考えましょう。C = C1×...×Cn とします。このとき、C上で定義されたコンストラクタは、|C1|×...×|Cn|→D または |C1|×...×|Cn|→Mor(D) の形です。プログラミングでは、幾つかの型引数を持つ型構成子／総称関数が、直積圏上の（圏論的）コンストラクタに対応します。例えば、2つのベクトル空間V, Wに対して、VからWへのゼロ線形写像をOV,Wとすると、V, W|→OV,Wは2つの対象にひとつの射を対応させるコンストラクタです。

圏論的コンストラクタは対象全域で定義される必要はありません。例えば、順序集合の圏Ordで、「対象Xの最小元を指定する」という操作を考えてみます。これは付点モダリティの例になります。Xに最小元があれば、⊥X:1→X が決まります。しかし、最小元がない順序集合はいくらでもあるので、X|→⊥X : |Ord|→Mor(Ord) は部分的にしか定義されません。

圏の射に射を対応させる写像を圏論的オペレータ（categorical operator）と呼びましょう。圏論的オペレータは、圏論的コンビネータ（categorical combinator）とも呼びます。この文脈での「オペレータ」と「コンビネータ」は同義語です。ただし、「圏論的コンビネータ」というと、S, K, Iなどを圏論的にゴニョゴニョすることだと思う人が多いので、主に「オペレータ」を使うことにします。「オペレータ」という言葉も多義的で曖昧なのですが、まーしょうがない。

例えば、A, B, Cを集合として、集合圏Setにおけるカリー化 (f:A×B→C)|→(Λ(f):A→CB) を考えてみましょう。これは、ΛA,B,C:Set(A×B, C)→Set(A, CB) という集合（Setの対象）3つで添字付けられた写像の族です。このように、圏論的オペレータの実体は、ホムセットのあいだの写像として与えられます。圏Cの構造を与える結合（composition）も、γA,B,C:C(A, B)×C(B, C)→C(A, C) という形の圏論的オペレータです。

圏論的オペレータは、シーケント計算の推論規則の形に書けます（「圏論の筆算としてのシーケント計算」参照）。直積をカンマ、指数（関数空間）を含意記号'⊃'で書くとして、カリー化は：

  A, B ⇒ C
 -----------[Curry = 左含意導入]
  A ⇒ B⊃C

圏の結合なら：

 A ⇒ B    B ⇒ C
 -----------------[Comp = カット]
     A ⇒ C

コンストラクタのなかには、シーケント計算の公理の形に書けるものもあります。A|→idA はそのようなコンストラクタです。

     *（前提なし）
 ---------------[Id = 同一律]
    A ⇒ A

圏論的コンストラクタと圏論的オペレータの区別は必ずしも明確ではありませんし、明確にする必要もないでしょう。関手の射部分（morphism part）をホムセットごとの関数で表した FX,Y:C(X, Y)→D(F(X), F(Y)) は、射から射を作り出しているので圏論的オペレータですが、|C|×|C|→Mor(Set) の形のコンストラクタだとも言えます。おおよその分類基準を書いておくと：

  • 対象のコンストラクタ： いくつか（0個, 1個, 2個, ...）の対象に対して対象を対応させる。
  • 射のコンストラクタ： いくつか（0個, 1個, 2個, ...）の対象に対して射を対応させる。
  • オペレータ： いくつか（0個, 1個, 2個, ...）の射に対して射を対応させる。

関手・自然変換の一部を見ているとき

圏論的コンストラクタ、圏論的オペレータが関手・自然変換を定義しても、もちろんかまいません。実際には関手・自然変換なのだが、関手性・自然性に気付かないでいることもあります。

デカルト閉圏Cにおけるカリー化オペレータ ΛA,B,C:C(A×B, C)→C(A, CB) は、Bを固定してA, Cを動かせば、関手 (-)×B と (-)B のあいだの随伴性を主張しているので、自然同型（成分が同型である自然変換）です。しかし、カリー化が自然変換だと知らないで使っている場合もあるだろうし、自然性なしでも役に立ちます。

カリー化と一緒に使う評価射 evA,B:A×BA→B も、随伴性を構成する余単位自然変換ですが、カリー化との関係を理解していれば、2つの添字A, Bを持つ射の族としての扱いでも十分なことも多いです。

リスト型構成子 X|→List(X) や直積型構成子 X, Y|→X×Y も関手・二項関手に拡張できます。リスト型構構成子はリスト・モナドの一部となり、直積型構成子はデカルト・モノイド積関手の一部になります。モナドやデカルト構造は関手概念を使わない定式化もあります（後述）。具体的な計算の場面では、コンストラクタ／オペレータの形のほうが使いやすかったりします。

関手性・自然性を見つけることは非常に重要ですが、関手性・自然性が明らかでないときは、とりあえずはコンストラクタ／オペレータ（コンビネータ）／モダリティとして定式化して調べるのが得策だと思います。どうやっても関手・自然変換にならなくても、役に立ってくれることもあります。

トレース、不動点、微分

よく知られた圏論的オペレータにトレース・オペレータと不動点オペレータがあります。これらのオペレータの下部構造として対称モノイド圏が要求されます。トレース・オペレータTrと不動点オペレータFixは次の形をしています。

   f : A\otimesX → B\otimesX
 --------------------
  TrA,BX(f) : A → B

   f : A\otimesX → X
 --------------------
  FixAX(f) : A → X

CADG（圏論的抽象微分幾何）に登場する微分オペレータを、一般化デカルト微分圏（generalized Cartesian differential category）で定式化した場合は次のようになります。Lは圏論的コンストラクタで、対象Xの線形化と呼ばれるモノがL(X)です。

   f : X → Y
 --------------------------
  DX,Y(f) : L(X)×X → L(Y)

トレース／不動点オペレータについては、過去に説明したことがあるので、それらの記事を参照してください（下のリスト）。トレース／不動点オペレータは、部分的な自然性や変形された自然性（対角自然性）を持ちますが、単なる自然変換として説明することはできません。

CADGの微分オペレータ（微分コンビネータ）については、いずれまた述べる機会があるでしょう。

モナド、デカルト圏、コンパクト閉圏

モナド

モナドの定義には、クライスリ拡張（Kleisli extension）を使うスタイルがあります。このスタイルを使う場合のモナドの構成素は：

  1. 型構成子 X|→T(X)
  2. 総称関数 ηX:X→T(X)
  3. f:X→T(Y) の形の関数に働く高階総称関数（これがクライスリ拡張） (-)# 、f#:T(X)→T(Y)

Tは“値が対象であるコンストラクタ”、ηは“値が射であるコンストラクタ”、(-)#は“オペレータ”です。拡張オペレータはほんとは添字付きで (-)#X,Y:C(X, T(Y))→C(T(X), T(Y)) です。これらのコンストラクタ／オペレータのあいだの条件（公理）によりモナドが定義されます。

デカルト圏

デカルト圏を定義するには幾つものやり方がありますが、そのなかのひとつでは次の構成素を使います。

  1. 対象に対してだけ定義された直積 X, Y|→X×Y
  2. 対象X, Yに対して一意に定義された射 π1X,Y:X×Y→X と π2X,Y:X×Y→Y
  3. 特定された対象1
  4. 対象Xに対して一意に定義された射 !X:X→1
  5. f:X→Y, g:X→Z という形の射に対して定義されたデカルト・ペアリング <-, -> 、<f, g>X,Y,Z:X→Y×Z

直積×は“ニ変項のコンストラクタ”、π1, π1は“添字を2つを持つ射のコンストラクタ”、!は“添字を1つ持つ射のコンストラクタ”、<-, ->は“ニ変項（入力の射が2つ）のオペレータ”です。デカルト・ペアリング・オペレータを添字付きで書けば、<-, ->X,Y,Z:C(X, Y)×C(X, Z)→C(X, Y×Z) 。これらのコンストラクタ／オペレータのあいだの条件（公理）によりデカルト圏が定義されます。

コンパクト閉圏

C = (C, \otimes, I) は対称モノイド圏であるとして、Cにコンパクト閉構造を載せることを考えましょう。そのとき、次の構成素を追加します。

  1. 対象Xに対して一意に定義された対象X*、Xの双対対象
  2. 対象Xに対して一意に定義された射 ηX:I→X*\otimesX 、双対の単位
  3. 対象Xに対して一意に定義された射 εX:X\otimesX*→I 、双対の余単位

(-)*は“コンストラクタ”、ηとεは“射を値とするコンストラクタ”です。これらのコンストラクタ／オペレータのあいだに条件を課します。その条件から、結果的に(-)*は反変関手に拡張できて、η, εも自然変換だとみなせますが、最初から関手性・自然性を仮定する必要はありません。

おわりに

ここで僕が言いたいことは、我々に必要な操作・構成がすべて関手・自然変換であるとは限らないことです。また、最終的には関手・自然変換だと判明するにしても、最初からその姿で現れないかも知れません。そのような操作・構成の定式化に圏論的コンストラクタ／圏論的オペレータが有効です。

コンストラクタ／オペレータは、プログラミングの型構成子／総称関数／高階総称関数などに対応するので、プログラミング的（運算的; calculational）な概念になります。このため、計算には有利となることもあります。

圏論的コンストラクタ／圏論的オペレータは、非全域関手／非自然変換の利用形態のなかで頻出するパターンを取り出して名付けたものです。非全域関手／非自然変換は組織化されて圏論的モダリティとなります。モダリティは、必ずしも関手・自然変換とは限らないメカニズムを使って、圏上の構造を定義する手法です。圏論的モダリティは、圏論の枠内で複雑さ／多様さ（あるいは“汚さ”）をうまく処理してくれます。